BZOJ 3028 食物

3/8/2017来源:ASP.NET技巧人气:2147

Description

明明这次又要出去旅游了,和上次不同的是,他这次要去宇宙探险! 我们暂且不讨论他有多么NC,他又幻想了他应该带一些什么东西。理所当然的,你当然要帮他计算携带N件物品的方案数。 他这次又准备带一些受欢迎的食物,如:蜜桃多啦,鸡块啦,承德汉堡等等 当然,他又有一些稀奇古怪的限制: 每种食物的限制如下:        承德汉堡:偶数个        可乐:0个或1个             鸡腿:0个,1个或2个             蜜桃多:奇数个             鸡块:4的倍数个             包子:0个,1个,2个或3个        土豆片炒肉:不超过一个。             面包:3的倍数个       注意,这里我们懒得考虑明明对于带的食物该怎么搭配着吃,也认为每种食物都是以‘个’为单位(反正是幻想嘛),只要总数加起来是N就算一种方案。因此,对于给出的N,你需要计算出方案数,并对10007取模。  

Input

输入样例1   1 输出样例1   1   输入样例2   5 输出样例2   35  数据范围    对于40%的数据,1<=N<=100000;    对于所有数据,1<=n<=10^500;  

Output

Sample Input

Sample Output

HINT

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

生成函数+逆元~

生成函数ax^b表示取b种该食物有a种方案,不同生成函数之间相乘,最终得到的函数中x^(i-1)的系数就是总共取i样的方案数。

承德汉堡:1/(1-x^2)

可乐:1+x

鸡腿:1+x+x^2

蜜桃多:x/(1-x^2)

鸡块:1/(1-x^4)

包子:1+x+x^2+x^3

土豆片炒肉:1+x

面包:1/(1-x^3)=1/(1-x)/(x^2+x+1)

把它们全部乘起来得到:x/(1-x)^4,即为x*(1-x)^(-4)

(注意1+x+x^2+x^3是(1+x)(x^2+1)不是(1+x)x^2--)

这个式子的第n-1项是x*C(n+2,n-1)*x^(n-1),

所以最终答案就是C(n+2,n-1)=C(n+2,3)。

n很大,每输入一位都取模再*10化简,至于组合数,直接拆开求逆元计算就好了,6的逆元求出来是1668,程序附在后面~

#include<cstdio>
#include<cstring>
#define modd 10007

int n,x;
char s[501];

int main()
{
	scanf("%s",s);x=strlen(s);
	for(int i=0;i<x;i++) n=((n*10%modd)+s[i]-'0')%modd;
	PRintf("%d\n",((n*(n+1)%modd)*(n+2)%modd)*1668%modd);
	return 0;
}

求逆元:

#include<cstdio>
#include<cstring>
#define modd 10007

int n,x;
char s[501];

int mi(int u,int v)
{
	int k=1;
	while(v)
	{
		if(v&1) k=(k*u)%modd;
		u=(u*u)%modd;v>>=1;
	}
	return k;
}

int main()
{
	printf("%d\n",mi(6,modd-2));
	return 0;
}