自动搬运

查看原文

来自洛谷，原作者为

	jiangly 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:52:17，当前版本为作者最后更新于2019-12-11 21:37:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意

给定 $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;
}