bzoj千题计划269：bzoj2655: calc (拉格朗日插值）

http://www.lydsy.com/JudgeOnline/problem.php?id=2655

f[i][j] 表示[1,i]里选严格递增的j个数，序列值之和

那么ans=f[A][n] *  n!

A太大，那么用拉格朗日插值法

f[i][j] 是关于i的2j次多项式，证明如下：

%%%rqy

#include<cstdio>

using namespace std;

int mod;

int f[][];

int x[],y[],tot;

int Pow(int a,int b)

{

    int res=;

    for(;b;a=1LL*a*a%mod,b>>=)

        if(b&) res=1LL*res*a%mod;

    return res;

}

int Langrange(int n)

{

    int fz=;

    for(int i=;i<=tot;++i) fz=1LL*fz*(n-x[i])%mod;

    int fm; int ans=;

    for(int i=;i<=tot;++i)

    {

        fm=n-x[i];

        for(int j=;j<=tot;++j)

            if(i!=j) fm=1LL*fm*(x[i]-x[j])%mod;

        ans=(ans+1LL*fz*y[i]%mod*Pow(fm,mod-)%mod)%mod;

    }

    if(ans<) ans+=mod;

    return ans;

}

int main()

{

    int A,n;

    scanf("%d%d%d",&A,&n,&mod);

    f[][]=;

    int m=*n+;

    f[][]=;

    for(int i=;i<=m;++i)

    {

        f[i][]=;

        for(int j=;j<=i;++j)

            f[i][j]=(1LL*f[i-][j-]*i%mod+f[i-][j])%mod;

    }

    for(int i=;i<=m && tot<*n+;++i)

        if(f[i][n] && i!=A) x[++tot]=i,y[tot]=f[i][n];

    int fac=;

    for(int i=;i<=n;++i) fac=1LL*fac*i%mod;

    printf("%d",1LL*Langrange(A)*fac%mod);

}