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|比赛网址]] | [[https://ac.nowcoder.com/acm/contest/5672|比赛网址]] | ||
| 行 150: | 行 150: | ||
| </code></hidden> | </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> | ||
| + | ===== 训练实况 ===== | ||
| + | 0~1:40 过三题 之后垃圾时间 | ||
| ===== 训练总结 ===== | ===== 训练总结 ===== | ||
2020-2021/teams/die_java/front_page_summertrain8.1596790143.txt.gz · 最后更改: 2020/08/07 16:49 由 fyhssgss
