组合
求 ∑ i = 0 ∞ C n k i k + r \sum_{i=0}^{\infty} C_{n k}^{i k+r} ∑i=0∞Cnkik+r 模 p p p 的值。
这道题题目非常的善良,直接把式子送给我们了,那我们直接开始推式子:
∑ i = 0 ∞ C n k i k + r = ∑ i = 0 ∞ ∑ j = 0 w C w j × C n k − w i k + r − w + j = ∑ j = 0 w C w j ∑ i = 0 ∞ C n k − w i k + r − w + j 令 w = k ∑ j = 0 k C k j ∑ i = 0 ∞ C ( n − 1 ) k i k + r − k + j 令 f ( n , r ) = ∑ i = 0 ∞ C n k i k + r f ( n , r ) = ∑ j = 0 k C k j f ( n − 1 , r − k + j ) 接着我们再来分析 n = 1 的情况 f ( n , r ) = ∑ j = 0 k C k j f ( n − 1 , ( r + j ) % k ) f ( 1 , r ) = ( r = = 0 ? 2 : C k r ) \begin{array}{c}\sum_{i=0}^{\infty} C_{n k}^{i k+r} \\=\sum_{i=0}^{\infty} \sum_{j=0}^{w} C_{w}^{j} \times C_{n k-w}^{i k+r-w+j} \\=\sum_{j=0}^{w} C_{w}^{j} \sum_{i=0}^{\infty} C_{n k-w}^{i k+r-w+j} \\\text { 令 } w=k \\\sum_{j=0}^{k} C_{k}^{j} \sum_{i=0}^{\infty} C_{(n-1) k}^{i k+r-k+j} \\\text { 令 } f(n, r)=\sum_{i=0}^{\infty} C_{n k}^{i k+r} \\f(n, r)=\sum_{j=0}^{k} C_{k}^{j} f(n-1, r-k+j)\\\text {接着我们再来分析}n=1\text {的情况}\\f(n, r)=\sum_{j=0}^{k} C_{k}^{j} f(n-1,(r+j) \% k) \\f(1, r)=\left(r==0 ? 2: C_{k}^{r}\right)\end{array} ∑i=0∞Cnkik+r=∑i=0∞∑j=0wCwj×Cnk−wik+r−w+j=∑j=0wCwj∑i=0∞Cnk−wik+r−w+j 令 w=k∑j=0kCkj∑i=0∞C(n−1)kik+r−k+j 令 f(n,r)=∑i=0∞Cnkik+rf(n,r)=∑j=0kCkjf(n−1,r−k+j)接着我们再来分析n=1的情况f(n,r)=∑j=0kCkjf(n−1,(r+j)%k)f(1,r)=(r==0?2:Ckr)
那么这道题目就水落石出了,先用杨辉三角预处理一遍,预处理一遍组合数,在去推 f f f 数组就好了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,p,k,r,C[105][105];
int f[1005][1005];
int zuhe(int n,int r)
{if(n==1)return r==0?2:C[k][r];if(f[n][r])return f[n][r];int sum=0;for(int i=0;i<=k;i++)sum+=(LL)C[k][i]*zuhe(n-1,(r+i)%k)%p,sum%=p;return f[n][r]=sum%p;
}
int main()
{scanf("%d%d%d%d",&n,&p,&k,&r);for(int i=0;i<=k;i++)//杨辉三角预处理{C[i][0]=1;for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;}printf("%d\n",zuhe(n,r));return 0;
}
但是,你会发现这个代码 RE 了。所以我们需要使用一下矩阵快速幂优化,我就不多说了,上代码。
#include<bits/stdc++.h>
using namespace std;
int P,K,R;
long long N;
struct matrix
{int n,m,a[51][51];matrix(){memset(a,0,sizeof(a));}matrix operator * (const matrix &c)const{matrix res;res.n=n;res.m=c.m;for(int i=0;i<n;i++)for(int j=0;j<c.m;j++)for(int k=0;k<m;k++)res.a[i][j]=(res.a[i][j]+1LL*a[i][k]*c.a[k][j]%P)%P;return res;}
}a,b;
void Pow(matrix x,long long y)
{while(y){if(y&1)a=a*x;x=x*x;y>>=1;}
}
int main()
{cin>>N;scanf("%d%d%d",&P,&K,&R);N=1LL*N*K;a.n=1;a.m=K;a.a[0][0]=1;b.n=b.m=K;for(int i=0;i<K;i++){b.a[i][i]++;b.a[i][(i+1)%K]++;}Pow(b,N);printf("%d",a.a[0][R]);return 0;
}