[国家集训队] calc(动规+拉格朗日插值法)

题目

P4463 [国家集训队] calc
集训队的题目真是做不动呀(\%>\_<\%)

朴素方程

设(f_{i,j})为前(i)个数值域([1,j])，且序列递增的总贡献，则有：

[f_{i,j}=f_{i-1,j-1}*j+f{i,j-1} ]

由于递增序列可以全排列的：(ans=f_{n,A}×n!)
时间复杂度(O(nA))

证明一

设(f_{i,j})为关于(j)的(2i)次多项式，则(f_{i-1,j-1}*j)为关于(j)的2i-1次多项式，(f_{i,j-1})为关于(j)的(2i)次多项式

通过归纳法证明出(f_{i,j})为关于(j)的(2i)次多项式

证明二

设(f_{i,j})为关于(j)的(g(i))次多项式，变式：

[f_{i,j}-f(i,j-1)=f_{i-1,j-1}*j ]

则有(g(i)-1=g(i-1)+1longrightarrow g(i)=g(i-1)+2)，故(f_{i,j})为关于(j)的(2i)次多项式

具体做法

综上我们已经证明出了(f_{i,j})为关于(j)的(2i)次多项式，所以仅需(2i)项，通过拉格朗日插值法就能得出这个多项式的系数表示法，从而代入(j=A)求解即可

而((i,f_{n,i}))，就相当于多项式在坐标系上的一点，我们需要求出(2n+1)个点去确定多项式(k_0~k_{2n})这些系数

Code

#include<bits/stdc++.h>
typedef int LL;
const LL maxn=2e3;
LL A,n,mod,N;
LL y[maxn],f[maxn][maxn];
inline LL Pow(LL base,LL b){
	LL ret(1);
	while(b){
		if(b&1) ret=1ll*ret*base%mod; base=1ll*base*base%mod; b>>=1;
	}return ret;
}
inline LL Calc(LL x){
	LL ret(0);
	for(LL i=1;i<=N;++i){
		LL p(y[i]),q(1);
		for(LL j=1;j<=N;++j){
			if(j!=i){
				p=1ll*p*(x-j+mod)%mod;
				q=1ll*q*(i-j+mod)%mod;
			}
		}
		ret=(ret+1ll*p*Pow(q,mod-2)%mod)%mod;
	}
	return ret;
}
int main(){
	scanf("%d%d%d",&A,&n,&mod);
	N=(n<<1)+1;
	for(LL i=0;i<=N;++i) f[0][i]=1;
	for(LL i=1;i<=n;++i)
	    for(LL j=1;j<=N;++j)
	        f[i][j]=(1ll*f[i-1][j-1]*j%mod+f[i][j-1])%mod;
	LL C(1);
	for(LL i=2;i<=n;++i) C=1ll*C*i%mod;
	for(LL i=1;i<=N;++i) y[i]=f[n][i];
	if(A<=N)
		printf("%d",1ll*f[n][A]*C%mod);
	else
		printf("%d",1ll*Calc(A)*C%mod);
	return 0;
}