Cptraser/ 三月 17, 2019/ 2019.3/ 0 comments

构造多项式:

    \[\delta_j(x)=\prod_{i=0,i!=j}^n \frac{x-x_i}{x_j-x_i}\]

我们注意到一个很巧妙的性质:\delta_j(x_j)=1,且\delta_j(x_i)=0

然后构造出这个n次多项式。

    \[F(x)=\sum_{i=0}^n y_i\delta_i(x)\]

根据我们构造的多项式的性质:P(x_i)=y_i

x_i取值连续时:

    \[F(k)=\sum_{i=0}^n y_i\prod_{i!=j}\frac{k-j}{i-j}\ \ \ \ (1)\]

维护关于k的前缀积和后缀积:

    \[pre_i=\prod_{j=0}^i k-j\]

    \[suf_i=\prod_{j=i}^n k-j\]

我们还发现(1)\prod下面是一个阶乘的形式,然后带掉:

    \[F(k)=\sum_{i=0}^n y_i \frac{pre_{i-1} * suf_{i+1}}{Fac[i] * Fac[n-i]}\]

同时要注意分母的符号问题,当n-i为奇数时,分母取负号。

模板题

#include <cstdio>
using namespace std;

typedef long long LL;

const int Maxn=2e3+5,Mod=998244353;

LL Ans;
int N,K,x[Maxn],y[Maxn],l[Maxn];
int Ksm(int x,int y){int res=1;for(;y;y>>=1,x=(LL)x*x%Mod)if(y&1)res=(LL)res*x%Mod;return res;}

int main()
{
    scanf("%d%d",&N,&K);
    for(int i=1;i<=N;i++)scanf("%d%d",&x[i],&y[i]),l[i]=1;
    for(int i=1;i<=N;i++){
        int c1=1,c2=1;
        for(int j=1;j<=N;j++)if(i^j){
            c1=(LL)c1*(K-x[j]+Mod)%Mod;
            c2=(LL)c2*(x[i]-x[j]+Mod)%Mod;
        }
        (Ans+=(LL)y[i]*c1%Mod*Ksm(c2,Mod-2)%Mod)%=Mod;
    }
    printf("%lld\n",Ans);
}

[TJOI2018]教科书般的亵渎

题目大意:求\sum\sum i^{m+1}

题目的瓶颈在于求\sum i^k,看出这是一个k次多项式然后lagrange插一插就好了。

#include <cstdio>
#include <algorithm>
using namespace std;

const int Maxm=55,Mod=1e9+7;
typedef long long LL;
LL T,M,A[Maxm],x[Maxm],y[Maxm],N,Ans=0;

LL Ksm(LL x,LL y){x%=Mod;LL res=1;for(;y;y>>=1,x=x*x%Mod)if(y&1)res=res*x%Mod;return res;}
LL Lagrange(LL p){
    LL res=0;int n=M+3;p%=Mod;
    for(int i=1;i<=n;i++){
        int c1=1,c2=1;
        for(int j=1;j<=n;j++)if(i^j){
            c1=(LL)c1*(p-x[j]+Mod)%Mod;
            c2=(LL)c2*(x[i]-x[j]+Mod)%Mod;
        }
        (Ans+=(LL)y[i]*c1%Mod*Ksm(c2,Mod-2)%Mod)%=Mod;
    }return res;
}

int main()
{
    for(scanf("%lld",&T);T;T--){
        scanf("%lld%lld",&N,&M);LL tot=0;Ans=0;
        for(int i=1;i<=M;i++)scanf("%lld",&A[i]);
        sort(A+1,A+M+1);
        for(int i=1;i<=M+3;i++)x[i]=i,y[i]=((tot+=Ksm(i,M+1))%=Mod);
        for(int i=0;i<=M;i++){
            Ans+=Lagrange(N-A[i]);
            for(int j=i+1;j<=M;j++)Ans=(Ans-Ksm(A[j]-A[i],M+1)+Mod)%Mod;
        }printf("%lld\n",Ans);
    }
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*