首页 > 代码库 > Bzoj3028食物

Bzoj3028食物

  1. Description

    明明这次又要出去旅游了,和上次不同的是,他这次要去宇宙探险!
    我们暂且不讨论他有多么NC,他又幻想了他应该带一些什么东西。理所当然的,你当然要帮他计算携带N件物品的方案数。
    他这次又准备带一些受欢迎的食物,如:蜜桃多啦,鸡块啦,承德汉堡等等
    当然,他又有一些稀奇古怪的限制:
    每种食物的限制如下:
           承德汉堡:偶数个
           可乐:0个或1个
                鸡腿:0个,1个或2个
                蜜桃多:奇数个
                鸡块:4的倍数个
                包子:0个,1个,2个或3个
           土豆片炒肉:不超过一个。
                面包:3的倍数个
     
     
     
    注意,这里我们懒得考虑明明对于带的食物该怎么搭配着吃,也认为每种食物都是以‘个’为单位(反正是幻想嘛),只要总数加起来是N就算一种方案。因此,对于给出的N,你需要计算出方案数,并对10007取模。
    数据范围 : n<=10^500
     
    ----------------------------------------------------------此后一千里---------------------------------------------------------------
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
     
    推一发生成函数后乘起来是这个样子 x / (1 - x) ^ 4
    然后不会了,并不知道封闭形式怎么求系数。。。。。
    然后膜了一发大爷的题解,
    大概是系数就是泰勒展开后 xn 前的系数,
    所以先求一发n阶导数,然后带入泰勒展开发现是C(n-2,3)
    然后就没有然后了。。。。
    出题人多大脑洞。。。。
    upd : 其实考虑封闭形式的话,头上的x就是函数右移一位,所以我们实际去求4种物品无限个选出n-1种的方案数,就是插板法sb题了。。。。
    代码 : 
    技术分享
    #include <cstdio>  
    #include <cstring>  
    #include <iostream>  
    #include <algorithm>  
    #define M 510  
    #define MOD 10007  
    using namespace std;  
    int n;  
    char s[M];  
    int main()  
    {  
        int i;  
        scanf("%s",s+1);  
        for(i=1;s[i];i++)  
            (n=(n<<1)+(n<<3)+(s[i]-0))%=MOD;  
        cout<<(n*(n+1)%MOD*(n+2)%MOD*1668%MOD)<<endl;  
        return 0;  
    }  
    View Code

     

Bzoj3028食物