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

· · 题解

题意

给定 n, p, r, k (1\le n\le 10^9, 0\le r<k\le 50, 2\le p\le 2^{30}-1)，求

\sum_{i\bmod k=r}{nk\choose i}\bmod p

题解

\begin{aligned}&\sum_{i\bmod k=r}{nk\choose i}\\=&\sum_{i\bmod k=r}[x^i](1+x)^{nk}\\=& [x^r]\left((1+x)^{nk}\bmod(x^k-1)\right)\end{aligned}

直接循环卷积快速幂，时间复杂度 O(k^2(\log n+\log k))。

代码

#include <bits/stdc++.h>
using namespace std;
int p, k;
vector<int> operator*(const vector<int> &lhs, const vector<int> &rhs) {
    vector<int> result(k);
    for (int i = 0; i < k; ++i)
        for (int j = 0; j < k; ++j)
            result[(i + j) % k] = (result[(i + j) % k] + 1LL * lhs[i] * rhs[j]) % p;
    return result;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r;
    cin >> n >> p >> k >> r;
    vector<int> a(k), ans(k);
    if (k == 1) {
        a[0] = 2 % p;
    } else {
        a[0] = a[1] = 1;
    }
    ans[0] = 1;
    auto e = 1LL * n * k;
    while (e > 0) {
        if (e & 1)
            ans = ans * a;
        a = a * a;
        e >>= 1;
    }
    cout << ans[r] << endl;
    return 0;
}