【题解】BZOJ 4870 [SHOI2017]组合数问题

Problem

$$ (\sum_{i=0}C_{nk}^{ik+r})\bmod p $$

Thought

观察式子，发现就是在 $nk$ 个物品中取模 $k$ 余 $r$ 个物品的方案数
那么就大力矩阵快速幂呗

值得注意的点：在计算初始矩阵考虑转移到下一位时要用加而不是赋值
因为可能会转移到自身

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n, p, k, r;
struct Matrix {
    int a[50][50];
    void clear() {memset(a, 0, sizeof(a));}
    int* operator [] (int pos) {
        return a[pos];
    }
    Matrix operator * (const Matrix x) const {
        Matrix ans; ans.clear();
        for(int i = 0; i < 50; ++ i)
            for(int j = 0; j < 50; ++ j)
                for(int k = 0; k < 50; ++ k) {
                    ans[i][j] += 1ll * a[i][k] * x.a[k][j] % p;
                    if(ans[i][j] >= p) ans[i][j] -= p;
                }
        return ans;
    }
}a;
Matrix qpow(Matrix a, ll b) {
    Matrix ans; ans.clear();
    for(int i = 0; i < 50; ++ i)
        ans[i][i] = 1;
    while(b) {
        if(b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}
int main() {
    n = read(); p = read(); k = read(); r = read();
    for(int i = 0; i < k; ++ i) {
        a[i][i] = 1;
        a[i][(i + 1) % k] += 1;
    }
    a = qpow(a, 1ll * n * k);
    printf("%d\n", a[0][r]);
    return 0;
}