P3746 [六省联考2017]组合数问题

考虑组合意义

有 nk 个物品，选 t 个，使得 t \equiv r \pmod{k}，求方案数。

随后可以容易得到 dp 方程，设 f_{i,j} 表示考虑到前 i 个物品，且选择的总物品数量膜 k 余 j。

则有 f_{i,j} = f_{i-1, j-1} + f_{i-1, j} 。

矩阵快速幂优化即可。

代码：

#include <bits/stdc++.h>
#define D fprintf(stderr, "Passed [%s] on line %d\n", __FUNCTION__, __LINE__)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

int n, mod, k, r;

int positive(int x, int modx) {
    return (x % modx + modx) % modx;
}

class Matrix {
public:
    vector<vector<int> > a;

    Matrix() { }
    Matrix(int n, int m) {
        a.resize(n);
        for(int i = 0; i < n; i++) {
            a[i].resize(m);
        }
    }
    Matrix(const vector<vector<int> > &_a) : a(_a) { }

    Matrix mul(Matrix b) {
        Matrix res;
        res.a.resize(a.size());
        for(int i = 0; i < (int) a.size(); i++) {
            for(int j = 0; j < (int) b.a[i].size(); j++) {
                int val = 0;
                for(int k = 0; k < (int) a[i].size(); k++) {
                    val += a[i][k] * b.a[k][j] % mod;
                    val %= mod;
                }
                res.a[i].push_back(val);
            }
        }
        return res;
    }

    Matrix I(int n) {
        vector<vector<int> > _a; _a.resize(n);
        for(int i = 0; i < n; i++) {
            _a[i].resize(n);
            _a[i][i] = 1;
        }
        return Matrix(_a);
    }

    Matrix qpow(int b) {
        Matrix base(a), res = I(a.size());
        while(b) {
            if(b & 1) res = res.mul(base);
            base = base.mul(base); b >>= 1;
        }
        return res;
    }

    void print() {
        for(auto it1 : a) {
            for(auto it2 : it1) {
                cout << it2 << " ";
            }
            cout << endl;
        }
    }
};

signed main() {
    n = rd(), mod = rd(), k = rd(), r = rd();
    Matrix f(1, k), trans(k, k);
    for(int i = 0; i < k; i++) {
        trans.a[i][i] += 1; trans.a[i][positive(i - 1, k)] += 1;
    }

    f.a[0][0] = 1;
    f = f.mul(trans.qpow(n * k));
    cout << f.a[0][r] << endl;
    return 0;
}