题目
Description
一个序列a1,…,an是合法的，当且仅当：
长度为给定的n。
a1,…,an都是[1,A]中的整数。
a1,…,an互不相等。
一个序列的值定义为它里面所有数的乘积，即a1a2…an。
求所有不同合法序列的值的和。
两个序列不同当且仅当他们任意一位不一样。
输出答案对一个数mod取余的结果。
Input
一行3个数，A，n，mod。意义为上面所说的。
Output
一行结果
Sample Input
9 7 10007
Sample Output
3611
HINT
数据规模和约定
0:A<=10,n<=10。
1..3:A<=1000,n<=20.
4..9:A<=10^9,n<=20
10..19:A<=10^9,n<=500。
全部:mod<=10^9,并且mod为素数，mod>A>n+1
题解
设$f_{i,j}$表示填到$i$，最大值不超过$j$的答案，有转移$f_{i,j}=ij\times f_{i-1,j-1}+f_{i,j-1}$
发现$A\le 10^9$，而这个玩意我感觉肯定不能用矩乘啥的优化
通过打表（并不）可以发现这个玩意是个最高次为$2n$的多项式
然后就可以用拉格朗日插值优化了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int N=1e3+5;
int n,A,mod,_N,ans;
int w[N];
int f[N][N];
int Pow(int a,int b)
{
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1) ans=1ll*ans*a%mod;
return ans;
}
int L(int x)
{
int ans=1;
for(int i=0;i<=_N;++i)
if(x!=i) ans=(1ll*ans*(A-i)%mod*(x-i<0?-1:1)*w[x-i<0?i-x:x-i]%mod+mod)%mod;
return ans;
}
int main()
{
scanf("%d%d%d",&A,&n,&mod),_N=n<<1;
for(int i=1;i<=_N;++i)
{
f[1][i]=f[1][i-1]+i;
if(f[1][i]>=mod) f[1][i]-=mod;
}
for(int i=1;i<=_N;++i)
for(int j=2;j<=n;++j)
{
f[j][i]=1ll*f[j-1][i-1]*i%mod*j%mod+f[j][i-1];
if(f[j][i]>=mod) f[j][i]-=mod;
}
if(A<=_N) return printf("%d",f[n][A]),0;
for(int i=1;i<=_N;++i)
w[i]=Pow(i,mod-2);
for(int i=0;i<=_N;++i)
{
ans+=1ll*f[n][i]*L(i)%mod;
if(ans>=mod) ans-=mod;
}
return printf("%d",ans),0;
}
