2020-2021:teams:die_java:front_page_summertrain8

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:die_java:front_page_summertrain8 [2020/08/07 16:49]
fyhssgss [训练实况]
+++ 2020-2021:teams:die_java:front_page_summertrain8 [2020/08/20 10:56] (当前版本)
fyhssgss
@@ 行 1: / 行 1: @@
-====== title ======
+====== 2020牛客暑期多校训练营（第七场） ======
 [[https://ac.nowcoder.com/acm/contest/5672|比赛网址]]
@@ 行 149: / 行 149: @@
 }
+</code></hidden>
+===== I.Valuable Forests =====
+=== 题意 ===
+定义一个无根树的权值为所有点的度数的平方的和，求有标号的$n$个点形成的所有森林的权值的和。
+=== 题解 ===
+设$f[i]$表示$i$个带标号的节点有多少种不同的森林，递推式为$f[i]=\sum_{j=1}^i C_i^j*f[i-j]*j^{j-2}$。
+设$w[i]$表示$i$个点能形成的所有无根树的权值和,考虑每一个点以及不同的度数对答案的贡献，递推式子为：$w[i]=i*\sum_{d=1}^{i-1}d^2*C_{n-2}^{d-1}*(n-1)*(n-2-(d-1))$
+那么最终答案$ans[i]$就是$ans[i]=\sum_{j=1}^iC_i^j*(j^{j-2}*ans[i-j]+f[i-j]*w[i])$
+<hidden 代码><code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+#define mem(a,b) memset(a,b,sizeof(a))
+typedef long long LL;
+typedef pair<int,int> PII;
+#define X first
+#define Y second
+inline int read()
+{
+    int x=0,f=1;char c=getchar();
+    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
+    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
+    return x*f;
+}
+const int maxn=5010;
+int T;
+LL MOD,c[maxn][maxn],w[maxn],f[maxn],ans[maxn];
+LL quickpow(LL a,int N)
+{
+    if(N<=0)return 1;
+    LL res=1,tmp=a;
+    while(N)
+    {
+        if(N&1)res=(res*tmp)%MOD;
+        tmp=(tmp*tmp)%MOD;
+        N>>=1;
+    }
+    return res;
+}
+int main()
+{
+    T=read();MOD=read();
+    for(int i=0;i<=5000;i++)c[i][0]=1;
+    for(int i=1;i<=5000;i++)
+        for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
+    for(int i=3;i<=5000;i++)
+    {
+        w[i]=i;
+        for(int d=1;d<=(i-1);d++)w[i]=(w[i]*d*d%MOD*c[i-2][d-1]%MOD*quickpow(i-1,i-1-d))%MOD;
+    }
+    printf("here");
+    f[0]=1;f[1]=1;f[2]=2;
+    for(int i=3;i<=5000;i++)
+        for(int j=1;j<=i;j++)
+            f[i]=(f[i]+c[i][j]*f[i-j]%MOD*quickpow(j,j-2)%MOD)%MOD;
+    ans[1]=0;ans[2]=2;
+    for(int i=3;i<=5000;i++)
+        for(int j=1;j<=i;j++)
+            ans[i]=(ans[i]+c[i][j]*(quickpow(j,j-2)*ans[i-j]%MOD+f[i-j]*w[j]%MOD)%MOD)%MOD;
+    while(T--)printf("%lld\n",ans[read()]);
+    return 0;
+}
 </code></hidden>
 ===== 训练实况 =====

2020-2021/teams/die_java/front_page_summertrain8.1596790162.txt.gz · 最后更改: 2020/08/07 16:49 由 fyhssgss