题目链接
题解
\[ans = \sum\limits_{i = 0}^{\infty}{nk \choose ik + r} \pmod p\]
发现实际是求
\[ans = \sum\limits_{i = 0}^{\infty}{nk \choose i}[i \mod k = r] \pmod p\] 设
\(f[i][j]\)表示
\(i\)个数选出
\(x \mod k = j\)个数的方案数
利用组合数递推 + 矩乘转移即可
#include #include #include #include #include #include #include #include #include