CF622F The Sum of the k-th Powers

Tx_Lcy · 2022-12-05 15:21:37 · 题解

题目传送门

思路

别的题解说的很吓人，发一篇简单的题解造福后人。

首先观察样例，我们发现答案一定是个 k+1 次多项式，于是可以得到朴素做法，代 k+2 个点进去拉插，时间复杂度 \mathcal O(k^2)。

发现这个拉插是可以优化的。

我们先写出拉插的柿子：\sum_{i=0}^n y_i \prod_{j ≠ i} \dfrac{k-x_j}{x_i-x_j}。

如果我们钦定 x_i 为一段连续的 0 到 n 的值，那么柿子可以化为：\sum_{i=0}^n y_i \prod_{j ≠ i} \dfrac{k-j}{i-j}。

发现分子可以直接维护，就等于 \dfrac{\prod_{j=0}^n k-j}{k-i}，上面那个东西可以前缀后缀积维护。

至于分母，不难发现下面那个东西等价于 \prod_{j=0,j≠i}^n (i-j)，是 0 以上一段连续的区间和 0 以下的一段连续的区间的乘积，这个东西也可以直接前缀后缀积维护。

那么这道题就被你成功地水过了，时间复杂度 \mathcal O(n)。

码

//A tree without skin will surely die.
//A man without face will be alive
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e6+10;
int const mod=1e9+7;
int y[N],sum1[N],sum2[N],pre[N],suf[N];
inline int qpow(int a,int b){
    int ans=1;
    while (b){
        if (b&1) ans*=a,ans%=mod;
        a*=a,a%=mod,b>>=1;
    }
    return ans;
}
#define inv(x) (qpow(x,mod-2))
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,k;cin>>n>>k;
    for (int i=1;i<=k+2;++i) y[i]=y[i-1]+qpow(i,k),y[i]%=mod;
    sum1[0]=sum2[0]=1;
    for (int i=1;i<=k+2;++i) sum1[i]=sum1[i-1]*i%mod;
    for (int i=1;i<=k+2;++i) sum2[i]=-sum2[i-1]*i%mod;
    pre[0]=suf[k+3]=1;
    for (int i=1;i<=k+2;++i) pre[i]=pre[i-1]*(n-i)%mod;
    for (int i=k+2;i;--i) suf[i]=suf[i+1]*(n-i)%mod;
    int ans=0;
    for (int i=1;i<=k+2;++i){
        int fz=pre[i-1]*suf[i+1]%mod;
        int fm=sum1[i-1]*sum2[abs(k+2-i)]%mod;
        ans+=y[i]*fz%mod*inv(fm)%mod;
        ans%=mod;ans+=mod;ans%=mod;
    }
    cout<<ans<<'\n';
    return 0;
}