题解 P6078 【[CEOI2004] Sweets】

· · 题解

生成函数入门题。

题意：n 种糖，每种糖有 m_i 个，求选出 l 到 r 颗糖的方案数。1 \le n \le 10,0 \le l,r \le 1e7,0 \le m_i \le 1e6

原题

本文适合生成函数入门。

我们尝试用一个函数来描述状态：令系数表示方案数，令指数表示拿了几颗糖。例如，2x^2 表示有两种方法拿两颗糖。

那么，对于每种糖，既然对于任意 i\le m_i 都只有一种方法拿走 i 颗这种糖，它的生成函数就是这个样子：

f(i)=\sum_{j=0}^{m_i}\limits x^j

我们发现，如果拿 a_1 颗糖有 b_1 种方案，拿 a_2 颗糖有 b_2 种方案，相当于有 b_1\cdot b_2 种拿 a_1+a_2 颗糖的方案。可以用 b_1x^{a_1} \cdot b_2x^{a_2}=b_1\cdot b_2\cdot x^{a_1+a_2} 来描述这个过程。

于是，我们枚举当前这种糖拿几颗，与之前计算得到的结果按上述方法更新答案，这样一步步枚举糖下去最后就是答案。

实际上这就是乘法。

所以每种糖的 f 全乘起来，指数在 l,r 之间的系数和就是答案 ( g ) 。

但是，如果大力多项式乘法算 g，你看一眼数据范围就知道会出事情。我们考虑有什么巧妙的方法。

首先，问题可以转化为求 g 的系数的前缀和。那么假设我们现在要求从x^0 到 x^{lim} 的系数前缀和。

观察 f：

f(i)=\sum_{j=0}^{m_i}\limits x^j,x\cdot f(i)=\sum_{j=1}^{m_i+1} x^j f(i)-x\cdot f(i)=(1-x)f(i)=1-x^{m_i+1} f(i)=\dfrac{1-x^{m_i+1}}{1-x}

上面的推导在生成函数中似乎很重要。

于是最后的结果等于 \dfrac{\prod{(1-x^{m_i+1})}}{(1-x)^n}

上面的东西，由于 n \le 10 ，我们可以直接大力 \text{dfs} 拆式子，假设它拆出来个 g' 好了

观察下面的东西：

\dfrac{1}{(1-x)^n} =(1-x)^{-n}

二项式定理拆开，得到

\sum_{i\ge0}{ \binom{-n}{i} \cdot(-x)^i } =\sum_{i\ge0}{\dfrac{(-n)(-n-1)...(-n-i+1)}{i!}\cdot (-x)^i} =\sum_{i\ge0}{\dfrac{n(n+1)...(n+i-1)}{i!}\cdot x^i} =\sum_{i\ge0}{\binom{n+i-1}{i}\cdot x^i}

此时我们将除法转换成了乘法。

那么我们考虑 g' 上一项 ax^b 对答案的贡献是多少。

a \cdot \sum_{}^{lim-b}\binom{n+i-1}{i}=a \cdot \binom{n+lim-b}{lim-b}

（不知道为什么的话，可以用组合数的递推公式 \binom{m}{n}=\binom{m-1}{n-1}+\binom{m-1}{n} 证一下，不难）

那么现在只剩下最后一个问题，怎么算组合数了。毕竟模数是 2004，很不幸不是质数，导致没有逆元。当然可以扩展卢卡斯，但是似乎有更便捷的方法。

\binom{n+lim-b}{lim-b}=\binom{n+lim-b}{n} =\dfrac{(n+lim-b)(n+lim-b-1)...}{n!}

注意到上面的部分总共只会有 n 个，能迅速得到（令其为 x），下面的部分也很好算。

令x=2004\cdot n!\cdot k2+r,\dfrac{x}{n!}\equiv ans \pmod{2004}，k 为整数

\dfrac{x}{n!}=ans+2004\cdot k1 2004\cdot n! \cdot k2+r=ans\cdot n!+2004\cdot k1\cdot n! r=ans\cdot n! + 2004\cdot k'\cdot n!=(ans+2004\cdot k')n! \dfrac{r}{n!}=ans+2004\cdot k' \dfrac{r}{n!}\equiv ans \pmod{2004}

综上，我们可以计算 x 在模 2004\cdot n! 意义下的答案，将其除以 n! 得到 x 除以 n! 在模 2004 意义下的结果。

扩展开来，对于模数非质数的除法，可以先把模数乘上除数，再将运算结果除以除数得到答案。算是个不太有用的小技巧？虽然有点偏题，但是其它题解都没有给出这个的证明。

那么，这道题就解决了。

代码：

#include <cstdio>

typedef long long ll;
const int maxn=15,mod=2004;

int n,l,r;ll a[maxn],fac=1,sum=0;

inline ll C(int x,int y){
    ll M=mod*fac,ans=1;
    for(int i=y-x+1;i<=y;i++) ans=(ans*i)%M;
    return (ans/fac)%mod;
}

void dfs(int step,int val,int key,int lim){//step->第几种糖 val->系数 key->次数 lim->前lim次的前缀和
    if(key>lim) return;
    if(step==n+1){
        sum+=1ll*val*C(n,n+lim-key)%mod;
        sum%=mod;return;
    }
    dfs(step+1,val,key,lim),dfs(step+1,-val,key+a[step]+1,lim);
}

inline ll solve(int lim){
    sum=0;dfs(1,1,0,lim);
    return (sum%mod+mod)%mod;
}

int main(){
    scanf("%d%d%d",&n,&l,&r);for(int i=1;i<=n;i++) scanf("%lld",&a[i]),fac=fac*i;//fac不能取模2004，小心顺手打个%mod上去
    printf("%lld\n",((solve(r)-solve(l-1))%mod+mod)%mod);
    return 0;
}