摘要:生成函数+泰勒展开+隔板法

BZOJ3028食物

题面

题目分析

首先可以对题目中的限制做生成函数,设$ai$为某个限制携带$i$个的方案数.

于是有:

把这些生成函数乘起来,得到$F(x)=\frac{x}{(1-x)^4}$.

根据泰勒展开,有:$\sum^\infty_{i=0} x^i=\frac{1}{1-x}$,所以:

就得到了$F(x)$的展开形式,现在要求出的是$n$次项的系数.

考虑这样一个关系,对于$n$次项的系数$a$,它由4个多项式进行卷积得到,所以$n$次项的系数与$n$的组合方式有关(想一下卷积的过程),把$n$分为4个非负数相加,因为可能出现0所以左右等式同时加4,得到:

使用隔板法,在$n+4$个数形成的$n+3$个位置中插入3个板形成4个数,那么显然有$\binom{n+3}{3}$种方案,又因为一开始的系数都为1,所以$a=\binom{n+3}{3}$.

再考虑上前面的$x$,$n$次项的系数为$\binom{n+2}{3}$种.

代码(2 2 9 狂 喜)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=11451,mod=10007;
lxl n;
char s[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline lxl FastPow(lxl a,lxl b)
{
lxl sum(1);
for(;b;b>>=1,a=a*a%mod)(b&1)&&(sum=sum*a%mod);
return sum;
}
int main(void)
{
scanf("%s",s+1);
// std::cout<<s<<endl;
for(R int i(1),len=strlen(s+1);i<=len;++i)n=(n*10+s[i]-'0')%mod;
printf("%lld\n",((n*n*n)%mod+(3*n*n)%mod+2*n%mod)%mod*FastPow(6,mod-2)%mod);
return 0;
}