当前位置: 代码迷 >> 综合 >> BZOJ 3028 食物
  详细解决方案

BZOJ 3028 食物

热度:71   发布时间:2024-01-19 02:21:43.0

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 10007int 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 10007int 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;
}