题解：AT_abc208_f [ABC208F] Cumulative Sum

· · 题解

这个形式很像网格行走，我们可以看成：在 (0, x) 位置拥有 x^k 的权值，这个权值会被贡献点到达 (n, m) 点的路径条数次数，也就是 \binom{n + m - 1 - x}{n - x}。

于是答案就是：

\sum\limits_{x = 1}^n x^k\binom{n+m - 1 - x}{m - 1}

试着用第二类斯特林数肘了肘，但是没肘动 ，化出来一个形式非常猎奇的东西。然后我就不会了。

对于一个很神秘的式子可以考虑拉插的！x^k 是一个关于 x 的 k 次多项式，(n + m - 1 - x)^{\underline{m - 1}} 是一个关于 x 的 (m - 1) 次多项式，乘起来就是 (k + m - 1) 次了，加上前缀和就是 O(k+m) 次。

容易 O(km) 求出此多项式在 1\sim (k+ m+1) 上的值，对着 n 插值即可。

特别的，因为这道题 m 可能为 0，所以要特判！

代码：

#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int N = 3e6, M = 30;
const int Mod = 1e9 + 7;;
int qpow(int n, int m) {
    int res = 1;
    while(m) {
        if(m & 1) res = 1ll * res * n % Mod;
        m >>= 1;
        n = 1ll * n * n % Mod;
    }
    return res;
}
int y[N + 10];
int fac[N + 10], invf[N + 10];
ll n; int m, qk;
void upd(int &x, int y) {
    x = ((x + y >= Mod) ? (x + y - Mod) : (x + y));
}
int C(int n, int m) {
    if(m > n) return 0;
    return 1ll * fac[n] * invf[m] % Mod * invf[n - m] % Mod;
}
int A(ll n, int m, ll del = -1) {
    ll res = 1;
    for(ll i = n; i >= max(0ll, n - m + 1); i--) {
        if(i != del) res = 1ll * res * (i % Mod) % Mod;
    }
    return res;
}
int premu[N + 10], sufmu[N + 10];
void fk(ll k, int n) {
    if(k <= n) {
        cout << y[k] << endl;
        return ;
    }
    premu[0] = 1; for(int i = 1; i <= n; i++) premu[i] = 1ll * premu[i - 1] * ((k - i) % Mod + Mod) % Mod;
    sufmu[n + 1] = 1; for(int i = n; i >= 1; i--) sufmu[i] = 1ll * sufmu[i + 1] * ((k - i) % Mod + Mod) % Mod;
    int sum = 0;
    for(int i = 1; i <= n; i++) {
        int t = 1ll * y[i] * premu[i - 1] % Mod * 1ll * sufmu[i + 1] % Mod;
        int tt = 1ll * invf[i - 1] * invf[n - i] % Mod;
        int ttt = (((n - i) % 2 == 0) ? 1 : (Mod - 1));
        upd(sum, 1ll * t * tt % Mod * 1ll * ttt % Mod);
    }
    cout << sum << endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> qk;
    fac[0] = 1; for(int i = 1; i <= N; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;
    invf[N] = qpow(fac[N], Mod - 2); for(int i = N - 1; i >= 0; i--) invf[i] = 1ll * invf[i + 1] * (i + 1) % Mod;

    if(!m) {
        cout << qpow(n % Mod, qk) << endl;
        return 0;
    }
    for(int i = 1; i <= qk + m + 1; i++)
        y[i] = 1ll * qpow(i, qk) * A(n + m - 1 - i, m - 1) % Mod * 1ll * invf[m - 1] % Mod;

    for(int i = 1; i <= qk + m + 1; i++)
        upd(y[i], y[i - 1]);
    fk(n, qk + m + 1);
}