洛谷 P5591 题解

admin 2021-09-28 PM 50℃ 0条

题目链接

分析

首先 $p$ 和 $n$ 的范围都很大,拿斯特林数去拆自然数幂是没有意义的。

题目中要求的式子主要是 $\lfloor\dfrac{i}{k}\rfloor$ 不好处理。

有一个非常显然但是不容易想到的结论:

$$\lfloor\dfrac{i}{k}\rfloor=\sum_{j=0}^i[k|j]-1$$

而题目中的模数是 998244353,可以对 $[k|j]$ 作单位根反演。

$$ \begin{aligned} \sum_{i=0}^n\binom{n}{i}\times p^i\times\lfloor\dfrac{i}{k}\rfloor=&\sum_{i=0}^n\binom{n}{i}\times p^i\times(\sum_{j=0}^i[k|j]-1)\\ =&\sum_{i=0}^n\binom{n}{i}\times p^i\times\sum_{j=0}^i\dfrac{1}{k}\times\sum_{d=0}^{k-1}\omega_k^{dj}-\sum_{i=0}^n\binom{n}{i}\times p^i\\ =&\sum_{i=0}^n\binom{n}{i}\times p^i\times\sum_{j=0}^i\dfrac{1}{k}\times\sum_{d=0}^{k-1}\omega_k^{dj}-(p+1)^n\\ =&\dfrac{1}{k}\times\sum_{d=0}^{k-1}\sum_{i=0}^n\binom{n}{i}\times p^i\times\sum_{j=0}^i\omega_k^{dj}-(p+1)^n \end{aligned} $$

这里需要特判 $d=0$,公比为 1,不能等比数列求和:

$$ \begin{aligned} \sum_{i=0}^n\binom{n}{i}\times p^i\times(i+1)=&\sum_{i=0}^n\binom{n}{i}\times p^i\times i+\sum_{i=0}^n\binom{n}{i}\times p^i\\ =&\sum_{i=0}^n\binom{n-1}{i-1}\times p^i\times n+(p+1)^n\\ =&n\times p\times\sum_{i=0}^n\binom{n-1}{i-1}\times p^{i-1}+(p+1)^n\\ =&n\times p\times(p+1)^{n-1}+(p+1)^n \end{aligned} $$

当 $d>0$ 时,中间的部分可以等比数列求和:

$$ \begin{aligned} \sum_{i=0}^n\binom{n}{i}\times p^i\times\sum_{j=0}^i\omega_k^{dj}=&\sum_{i=0}^n\binom{n}{i}\times p^i\times\dfrac{\omega_k^{d(i+1)}-1}{\omega_k^d-1}\\ =&\dfrac{\sum_{i=0}^n\binom{n}{i}\times p^i\times(\omega_k^{d(i+1)}-1)}{\omega_k^d-1}\\ =&\dfrac{\sum_{i=0}^n\binom{n}{i}\times p^i\times\omega_k^{d(i+1)}-\sum_{i=0}^n\binom{n}{i}\times p^i}{\omega_k^d-1}\\ =&\dfrac{\omega_k^d\times\sum_{i=0}^n\binom{n}{i}\times (p\times\omega_k^d)^i-\sum_{i=0}^n\binom{n}{i}\times p^i}{\omega_k^d-1}\\ =&\dfrac{\omega_k^d\times(p\times\omega_k^d+1)^n-(p+1)^n}{\omega_k^d-1} \end{aligned} $$

带回原式即可。

解决

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int MOD = 998244353, G = 3;
int n, p, k;

int power(int x, int y = MOD - 2, int p = MOD)
{
    int ans = 1, base = x;
    while (y)
    {
        if (y & 1)
            ans = 1LL * ans * base % p;
        base = 1LL * base * base % p, y >>= 1;
    }
    return ans;
}

int main()
{
    cin >> n >> p >> k;
    int x = (p + 1) % MOD, ans = (1LL * n * p % MOD * power(x, n - 1) + power(x, n)) % MOD;
    for (int d = 1, t = power(G, (MOD - 1) / k), w = 1; d < k; d++)
    {
        w = 1LL * w * t % MOD;
        ans =
            (ans + 1LL * power(w - 1) * (1LL * w * power((1LL * p * w + 1) % MOD, n) % MOD - power(x, n) + MOD)) % MOD;
    }
    ans = (1LL * ans * power(k) % MOD - power(x, n) + MOD) % MOD;
    cout << ans << endl;
    return 0;
}
标签: none

非特殊说明,本博所有文章均为博主原创。

评论啦~