「Bzoj 4870」「六省联考2017」组合数问题 (组合数+矩阵快速幂)

BZOJ 4870
题意：给定$n,p,k,r$，求
$$
\sum_{i=0}^{∞} C_{nk}^{ik+r}
$$

注意到$ik+r \mod k=r$，则我们考虑组合数的组合意义

从$nk$个物品中选 $\mod k=r$ 的个数的物品的方案数

那么设$dp(i,j)$为前 $i$ 个物品选择 $\mod k$ 为 $j$ 的方案数.
转移即
$$
dp(i,j)=dp(i-1,j)+dp(i-1,(j-1+k)\mod k)
$$

矩阵快速幂优化即可。