Description
求：
(∑i=1∞Cik+rnk)modP
n<109,r<k<50,P<230−1
Solution
指向【一大堆常犯的错误、提醒和公式】的第19条； 我们来考虑一下这个式子的意义： 在nk个物品中，选出x个物品，使得
xmodk=r
转化成这样以后就简单多了， 设DP
fi,j
表示选了前i物品，余数为j的方案数， 暴力转移：
fi,j=fi−1,j+fi−1,((j−1+k)modk)
发现，这东西满足倍增的性质，就是可以从i转移到2i， 这样用矩阵乘法或倍增即可
复杂度：
O(k3log(n))
或
O(k2log(n))
Code
using namespace std;
typedef long long LL;
const
int N=
55;
int m,mo,m1;
LL n,f[N],ans[N];
LL g[N];
LL ksm(LL
q,LL w)
{
LL ans=
1;
for(;w;w>>=
1,
q=
q*q%mo)
{
if(w&
1)ans=ans
*q%mo;
}
return ans;
}
int main()
{
int q,w;LL SR;
scanf(
"%lld%d%d%d",&n,&mo,&
m,&m1);
n
*=(LL)
m;
if(
m==
1)
{
printf(
"%lld",ksm(
2,n));
return 0;
}
ans[
0]=
1;
f[
1]=f[
0]=
1;
for(;n;n>>=
1)
{
if(n&
1)
{
fo(i,
0,
m-
1)fo(j,
0,
m-
1)
g[(i+j)
%m]=(g[(i+j)
%m]+f[i]
*ans[j])
%mo;
fo(i,
0,
m-
1)ans[i]=g[i],g[i]=
0;
}
fo(i,
0,
m-
1)fo(j,
0,
m-
1)
g[(i+j)
%m]=(g[(i+j)
%m]+f[i]
*f[j]
%mo)
%mo;
fo(i,
0,
m-
1)f[i]=g[i],g[i]=
0;
}
printf(
"%lld\n",ans[m1]);
return 0;
}
