【BZOJ4870】[Shoi2017]组合数问题
Description
Input
第一行有四个整数 n, p, k, r，所有整数含义见问题描述。
1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 − 1
Output
一行一个整数代表答案。
Sample Input
2 10007 2 0
Sample Output
8
题解：题意：nk个数，选出一些数，使得选出来的数的个数%k=r的方案数（所以就不要管原来的题面了！）
然后这变成了一道动态规划题，由于nk很大我们试着用矩阵乘法，发现很容易就能构造出转移矩阵，具体不说了
当然，如果不强行使用矩乘的话也是可以搞的，设f[i][j]表示i个数，取出一些数使得个数%k=j的方案数，然后可以得到转移方程
f[i*2][(j+j')%k]+=f[i][j]*f[i][j']
显然这个式子是满足可加性的，所以可以直接用倍增的思想搞一搞，时间复杂度比矩乘还少一个n
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
ll n,p;
ll k,r;
typedef struct matrix
{
ll v[60];
}M;
M x,ans,emp;
M mpls(M a,M b)
{
M c=emp;
int i,j;
for(i=0;i<k;i++)
for(j=0;j<k;j++)
c.v[(i+j)%k]=(c.v[(i+j)%k]+a.v[i]*b.v[j])%p;
return c;
}
void pm(ll y)
{
while(y)
{
if(y&1) ans=mpls(ans,x);
x=mpls(x,x),y>>=1;
}
}
int main()
{
scanf("%lld%lld%d%d",&n,&p,&k,&r);
ans.v[0]=1,x.v[0]=1,x.v[1%k]++;
pm(n*k);
printf("%lld",ans.v[r]);
return 0;
}