BZOJ 3028: 食物 生成函数

title

\(~\)
BZOJ 3028
Description

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

Input

输入一个数字N，1<=n<=10^500

Output

如题

Sample Input

输入样例1
1
输入样例2
5

Sample Output

输出样例1
1
输出样例2
35

analysis

根据生成函数可知：

承德汉堡：\(1+x^2+x^4+...=\frac{1}{1?x^2}\)

可乐：\(1+x\)

鸡腿：\(1+x+x^2=\frac{x^3?1}{x?1}\)

蜜桃多：\(x+x^3+x^5+...=\frac{x}{1?x^2}\)

鸡块：\(1+x^4+x^8+...=\frac{1}{1?x^4}\)

包子：\(1+x+x^2+x^3=\frac{x^4?1}{x?1}\)

土豆片炒肉：\(1+x\)

面包：\(1+x^3+x^6+x^9+...=\frac{1}{1?x^3}\)

乘起来是\(\frac{x}{(1?x)^4}\)。

然后根据某公式，生成函数\(\frac{1}{(1?x)^n}=(1+x+x^2+x^3+...)^n\)，求 \(m\) 项系数就相当于组合数 \(C^{n?1}_{n+m?1}\)。

然后乘上 \(x\) 就相当于右移一位，就变成了 \(C^{n?1}_{n+m?2}\)，要求第 \(n\) 位，答案就是 \(C^3_{n+2}\)。

code

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
 
char buf[1<<15],*fs,*ft;
inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
template<typename T>inline void read(T &x)
{
    x=0;
    T f=1, ch=getchar();
    while (!isdigit(ch) && ch^'-') ch=getchar();
    if (ch=='-') f=-1, ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
 
template<typename T>inline void write(T x)
{
    if (!x) { putchar('0'); return ; }
    if (x<0) putchar('-'), x=-x;
    T num=0, ch[20];
    while (x) ch[++num]=x%10+48, x/=10;
    while (num) putchar(ch[num--]);
}
 
inline void exgcd(int a,int b,int &x,int &y)
{
    if (!b)
    {
        x=1,y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-a/b*y;
}
 
char ch[510];
int main()
{
    scanf("%s",ch+1);
    int len=strlen(ch+1),n=0;
    for (int i=1; i<=len; ++i) n=((n<<1)+(n<<3)+(ch[i]^48))%mod;
    int x,y;
    exgcd(6,mod,x,y);
    x=(x%mod+mod)%mod;
    write((n%mod*(n+1)%mod*(n+2)%mod)*x%mod),puts("");
    return 0;
}

BZOJ 3028: 食物 生成函数

原文：https://www.cnblogs.com/G-hsm/p/11318529.html