2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_7
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_7 [2020/08/03 23:15] gary |
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_7 [2020/08/04 19:18] (当前版本) grapelemonade [B] |
||
|---|---|---|---|
| 行 55: | 行 55: | ||
| 尽量选最大的吧 具体没太证 | 尽量选最大的吧 具体没太证 | ||
| - | <code> | + | <code cpp> |
| void work(int n,int m){ | void work(int n,int m){ | ||
| while(n&&m){ | while(n&&m){ | ||
| 行 96: | 行 96: | ||
| 直接数论分块即可。 | 直接数论分块即可。 | ||
| ===== I ===== | ===== I ===== | ||
| + | |||
| + | dp如代码所示，主要写下g数组怎么求 | ||
| + | |||
| + | 对于n个节点的无根树求$\sum d_i^2$ | ||
| + | |||
| + | 可以枚举数字在prufer序列出现的次数i，从n-2个节点中选出i个的方案为$C_{n-2}^i$，这i个位置全填1,2...n都是可行的，剩余的n-i-2个位置用剩下的n-1个数随便填满即可，方案数为${(n-1)}^{n-2-i}$ | ||
| + | |||
| + | 故$\sum d_i^2=C_{n-2}^i \times n \times {(n-1)}^{n-2-i} \times {(i+1)}^2$ | ||
| + | |||
| + | |||
| + | <code cpp> | ||
| + | for(int n=2;n<N;n++){ //n 无根树 value | ||
| + | for(int i=0;i<=n-2;i++) | ||
| + | (g[n]+=C(n-2,i)*n%M*(i+1)%M*(i+1)%M*poww(n-1,n-2-i))%=M; | ||
| + | } | ||
| + | for(int n=2;n<N;n++){ //n 无根森林 方案 | ||
| + | for(int i=1;i<=n;i++){ | ||
| + | (f[n]+=C(n-1,i-1)*poww(i,i-2)%M*f[n-i]%M)%=M; | ||
| + | } | ||
| + | } | ||
| + | for(int n=2;n<N;n++){ //n 无根森林 value | ||
| + | for(int i=1;i<=n;i++){ | ||
| + | (A[n]+=C(n-1,i-1)*((A[n-i]*poww(i,i-2)%M+f[n-i]*g[i]%M)%M)%M)%=M; | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| + | |||
| ===== J ===== | ===== J ===== | ||
| 行 186: | 行 213: | ||
| * A题可以打表，写C之前应该把A的暴力先调出来的（ | * A题可以打表，写C之前应该把A的暴力先调出来的（ | ||
| * 对板子不太熟悉了，C调了好久，赛后过题（ | * 对板子不太熟悉了，C调了好久，赛后过题（ | ||
| + | |||
| + | Gary: | ||
| + | |||
| + | * I题逆元求错了 （真的zz） | ||
| + | * 需要好好维护一下板子库 | ||
| + | |||
| + | |||
2020-2021/teams/mian/nowcoder_training/2020_multi-university_training_contest_7.1596467702.txt.gz · 最后更改: 2020/08/03 23:15 由 gary
