4870: [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
HINT
Source
dp+矩阵快速幂
很坑的就是k会等于1
所以不能写A.a[i][i]=1,A.a[i][(i-1+k)%k]=1
应该写A.a[i][i]++,A.a[i][(i-1+k)%k]++;
/**************************************************************
Problem: 4870
User: white_hat_hacker
Language: C++
Result: Accepted
Time:680 ms
Memory:820 kb
****************************************************************/ #include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define ll long long
#define MAXN 52
using namespace std;
ll n,p,k,r;
struct Mat{
ll a[MAXN][MAXN];
Mat(){
memset(a,,sizeof(a));
}
void operator *= (const Mat &B){
ll ret[MAXN][MAXN];
memset(ret,,sizeof(ret));
for(int i=;i<k;i++){
for(int j=;j<k;j++){
for(int q=;q<k;q++){
ret[i][j]=(ret[i][j]+a[i][q]*B.a[q][j])%p;
}
}
}
memcpy(a,ret,sizeof(a));
}
};
int main()
{
Mat A,B;
scanf("%lld%lld%lld%lld",&n,&p,&k,&r);
ll b=n*k;
for(int i=;i<k;i++){
A.a[i][i]++,A.a[i][(i-+k)%k]++;
B.a[i][i]=;
}
while(b){
if(b&){
B*=A;
}
b>>=;
A*=A;
}
printf("%lld\n",B.a[r][]);
return ;
}