【国家集训队】calc
foreverlasting
·
·
题解
题面
拉格朗日插值。
首先推出一个DP。
code：
```
//2018.10.11 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
res s=0;
bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return w?-s:s;
}
inline void _swap(res &x,res &y){
x^=y^=x^=y;
}
inline int _abs(const res &x){
return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
return x>y?x:y;
}
inline int _min(const res &x,const res &y){
return x<y?x:y;
}
const int N=5e2+10;
namespace MAIN{
int A,n,kcz;
int dp[N][N<<1];
int ans;
inline int qpow(res x,res y){
res ret=1;
while(y){
if(y&1)ret=1LL*ret*x%kcz;
y>>=1,x=1LL*x*x%kcz;
}
return ret%kcz;
}
inline void add(res &x,const res &y){
x+=y;
x>=kcz?x-=kcz:1;
x<0?x+=kcz:1;
}
inline int calc(const res &x){
res tmp=1,ret=0,p=((n<<1)&1)?kcz-1:1;
for(res i=1;i<=n<<1;i++)tmp=1LL*tmp*(x-i)%kcz*qpow(i,kcz-2)%kcz;
for(res i=0;i<=n<<1;i++,p=kcz-p)
add(ret,1LL*p*dp[n][i]%kcz*tmp%kcz),tmp=1LL*tmp*(x-i)%kcz*qpow(x-i-1,kcz-2)%kcz*((n<<1)-i)%kcz*qpow(i+1,kcz-2)%kcz;
return ret;
}
inline void MAIN(){
A=read(),n=read(),kcz=read();
for(res i=0;i<=n<<1;i++)dp[0][i]=1;
for(res i=1;i<=n;i++)
for(res j=1;j<=n<<1;j++)
dp[i][j]=(1LL*dp[i-1][j-1]*i*j%kcz+dp[i][j-1])%kcz;
if(A<=n<<1)printf("%d\n",dp[n][A]);
else printf("%d\n",calc(A));
}
}
int main(){
MAIN::MAIN();
return 0;
}
```