题目描述
组合数 \(C_n^m\) 表示的是从 \(n\) 个互不相同的物品中选出 \(m\) 个物品的方案数。举个例子， 从 \((1, 2, 3)\) 三个物品中选择两个物品可以有 \((1, 2)\)，\((1, 3)\)，\((2, 3)\) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 \(C_n^m\) 的一般公式：
\[C_n^m = \frac {n!} {m! \ (n - m)!} \]其中 \(n! = 1 \times 2 \times \cdots \times n\)。（特别地，当 \(n = 0\) 时，\(n! = 1\)；当 \(m > n\) 时，\(C_n^m = 0\)。）
小葱在 NOIP 的时候学习了 \(C_i^j\) 和 \(k\) 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现，\(C_i^j\) 是否是 \(k\) 的倍数，取决于 \(C_i^j \bmod k\) 是否等于 \(0\)，这个神奇的性质引发了小葱对 \(\mathrm{mod}\) 运算（取余数运算）的兴趣。现在小葱选择了是四个整数 \(n, p, k, r\)，他希望知道
\[\left( \sum_{i = 0}^\infty C_{nk}^{ik + r} \right) \bmod p, \]即
\[\left( C_{nk}^{r} + C_{nk}^{k + r} + C_{nk}^{2k + r} + \cdots + C_{nk}^{(n - 1)k + r} + C_{nk}^{nk + r} + \cdots \right) \bmod p \]的值。
对于 \(100\%\) 的测试点，\(1 \leq n \leq 10^9, 0 \leq r < k \leq 50, 2 \leq p \leq 2^{30} - 1\)。
题解
所求即为
\[\sum\limits_{i\ mod\ k=r}\binom{nk}{i}=\sum\limits_{i\ mod\ k=r}[x^i](1+x)^{nk}=[x^r]((1+x)^{nk}\ mod\ (x^k-1)) \]循环卷积一下，做完了。
代码：
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=(l);i<=(r);++i)
typedef long long ll;
using namespace std;
int n,p,k,r;
vector<ll> operator * (vector<ll> &f,vector<ll> &g)
{
vector<ll> res;
res.resize(k);
For(i,0,k-1)
res[i]=0;
int len_f=f.size()-1,len_g=g.size()-1;
For(i,0,len_f)
{
For(j,0,len_g)
(res[(i+j)%k]+=(f[i]*g[j]))%=p;
}
return res;
}
vector<ll> qpow(vector<ll> a,ll b)
{
vector<ll> res;
res.resize(k);
For(i,1,k-1)
res[i]=0;
res[0]=1;
while(b)
{
if(b&1)
res=res*a;
a=a*a;
b>>=1;
}
return res;
}
int main()
{
scanf("%d%d%d%d",&n,&p,&k,&r);
ll tmp=n;
tmp*=(1ll*k);
vector<ll> base;
base.resize(k);
For(i,2,k-1)
base[i]=0;
if(k==1)
{
base[0]=2;
base[0]%=p;
}
else if(k!=1)
{
base[0]=1;
base[1]=1;
}
vector<ll> ans=qpow(base,tmp);
printf("%lld",ans[r]);
return 0;
}