[国家集训队] 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)+1\longrightarrow 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;

}