好题集(10) - LG P6078 [CEOI 2004] Sweets

题目传送门。

题意：有 \(n\) 种糖，第 \(i\) 种糖至多可选 \(m_i\) 颗；求有多少种不同的选糖的方案，使得糖的总数在 \([a,b]\) 之间。答案对 \(2004\) 取模。\(1\le n\le 10,1\le a,b\le 10^7,1\le m_i\le 10^6\)。

令单项式 \(px^q\) 表示拿 \(q\) 颗糖的方案数为 \(p\)。

对于第 \(i\) 种糖，要拿出 \(j\le m_i\) 颗糖的方案数固定为 \(1\)。于是定义其生成函数：

\[f_i(x)=\sum\limits_{j=0}^{m_i}x^j\tag{1} \]

其中 \(x^j\) 的系数表示拿 \(j\) 颗第 \(i\) 种糖的方案数。按照上面提到的性质，这个数固定为 \(1\)。

假如拿 \(p_1\) 颗糖有 \(q_1\) 种方案，拿 \(p_2\) 颗糖有 \(q_2\) 种方案，那么由乘法原理，拿 \((p_1+p_2)\) 颗糖就有 \((q_1\cdot q_2)\) 种方案。体现在我们之前的定义上，就是 \(q_1 a^{p_1}\cdot q_2 a^{p_2}=q_1\cdot q_2 a^{p_1+p_2}\)。

扩展开来可以得到，如果把 \(A=\prod\limits_{i=1}^{n}f_i(x)\) 暴力展开并整理出来，那么次数在 \([a,b]\) 的项的系数和即为答案。

记 \(g(l)=\sum\limits_{i=1}^n q_i\)，其中 \(q_i\) 为在 \(A\) 的展开式中次数为 \(i\) 的项的系数。由前缀和思想，答案即为 \(g(b)-g(a-1)\)。

现在考虑如何求 \(g\)；要求 \(g\)，先求 \(f\)。尝试求其封闭形式：

\[\begin{align*} x\cdot f_i(x)&=x\cdot\sum\limits_{j=0}^{m_i}x^j\\ &=\sum\limits_{j=1}^{m_i+1}x^j\tag{2} \end{align*} \]

\((1)-(2)\)：

\[\begin{align*} f_i(x)-x\cdot f_i(x)&=(\sum\limits_{j=0}^{m_i}x^j)-(\sum\limits_{j=1}^{m_i+1}x^j)\\ &=x^0-x^{m_i+1}\\ &=1-x^{m_i+1} \end{align*} \]

又 \(f_i(x)-x\cdot f_i(x)=(1-x)\cdot f_i(x)\)，有 \((1-x)\cdot f_i(x)=1-x^{m_i+1}\)，整理得：

\[f_i(x)=\frac{1-x^{m_i+1}}{1-x} \]

这就是我们要的封闭形式了。回代：

\[\begin{align*} A&=\prod\limits_{i=1}^{n}f_i(x)\\ &=\prod\limits_{i=1}^{n}\frac{1-x^{m_i+1}}{1-x}\\ &=\frac{\prod\limits_{i=1}^{n}(1-x^{m_i+1})}{(1-x)^n} \end{align*} \]

由于 \(n\) 很小，因此分子部分可以直接 DFS 暴力求解；下面研究分母如何计算。

推一下：

\[\begin{align*} \frac{1}{(1-x)^n}&=(1-x)^{-n}\\ &=\sum\limits_{i=0}^{\infty}C_{-n}^i (-x)^i\\ &=\sum\limits_{i=0}^{\infty}\frac{(-n)!}{i!(-n-i)!}(-x)^i\\ &=\sum\limits_{i=0}^{\infty}\frac{\prod\limits_{i=-n-i+1}^{-n}i}{i!}(-x)^i\tag{3}\\ &=\sum\limits_{i=0}^{\infty}\frac{\prod\limits_{i=n+i-1}^{n}i}{i!}\tag{4}\\ &=\sum\limits_{i=0}^{\infty}C_{n+i-1}^i x^i\\ \end{align*} \]

