题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4870
题意：见原题面。
就是个模 k 下的组合数递推啊... 去年好像在考场上很 naive 的爆零了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define K 55 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,p,k,r; int f[K],g[K],h[K]; void mul(int *a,int *b) { for(int i=0;i<=k;i++) for(int j=0;j<=k;j++) (h[(i+j)%k]+=1ll*a[i]*b[j]%p)%=p; for(int i=0;i<=k;i++)a[i]=h[i],h[i]=0; } void Qpow(ll b) { while(b) { if(b&1)mul(f,g); b>>=1,mul(g,g); } } int main() { n=read(),p=read(),k=read(),r=read(); f[0]=1,g[0]=1,g[1%k]++; Qpow(1ll*n*k); printf("%d\n",f[r]%p); } |
Comments | NOTHING