题解 P6667 【[清华集训2016] 如何优雅地求和】

· · 题解

更好的阅读体验

众所周知这题可以用斯特林数 m^2 求，但是要快速插值斯特林数等一堆东西估计过不了。

令 f(x) = \sum\limits_{i = 0}^{m} \binom{x}{i} s_i。\binom{x}{i} 是 i 次多项式，因此存在这样的 s 。

二项式反演：f(x) = \sum\limits_{i = 0}^{x} \binom{x}{i} s_i \Leftrightarrow s_x = \sum\limits_{i = 0}^{x} \binom{x}{i} (-1)^{x - i} f(i)

通过卷积可以快速得到 s 数组。

通过这个我们可以快速得到一个点的点值。

（知道这个这题就不难了）

推式子：

\sum\limits_{k = 0}^{n} \sum\limits_{i = 0}^{m}s_i \binom{k}{i} \binom{n}{k} x^k (1 - x)^{n - k} \sum\limits_{k = 0}^{n} \sum\limits_{i = 0}^{m}s_i \binom{k}{i} \binom{n}{k} x^k (1 - x)^{n - k} \sum\limits_{k = 0}^{n} \sum\limits_{i = 0}^{m} s_i \binom{n}{i} \binom{n - i}{k - i} x^k (1 - x)^{n - k} \sum\limits_{i = 0}^{m} s_i \binom{n}{i} \sum\limits_{k = i}^{n} \binom{n - i}{k - i} x^k (1 - x)^{n - k} \sum\limits_{i = 0}^{m} s_i \binom{n}{i} \sum\limits_{k = 0}^{n - i} \binom{n - i}{k} x^{k + i} (1 - x)^{n - k - i} \sum\limits_{i = 0}^{m} s_i \binom{n}{i} x^i \sum\limits_{k = 0}^{n - i} \binom{n - i}{k} x^{k} (1 - x)^{n - i - k} \sum\limits_{i = 0}^{m} s_i \binom{n}{i} x^i (x + 1 - x)^{n - i} \sum\limits_{i = 0}^{m} s_i \binom{n}{i} x^i

这样就可以很方便地做了。

时间复杂度 \Theta(m \log m)

代码：

int fac[N], ifac[N];
void minit(int x) {
    fac[0] = 1;
    L(i, 1, x) fac[i] = (ll) fac[i - 1] * i % mod;
    ifac[x] = qpow(fac[x]);
    R(i, x, 1) ifac[i - 1] = (ll) ifac[i] * i % mod;
}
int fpow(int x) {
    return x % 2 == 0 ? 1 : mod - 1;
}
int n, m, x, f[N], g[N], s[N], ans;
int main() {
    n = read(), m = read(), x = read();
    minit(m), init(m << 1);
    L(i, 0, m) f[i] = (ll) ifac[i] * fpow(i) % mod;
    L(i, 0, m) g[i] = (ll) ifac[i] * read() % mod;
    Mul(f, g, s, m + 1, m + 1);
    L(i, 0, m) s[i] = (ll) s[i] * fac[i] % mod;
    int now = 1;
    L(i, 0, m) (ans += (ll) now * s[i] % mod * ifac[i] % mod) %= mod, now = (ll) now * x % mod * (n - i) % mod;
    cout << ans << endl;
    return 0;
}

祝大家学习愉快！