题目概述

求 $\sum_{i=0}^{+\infty}{nk\choose ik+r}$ 。

解题报告

我好斯波啊……这个式子很明显不可算，应该考虑实际意义，发现就是在 $nk$ 个里选出 $mod\ K=r$ 个元素的方案数，所以考虑DP $f_{i,j}$ 表示 $i$ 个物品选了 $mod\ K=j$ 个物品的方案数，然后矩阵快速幂。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxk=50;

int n,K,r,MOD;
struct Matrix{
    int r,c,s[maxk][maxk];
    inline void zero(int R,int C) {r=R;c=C;for (int i=0;i<R;i++) for (int j=0;j<C;j++) s[i][j]=0;}
    inline void unit(int R) {zero(R,R);for (int i=0;i<R;i++) s[i][i]=1;}
}T,f;
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.zero(a.r,b.c);
    for (int i=0;i<a.r;i++)
        for (int j=0;j<b.c;j++)
            for (int k=0;k<a.c;k++) AMOD(c.s[i][j],(LL)a.s[i][k]*b.s[k][j]%MOD);return c;
}

inline Matrix Pow(Matrix w,LL b) {static Matrix s;s.unit(w.r);for (;b;b>>=1,w=w*w) if (b&1) s=s*w;return s;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d%d",&n,&MOD,&K,&r);T.zero(K,K);for (int i=0;i<K;i++) T.s[i][i]++,T.s[i][(i+1)%K]++;
    f.zero(1,K);f.s[0][0]++;f=f*Pow(T,(LL)n*K);printf("%d\n",f.s[0][r]);return 0;
}