题解 P5160 【WD与循环】
ezoixx130
2019-01-04 08:20:44
### 题意：
有一个数列 $a_1,a_2,a_3,...,a_n$，其中每个数都是自然数，问有多少种方案使得它们的和不超过 $m$，答案对 $19491001$ 取模。
### 题解：
题目是求和不超过 $m$ 的方案数，这个有点难处理，我们考虑求出和等于 $i$ 的方案数，再累加起来。
那么这就转化为了一个经典问题：$n$ 个数的和等于 $m$ 的方案数，考虑插板法解决，和为 $m$ 相当于 $m$ 个球，$m-1$ 个空位，$n$ 个数相当于 $n-1$ 个板，那么答案就是 $m-1 \choose n-1$。
但是这样考虑的话是 $n$ 个正整数的和等于 $m$ 的方案数，如何将自然数变为正整数呢？
每个数都加一即可，问题变为 $n$ 个正整数的和等于 $m+n$ 的方案数，答案为 $m+n-1 \choose n-1$。
于是题目要求的答案是 $\sum\limits_{i=0}^{m}{i+n-1 \choose n-1}$
然后由于 $\sum\limits_{k=0}^{n}{m+k \choose k}={m+n+1 \choose n}$。
所以答案就是 $\sum\limits_{i=0}^{m}{i+n-1 \choose n-1}={n+m \choose m}$。
然而这需要支持 $10^{18}$ 以内的组合数计算，发现模数很小，预处理模数以内的阶乘以及阶乘逆元，使用 lucas 定理即可。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define mod 19491001
int fac[mod+1],inv[mod+1];
int qpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=(long long)res*a%mod;
a=(long long)a*a%mod;
b>>=1;
}
return res;
}
void init()
{
fac[0]=fac[1]=1;
for(int i=2;i<mod;++i)fac[i]=(long long)fac[i-1]*i%mod;
inv[0]=1;
inv[mod-1]=qpow(fac[mod-1],mod-2);
for(int i=mod-2;i>=1;--i)inv[i]=(long long)inv[i+1]*(i+1)%mod;
}
int c(int n,int m)
{
if(n>m)return 0;
else return (long long)fac[m]*inv[n]%mod*inv[m-n]%mod;
}
int lucas(long long n,long long m)
{
if(n<mod && m<mod)return c(n,m);
else return (long long)lucas(n/mod,m/mod)*lucas(n%mod,m%mod)%mod;
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--)
{
long long n,m;
scanf("%lld%lld",&n,&m);
printf("%d\n",lucas(n,n+m));
}
}
```