bzoj 2655 calc —— 拉格朗日插值

时间：2023-03-09 17:00:10
bzoj 2655 calc —— 拉格朗日插值

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2655

先设 f[i][j] 表示长度为 i 的序列，范围是 1~j 的答案；

则 f[i][j] = f[i-1][j-1] * i * j + f[i][j-1]，分别是选不选 j，选 j 的话放在哪个位置；

看不出次数...据说这是个最高次数为 2i 的多项式，感性理解...

知道了次数，就可以用拉格朗日插值算了，DP得到比较小的 2*n+1 个值，即可算出 x=A 的答案。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=;

int n,A,mod,f[xn][xn<<],yy[xn<<];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

int pw(ll a,int b)

{

  ll ret=;

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

    if(b&)ret=(ret*a)%mod;

  return ret;

}

int main()

{

  A=rd(); n=rd(); mod=rd(); int m=*n+;

  //  f[0][0]=1;

  for(int j=;j<=m;j++)f[][j]=;//!!!

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

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

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

  if(A<=m){printf("%d\n",f[n][A]); return ;}

  for(int i=;i<=m;i++)yy[i]=f[n][i];

  ll ans=;

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

    {

      ll s1=,s2=;

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

    {

      if(i==j)continue;

      s1=(s1*(A-j)%mod+mod)%mod;//

      s2=(s2*(i-j)%mod+mod)%mod;//

    }

      ans=(ans+s1*pw(s2,mod-)%mod*yy[i]%mod)%mod;

    }

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

  return ;

}

相关文章