其中从 \((3)\) 到 \((4)\) 的原理是分子上提出了 \(i\) 个负号，\(x\) 项也提出了 \(i\) 个负号；两两相消，得到正号。

考虑前一项 \(ax^b\) 的贡献。

\[a\cdot\sum\limits_{i=0}^{l-b}C_{n+i-1}^i=a\cdot C_{n+l-b}^{l-b} \]

原理是组合数递推公式。

于是考虑如何求组合数，发现最大的瓶颈在于模数不是质数，无法求逆元。不会 exLucas，我们考虑如何简单地处理这一问题。还是推式子：

\[\begin{align*} C_{n+l-b}^{l-b}&=\frac{(n+l-b)!}{(l-b)!n!}\\ &=\frac{\prod\limits_{i=l-b+1}^{n+l-b}i}{n!} \end{align*} \]

下面这一坨好算；设上面这一坨为 \(B\)。显然组合数必然是一个整数，那么 \(B\) 一定含一个为 \(n!\) 的因子。又考虑到是在模 \(2004\) 意义下同余的，我们可以设 \(B=k_1\cdot(n!\cdot2004)+r_1\)，其中 \(k_1=\lfloor\frac{B}{n!\cdot 2004}\rfloor,r_1=B\bmod(n!\cdot 2004)\)。同样由于模 \(2004\)，我们可设答案 \(\frac{B}{n!}=ans+2004\cdot k_2\)，其中 \(ans\) 为答案。于是我们得到：

\[\frac{\prod\limits_{i=l-b+1}^{n+l-b}i}{n!}\equiv ans\pmod{2004}\\ \frac{B}{n!}\equiv ans\pmod{2004}\\ \frac{B}{n!}=ans+2004\cdot k_2\\ B=n!(ans+2004\cdot k_2)\\ k_1\cdot n!\cdot 2004+r_1=ans\cdot n!+k_2\cdot n!\cdot 2004\\ \]

把 \(r_1\) 拆出来：

\[\begin{align*} r_1&=ans\cdot n!+k_2\cdot n!\cdot 2004-k_1\cdot(n!\cdot2004)\\ &=ans\cdot n!+2004(k_2-k_1)\cdot n!\\ &=\Big(ans+2004(k_2-k_1)\Big)\cdot n! \end{align*} \]

接着变形：

\[\frac{r_1}{n!}=ans+2004(k_2-k_1) \]

即：

\[\frac{r_1}{n!}\equiv ans\pmod{2004} \]

因此我们可以计算 \(A\bmod(2004\cdot n!)\)，再将得到的结果除以 \(n!\)。

扩展开来，对于模数非质数的除法，可以先把模数乘上除数，再将运算结果除以除数得到答案。

代码：

#include<iostream>
#define int long long
using namespace std;const int N=1e2+5;int n,a,b;int m[N];namespace Math{const int p=2004;int np;int jc=1;inline int mul(int a,int b){return (((a%p+p)%p)*((b%p+p)%p))%p;}inline int C(int n,int m){int res=1;for(int i=n-m+1;i<=n;++i)(res*=i)%=np;return (res/jc)%p;}inline void dfs(int st/*步数*/,int xs/*系数*/,int cs/*次数*/,int lim/*当前在求 [0,lim] 次项的系数和*/,int &ans){if(cs>lim)return ;if(st==n+1)return (ans+=mul(xs,C(n+lim-cs,n)))%=p,void();return dfs(st+1,xs,cs,lim,ans),dfs(st+1,-xs,cs+m[st]+1,lim,ans),void();}inline int calc(int lim,int ans=0){//上文中的 greturn dfs(1,1,0,lim,ans),ans;}}using namespace Math;signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>a>>b;for(int i=1;i<=n;++i)cin>>m[i],jc*=i;return np=jc*p,cout<<((calc(b)-calc(a-1))%p+p)%p<<"\n",0;
}

提交记录。