bzoj 2655 calc——拉格朗日插值

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

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

先考虑DP。dp[ i ][ j ]表示值域为 i 、选 j 个值的答案，则 dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i-1 ][ j-1] * i * j 。两项分别表示一定不选/一定选第 i 个值。

因为答案是值域大、个数小，所以考虑只看 dp[ ][ n ] ，即把值域看成自变量。

不知怎么知道这个式子的次数是 2*n 。尝试用做几遍差分看什么时候数列都为0的方法来看，但得出应该是 2*n - 2 次才对呀……

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=,K=,M=;

ll dp[M][M],c[M];

int pw(int x,int k)

{

  int ret=;while(k){if(k&)ret*=x;x*=x;k>>=;}return ret;

}

int main()

{

  dp[][]=;

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

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

      dp[i][j]=dp[i-][j]+dp[i-][j-]*i*j;

  for(int i=N;i<=K;i++)c[i]=dp[i][N];

  int cnt=,nw=N;

  while(c[K])

    {

      for(int i=K;i>=nw;i--)

    c[i]-=c[i-]; c[nw-]=;

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

    printf("%6lld ",c[i]); puts("");

      nw++; cnt++;

    }

  printf("cnt=%d\n",cnt);

  return ;

}

打表观察

以为值域<个数的dp无意义，于是选择 n~3*n 这 2*n+1 个值。但其实值域<个数的也能用。

注意 x[ i ] - x[ j ] 有负数，最后(答案+mod)%mod。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=;

int n,A,mod,dp[N*][N],ans;

int pw(int x,int k)

{

  int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;

}

int main()

{

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

  int lm=n*;

  for(int i=;i<=lm;i++)dp[i][]=;///

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

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

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

  if(A<=lm)

    {

      printf("%d\n",dp[A][n]);return ;

    }

  int s0,s1;

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

    {

      s0=; s1=;//////

      for(int j=n;j<=lm;j++)

    {

      if(j==i)continue;

      s0=(ll)s0*(A-j)%mod;  s1=(ll)s1*(i-j)%mod;

    }

      ans=(ans+(ll)s0*pw(s1,mod-)%mod*dp[i][n]%mod)%mod;

    }

  printf("%d\n",(ans+mod)%mod);

  return ;

}

相关文章