正题

题目链接:https://www.luogu.com.cn/problem/CF622F

题目大意

给出\(n,k\)，求

\[\sum_{i=1}^ni^k
\]

解题思路

很经典的拉格朗日差值问题

这个东西显然是可以化成一个\(k+1\)次的多项式的，所以我可以直接代\(k+2\)个点插出值来。看到顺眼先把\(n,k\)互换一下。

先上一个要刻在\(DNA\)里的公式

\[f(k)=\sum_{i=1}^ny_i\prod_{j=1,j\neq i}^n\frac{x_j-k}{x_i-x_j}
\]

发现这个直接计算是\(O(n^2)\)的搞不定。

上面的\(x_j-k\)挺好优化的，分别做一个前后缀积就好了，但是麻烦的是\(x_i-x_j\)。我们可以利用\(x_i\)是连续的这个性质，我们只需要带入\(x_i\in[1,n+2]\)的点即可。

此时\(x_i-x_j\)就变为了两段阶乘分别是\(\prod_{j=1}^{i-1}\frac{1}{i-j}\)和\(\prod_{j=i+1}^j\frac{1}{i-j}\)。预处理逆元前缀和就好了，需要注意的是因为后面那个式子\(i-j\)是负数所以我们需要判断一下如果\(n-i\)是奇数就要取反。

线性筛\(y_i\)的话时间复杂度\(O(n)\)，懒得话直接快速幂\(O(n\log k)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll N=1e6+10,P=1e9+7;

ll n,k,ans,inv[N],suf[N],pre[N];

ll power(ll x,ll b){

    ll ans=1;

    while(b){

        if(b&1)ans=ans*x%P;

        x=x*x%P;b>>=1;

    }

    return ans;

}

signed main()

{

    scanf("%lld%lld",&k,&n);

    // if(k<=n+2){

    //     for(ll i=1;i<=k;i++)

    //         ans=(ans+power(i,n))%P;

    //     printf("%d\n",ans);

    //     return 0;

    // }

    inv[1]=1;n+=2;

    for(ll i=2;i<=n;i++)

        inv[i]=P-(P/i)*inv[P%i]%P;

    inv[0]=1;

    for(ll i=1;i<=n;i++)

        inv[i]=inv[i-1]*inv[i]%P;

    ll tmp=1;pre[0]=suf[n+1]=1;

    for(ll i=1;i<=n;i++)pre[i]=pre[i-1]*(k-i)%P;

    for(ll i=n;i>=1;i--)suf[i]=suf[i+1]*(k-i)%P;

    for(ll i=1,p=0;i<=n;i++){

        (p+=power(i,n-2))%=P;

        ans+=p*pre[i-1]%P*suf[i+1]%P*inv[i-1]%P*(((n-i)&1)?P-inv[n-i]:inv[n-i])%P;

        ans=ans%P;

    }

    printf("%lld\n",(ans+P)%P);

    return 0;

}

巴特西

CF622F-The Sum of the k-th Powers【拉格朗日插值】

正题

题目大意

解题思路

code

最新文章

热门文章