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=4,K=12,M=505;
ll dp[M][M],c[M];
int pw(int x,int k)
{
  int ret=1;while(k){if(k&1)ret*=x;x*=x;k>>=1;}return ret;
}
int main()
{
  dp[0][0]=1;
  for(int i=1;i<=K;i++)
    for(int j=1;j<=N;j++)
      dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*i*j;
  for(int i=N;i<=K;i++)c[i]=dp[i][N];
  int cnt=0,nw=N;
  while(c[K])
    {
      for(int i=K;i>=nw;i--)
    c[i]-=c[i-1]; c[nw-1]=0;
      for(int i=1;i<=K;i++)
    printf("%6lld ",c[i]); puts("");
      nw++; cnt++;
    }
  printf("cnt=%d\n",cnt);
  return 0;
}

以为值域<个数的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=505;
int n,A,mod,dp[N*3][N],ans;
int pw(int x,int k)
{
  int ret=1;while(k){if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;
}
int main()
{
  scanf("%d%d%d",&A,&n,&mod);
  int lm=n*3;
  for(int i=0;i<=lm;i++)dp[i][0]=1;///
  for(int i=1;i<=lm;i++)
    for(int j=1;j<=i&&j<=n;j++)
      dp[i][j]=(dp[i-1][j]+(ll)dp[i-1][j-1]*i%mod*j)%mod;
  if(A<=lm)
    {
      printf("%d\n",dp[A][n]);return 0;
    }
  int s0,s1;
  for(int i=n;i<=lm;i++)
    {
      s0=1; s1=1;//
      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-2)%mod*dp[i][n]%mod)%mod;
    }
  printf("%d\n",(ans+mod)%mod);
  return 0;
}