大意:不解释
思路:
首先方案数共有n！种，第1个点只有1种选择，第2个点2种选择，生成2个选择的同时消耗一个，第3个点则有3种选择，依次类推共有n!种方案，由于最后答案*n！，故输出的实际上是每种方案的总和。
由于枚举方案是不可行的，考虑枚举边，计算每一个点连向父亲的边的贡献，容易知道贡献为siz*(n-siz)，siz为子树大小。所以枚举点与siz即可。再考虑组成子树的形态，与子树外的形态。设当前枚举到i号点，子树大小为siz，则子树内不考虑编号有siz!种形态,考虑编号则有C(n-i,siz-1)种编号组合,则子树内共有siz!*C(n-i,siz-1)种方案；考虑子树外：由于已有i个点，这i个点可以有i！种方案,从第i+siz-1点开始由于以i为根的子树siz已确定，故这个点不能插入到以i为根的子树内，所以只有i-1种选择,这一部分贡献为(i-1)*(i)*(i+1)*……*(n-siz-1)，与前面的总和化简得i*(i-1)*(n-siz-1)!。则当前枚举的点i与siz对答案的贡献为siz*(n-siz)*i*(i-1)*(n-siz-1)!*C(n-i,siz-1)*siz!。预处理出组合和阶乘枚举点i和siz统计即可。时间复杂度O(n^2);
1 #include <iostream> 2 #include <cstdio> 3 #include <memory.h> 4 #define r(x) x=read() 5 #define MAXX 2005 6 #define MAX(a,b) (a>b?a:b) 7 #define MIN(a,b) (a<b?a:b) 8 using namespace std; 9 typedef long long ll; 10 ll read() 11 { 12 char ch=0;ll w=0,ff=1; 13 while(ch<'0'||ch>'9'){if(ch=='-')ff=-1;ch=getchar();} 14 while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();} 15 return ff*w; 16 } 17 ll P,n,fac[MAXX][MAXX],jie[MAXX],ans; 18 int main() 19 { 20 jie[0]=1ll; 21 r(n),r(P); 22 for(int i=0;i<=n;++i) 23 for(int j=0;j<=i;++j) 24 fac[i][j]=(j==0?1:(fac[i-1][j-1]+fac[i-1][j])%P); 25 for(int i=1;i<=2000;++i) jie[i]=jie[i-1]*i*1ll%P; 26 for(int i=2;i<=n;++i) 27 for(int sz=1;sz<=n-i+1;++sz) 28 ans=(ans+(sz*1ll*(n-sz)*1ll%P*jie[sz]%P*jie[n-sz-1]%P*i*(i-1)%P*fac[n-i][sz-1])%P)%P; 29 printf("%lld",ans%P); 30 return 0; 31 }