题解：P10780 BZOJ3028 食物

组合题、个数、累和……能想到生成函数。

仔细看一下，发现这题的生成函数很模版，可以依次求生成函数，再累乘。

承德汉堡：

f_1(x)=x^0+x^2+…+x^{2k}+…=\frac{1}{1-x^2}

在无穷累和且

0<x<1

的情况下这个等式是恒成立的，移项即可证明。

同理，鸡腿：

f_2(x)=x^0+x^1+x^2

，可乐：

f_3(x)=x^0+x^1

，包子：

f_4(x)=x^0+x^1+x^2+x^3

，土豆片炒肉:

f_5(x)=x^0+x^1

。

鸡块：

f_6(x)=x^0+x^4+…+x^{4k}+…=\frac{1}{1-x^4}

蜜桃多：

f_7(x)=x^1+x^3+…+x^{2k+1}+…=\frac{x}{1-x^2}

面包：

f_8(x)=x^0+x^3+…+x^{3k}+…=\frac{1}{1-x^3}

所以总的也就是：

f(x)=\sum_{i=1}^{8}f_i(x)=\frac{x(x^0+x^1)^2(x^0+x^1+x^2)(x^0+x^1+x^2+x^3)}{(1-x^2)^2(1-x^3)(1-x^4)}=\frac{x(1-x^2)^2(1-x^3)(1-x^4)}{(1-x)^4}\times\frac{1}{(1-x^2)^2(1-x^3)(1-x^4)}=\frac{x}{(1-x)^4}=x(1+x+x^2+x^3+…+x^k+…)^4

现在要取

n

次项的系数，可以将问题转化为：把

n-1

个小球放入

4

个格子中，格子允许为空，求方案数。

由插板法，可以得知答案为

C^{4-1}_{n-1+4-1}=\frac{n(n+1)(n+2)}{3!}

代码如下：

CPP

/*胡金梁*/
#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
const int mod=1e4+7;
int ksm(int a,int b)
{
	int re=1;
	while(b)
	{
		if(b&1)
		{
			re*=a;
			re%=mod;
		}
		a*=a;
		a%=mod;
		b/=2;
	}
	return re;
}
signed main(){
#if __MY_TEST__
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n=0;
	char ch;
	while(cin>>ch)
	{
		n=(n*10+ch-'0')%mod;
	}
	cout<<n*(n+1)%mod*(n+2)%mod*ksm(6,mod-2)%mod;
#if __MY_TEST__
	fclose(stdin);
	fclose(stdout);
#endif
}

题解：P10780 BZOJ3028 食物

文章操作

相关推荐

评论

题解：P10780 BZOJ3028 食物