传送门
题意简述：问有多少数列满足如下条件：
- 所有数在[1,A][1,A][1,A]之间。
- 没有相同的数
- 数列长度为nnn
一个数列的贡献是所有数之积，问所有满足条件的数列的贡献之和。
A≤1e9,n≤500A\le1e9,n\le500A≤1e9,n≤500
思路：
肯定不能枚举所有情况。
我们先规定这个数列满足a1<a2<⋅˙⋅⋅<ana_1<a_2<\dot\cdot\cdot\cdot<a_na1<a2<⋅˙⋅⋅<an，最后答案乘上n!n!n!即可。
现在转化一下问题：
就是求f(x)=∏i=1A(1+ix)f(x)=\prod_{i=1}^A(1+ix)f(x)=∏i=1A(1+ix)这个多项式的xnx^nxn的系数是多少。
考虑定义状态fi,jf_{i,j}fi,j表示多项式∏k=1i(1+kx)\prod_{k=1}^i(1+kx)∏k=1i(1+kx)这个多项式xjx^jxj的系数。
于是有下面的转移：
fi,j=ifi−1,j−1+fi−1,jf_{i,j}=if_{i-1,j-1}+f_{i-1,j}fi,j=ifi−1,j−1+fi−1,j 可以暴力走一波了
然后把后面一项展开变成：
fi,j=ifi−1,j−1+(i−1)fi−2,j−1+fi−2,j=⋅˙⋅⋅=∑k=0i−1(k+1)fk,j−1f_{i,j}=if_{i-1,j-1}+(i-1)f_{i-2,j-1}+f_{i-2,j}=\dot\cdot\cdot\cdot=\sum_{k=0}^{i-1}(k+1)f_{k,j-1}fi,j=ifi−1,j−1+(i−1)fi−2,j−1+fi−2,j=⋅˙⋅⋅=∑k=0i−1(k+1)fk,j−1
这说明fi,jf_{i,j}fi,j可以等于一个多项式。
相当于对于一个矩阵的某一行集体乘上一个数，然后用前缀和去更新当前状态。
于是f∗,jf_{*,j}f∗,j对应多项式的最高次数等于f∗,j−1f_{*,j-1}f∗,j−1对应多项式的最高次数+2+2+2，这样递推下去f∗,jf_{*,j}f∗,j对应多项式的最高次数是2j2j2j。
这样我们知道了fn,kf_{n,k}fn,k对应的多项式次数是2k2k2k，于是先暴力dpdpdp出f1→2k+1,kf_{1\rightarrow 2k+1,k}f1→2k+1,k的值，然后用拉格朗日插值算出第nnn项即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1005;
int A,f[N][N],inv[N],n,k,mod,ans=0;
typedef long long ll;
inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(const int&a,const int&b){return a>=b?a-b:a-b+mod;}
inline int mul(const int&a,const int&b){return (ll)a*b%mod;}
int main(){
scanf("%d%d%d",&A,&n,&mod);
int lim=n*2+1;
inv[1]=1;
for(ri i=2;i<=lim;++i)inv[i]=mul(inv[mod-mod/i*i],mod-mod/i);
f[0][0]=1;
for(ri i=1;i<=lim;++i){
f[i][0]=1;
for(ri j=1;j<=n;++j)f[i][j]=add(f[i-1][j],mul(f[i-1][j-1],i));
}
for(ri mult,i=1;i<=lim;++i){
mult=f[i][n];
for(ri j=1;j<=lim;++j)if(i^j)mult=mul(mult,dec(A,j)),mult=mul(mult,(i>j?inv[i-j]:mod-inv[j-i]));
ans=add(ans,mult);
}
for(ri i=1;i<=n;++i)ans=mul(ans,i);
cout<<ans;
return 0;
}