自动搬运

查看原文

来自洛谷，原作者为

	Rui_R El Psy Congroo

搬运于2025-08-24 22:17:12，当前版本为作者最后更新于2020-11-05 11:35:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

生成函数入门题。

题意：$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;
}