Description

一个序列a1,...,an是合法的，当且仅当：

长度为给定的n。

a1,...,an都是[1,A]中的整数。

a1,...,an互不相等。

一个序列的值定义为它里面所有数的乘积，即a1a2...an。

求所有不同合法序列的值的和。

两个序列不同当且仅当他们任意一位不一样。

输出答案对一个数mod取余的结果。

Solution

由于 \(f(A)\) 是一个关于 \(A\) 的 \(n\) 次多项式 .

知道 \(f[1]...f[2*n+1]\) 然后插值一下就行了.

\(f[1]...f[2*n+1]\) 可以 \(DP\) 求出 , 强制序列递增 , 最后乘以 \(n!\) 就行了.

#include
    
     using namespace std;const int N=1010;int A,n,m,mod,f[N][N],inv[N],Fac[N];int main(){  freopen("pp.in","r",stdin);  freopen("pp.out","w",stdout);  cin>>A>>n>>mod;  m=2*n+1;  for(int i=1;i<=m;i++)f[1][i]=i;  for(int i=2;i<=n;i++){      int sum=0;      for(int j=i-1;j<=m;j++){          f[i][j]=1ll*j*sum%mod;          sum=(sum+f[i-1][j])%mod;      }  }  inv[0]=inv[1]=Fac[0]=1;  for(int i=2;i<=m;i++)inv[i]=(mod-1ll*(mod/i)*inv[mod%i]%mod)%mod;  for(int i=1;i<=m;i++)Fac[i]=1ll*Fac[i-1]*i%mod;  for(int i=n;i<=m;i++)f[n][i]=1ll*f[n][i]*Fac[n]%mod;  for(int i=n;i<=m;i++)f[n][i]=(f[n][i]+f[n][i-1])%mod;  if(A<=m)cout<
     
      =j?inv[i-j]:-inv[j-i])%mod;      ans=(ans+1ll*f[n][i]*t)%mod;  }  cout<<(ans+mod)%mod;  return 0;}