洛谷 P6620 题解

admin 2021-09-28 AM 34℃ 0条

题目链接

分析

单项式和组合数看起来非常的不搭,所以考虑转下降幂,设

$$ \begin{aligned} f(k)=&\sum_{i=0}^ma_i\times k^i\\ =&\sum_{i=0}^mb_i\times k^{i\over} \end{aligned} $$

则:

$$ \begin{aligned} f(k)=&\sum_{i=0}^ma_i\times k^i\\ =&\sum_{i=0}^ma_i\times\sum_{j=1}^i\begin{Bmatrix}i\\j\end{Bmatrix}\times k^{j\over} \end{aligned} $$

故有

$$b_i=\sum_{j=i}^ma_j\times\begin{Bmatrix}j\\i\end{Bmatrix}$$

将下降幂多项式带入要求的式子:

$$\sum_{k=0}^nf(k)\times x^k\times\binom{n}{k}=\sum_{k=0}^n\sum_{i=0}^mb_i\times k^{i\over}\times\binom{n}{k}\times x^k$$

又因为

$$ \begin{aligned} k^{i\over}\times\binom{n}{k}=&\dfrac{k!}{(k-i)!}\times\dfrac{n!}{k!(n-k)!}\\ =&\dfrac{n!}{(k-i)!(n-k)!}\\ =&\dfrac{n!(n-i)!}{(k-i)!(n-k)!(n-i)!}\\ =&\dfrac{n!}{(n-i)!}\times\dfrac{(n-i)!}{(k-i)!(n-k)!}\\ =&n^{i\over}\times\binom{n-i}{k-i} \end{aligned} $$

所以,

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

式子推完了。

$O(m^2)$ 递推出斯特林数,$O(m^2)$ 求 $b$,$O(m\log n)$ 计算答案,总时间复杂度 $O(m^2)$。

瓶颈在多项式转下降幂。

解决

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

using namespace std;

const int _ = 1005;
int n, x, p, m, a[_], b[_], S2[_][_];

int power(int x, int y)
{
    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 >> x >> p >> m;
    for (int i = 0; i <= m; i++)
        cin >> a[i];
    S2[0][0] = 1 % p;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            S2[i][j] = (S2[i - 1][j - 1] + 1LL * S2[i - 1][j] * j) % p;
    for (int i = 0; i <= m; i++)
        for (int j = i; j <= m; j++)
            b[i] = (b[i] + 1LL * a[j] * S2[j][i]) % p;
    int ans = 0;
    for (int i = 0, ppk = 1; i <= m; i++)
    {
        ans = (ans + 1LL * b[i] * ppk % p * power(x, i) % p * power(x + 1, n - i)) % p;
        ppk = 1LL * ppk * (n - i) % p;
    }
    cout << ans << endl;
    return 0;
}

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

上一篇 CF 97E 题解
下一篇 洛谷 P5591 题解

评论啦~