题目描述

一个序列 $a_1,\cdots,a_na1,⋯,an是合法的，当且仅当：$

长度为给定的

$a_1,\cdots,a_na1,⋯,an都是[1,A][1,A]中的整数。$

$a_1,\cdots,a_na1,⋯,an互不相等。$

一个序列的值定义为它里面所有数的乘积，即 $a_1\times a_2\times\cdots\times a_na1×a2×⋯×an。$

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

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

输出答案对一个数

题解

我们可以先统计出数值递增的贡献和，为贡献和*n!

设f[i][j]表示前i个数选的值都小于等于j的贡献和，转移为f[i][j]=f[i-1][j-]*j+f[i][j-1]

然后呢我们就可以暴力做拉格朗日插值法就好了

代码

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define ll long long  5 int a,n,mo,res,m,f[510][1010],y[1010]; 6 using namespace std; 7 int ksm(int a,int b) { int r=1; for (;b;b>>=1,a=1ll*a*a%mo) if (b&1) r=1ll*r*a%mo; return r; } 8 int change(int x) 9 {10     if (x>=1&&x<=m) return y[x];11     int r=0;12     for (int i=1;i<=m;i++)13     {14         int p=y[i],q=1;15         for (int j=1;j<=m;j++) if (i!=j) p=1ll*p*(x-j)%mo,q=1ll*q*(i-j)%mo;16         p<0?p+=mo:0,q<0?q+=mo:0,r=(r+1ll*p*ksm(q,mo-2))%mo;17     }18     return r;19 }20 int main()21 {22     scanf("%d%d%d",&a,&n,&mo),res=1,m=2*n+1;23     for (int i=1;i<=n;i++) res=1ll*res*i%mo;24     for (int i=0;i<=m;i++) f[0][i]=1;25     for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) f[i][j]=(1ll*f[i-1][j-1]*j+f[i][j-1])%mo;26     for (int i=1;i<=m;i++) y[i]=f[n][i];27     printf("%lld",1ll*res*change(a)%mo);     28 }