题解：AT_abc208_f [ABC208F] Cumulative Sum

· · 题解

观察样例解释题。

我们把样例解释搬过来看看。

\begin{array}{c|ccccc} & m=0 & m=1 & m=2 & m=3 & m=4 \\ \hline n=0 & 0 & 0 & 0 & 0 & 0 \\ n=1 & 1 & 1 & 1 & 1 & 1 \\ n=2 & 4 & 5 & 6 & 7 & 8 \\ n=3 & 9 & 14 & 20 & 27 & 35 \\ \end{array}

我们观察到这个函数有一个非常重要的东西：

f(n,m) = f(n-1,m)+f(n,m-1)

所以，我们很自然地改写这个表格为：

\begin{array}{c|ccccc} & m=0 & m=1 & m=2 & m=3 & m=4 \\ \hline n=0 & 0 & 0 & 0 & 0 & 0 \\ n=1 & 1^k & \textcolor{red}{1} \times 1^k & \textcolor{red}{1} \times 1^k & \textcolor{red}{1} \times 1^k & \textcolor{red}{1} \times 1^k \\ n=2 & 2^k & \textcolor{red}{1} \times 1^k+ \textcolor{green}{1} \times 2^k & \textcolor{red}{2} \times 1^k+\textcolor{green}{1} \times 2^k & \textcolor{red}{3} \times 1^k+\textcolor{green}{1} \times 2^k & \textcolor{red}{4} \times 1^k+\textcolor{green}{1} \times 2^k \\ n=3 & 3^k & \textcolor{red}{1} \times 1^k+\textcolor{green}{1} \times 2^k+\textcolor{blue}{1} \times 3^k & \textcolor{red}{3} \times 1^k+\textcolor{green}{2} \times 2^k+\textcolor{blue}{1} \times 3^k & \textcolor{red}{6} \times 1^k+\textcolor{green}{3} \times 2^k+\textcolor{blue}{1} \times 3^k & \textcolor{red}{10} \times 1^k+\textcolor{green}{4} \times 2^k+\textcolor{blue}{1} \times 3^k \\ \end{array}

我们发现每个 i^k 的出现次数其实是一个高阶前缀和。

更加本质地，回想一下我们在提高组学的一个经典问题：

从 (0,0) 走到 (n,m)，每次只能向上或向右走一个单位，有多少种路径？

我们知道这个答案的封闭形式实际就是 \binom{n+m}{n}，并且其递推式恰好为

dp_{i,j} = dp_{i-1,j}+dp_{i,j-1}

也就是说，每一个数最终出现的次数，实际是一个路径计数的结果。

那么我们稍微推一下就会发现，数 i^k 在 f(n,m) 中的出现次数就是

\binom{n-i+m-1}{m-1}

那么最终的结果就是

\sum_{i=1}^n i^k \binom{n-i+m-1}{m-1}

无论如何，这个东西都是不好直接计算的。

于是我们引入多项式。

由于 n \leq 10^{18}，所以我们可以把这个玩意看做一个关于 n 的多项式。

具体地：

F(n) = \sum_{i=1}^n i^k \binom{n-i+m-1}{m-1}

这实际上是一个关于 n 的 (k+m) 次多项式。

为什么？

有一个基本事实是：若 S(n) 是一个关于 n 的 d 次多项式，那么 S(n)-S(n-1) 是一个关于 n 的 (d-1) 次多项式。

换句话说，如果 S(n)-S(n-1) 是一个关于 n 的 d 次多项式，那么 S(n) 是一个关于 n 的 (d+1) 次多项式。

对多项式暴力展开即可，读者自证不难。

由于 f(n,0) = n^k，所以 \deg_n f(n,0) = k。

而我们知道

f(n,m) - f(n-1,m) = f(n,m-1) \tag{*}

而且我们还知道

f(n,m) = \sum_{i=1}^n f(i,m-1) \tag{+}

由 (*) 式，我们从 m=1 开始取，就会发现这个东西的次数实际上是在每次升 1 的，而结合 (+) 式，我们知道，每做一次前缀和，其次数就升一次。其做了 m 次前缀和，初始还有 k 次，那么最终的次数就是 (k+m) 次。

那么我们只要求出 n \in [0,m+k] 处 F(n) 的取值，然后拉插就行了。

:::success[AC code]

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 2.5e6+32,M = 31,mod = 1e9+7;
long long n;
int m,k,f[N],y[N],fact[N],inv[N],pre[N];
inline int qpow(int base,int e){
    int res = 1;
    while(e){
        if(e&1){
            res = 1ll*res*base%mod;
        }
        base = 1ll*base*base%mod;
        e>>=1;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1;i<=m+k;++i){
        f[i] = qpow(i,k);
    }
    for(int i = 1;i<=m;++i){
        for(int j = 1;j<=m+k;++j){
            f[j] = (f[j]+f[j-1])%mod;
        }
    }
    for(int i = 1;i<=m+k;++i){
        y[i] = f[i];
    }
    fact[0] = 1;
    for(int i = 1;i<=m+k;++i){
        fact[i] = 1ll*fact[i-1]*i%mod;
    }
    inv[m+k] = qpow(fact[m+k],mod-2);
    for(int i = m+k-1;i>=0;--i){
        inv[i] = 1ll*inv[i+1]*(i+1)%mod;
    }
    n%=mod;
    if(n<=m+k){
        cout << y[n];
        return 0;
    }
    pre[0] = 1;
    for(int i = 0;i<=m+k;++i){
        pre[i+1] = 1ll*pre[i]*((n-i+mod)%mod)%mod;
    }
    int ans = 0,suf = 1;
    for(int i = m+k;i>=0;--i){
        int num = 1ll*pre[i]*suf%mod;
        int term = 1ll*y[i]*num%mod;
        term = 1ll*term*inv[i]%mod*inv[m+k-i]%mod;
        if((m+k-i)&1){
            ans = (ans-term+mod)%mod;
        }else{
            ans = (ans+term)%mod;
        }
        suf = 1ll*suf*((n-i+mod)%mod)%mod;
    }
    cout << ans;
    return 0;
}

:::