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/01 21:56] withinlover [A] |
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_7 [2020/08/04 19:18] (当前版本) grapelemonade [B] |
||
|---|---|---|---|
| 行 52: | 行 52: | ||
| 后来改成40个过了（据说可以直接搜过去然而没有成功） | 后来改成40个过了（据说可以直接搜过去然而没有成功） | ||
| ===== B ===== | ===== B ===== | ||
| + | |||
| + | 尽量选最大的吧 具体没太证 | ||
| + | |||
| + | <code cpp> | ||
| + | void work(int n,int m){ | ||
| + | while(n&&m){ | ||
| + | if(n<m) swap(n,m); | ||
| + | if(n%m==0){ | ||
| + | for(int i=1;i<=n;i++) tmp[++cnt]=m; | ||
| + | n-=n; | ||
| + | } | ||
| + | else{ | ||
| + | for(int i=1;i<=m;i++) tmp[++cnt]=m; | ||
| + | n-=m; | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| + | |||
| ===== C ===== | ===== C ===== | ||
| + | |||
| + | 主要是1和3操作，2操作单独记一下就解决了 | ||
| + | |||
| + | 1操作可以转化到根节点上，但是会把根节点到被操作节点的整颗子树的答案算错。修正的方法是加一个等差数列，由于只会查询单点的值所以可以差分一下变成区间加法和单点查询。 | ||
| + | |||
| ===== D ===== | ===== D ===== | ||
| 行 72: | 行 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 ===== | ||
| 行 162: | 行 213: | ||
| * A题可以打表，写C之前应该把A的暴力先调出来的（ | * A题可以打表，写C之前应该把A的暴力先调出来的（ | ||
| * 对板子不太熟悉了，C调了好久，赛后过题（ | * 对板子不太熟悉了，C调了好久，赛后过题（ | ||
| + | |||
| + | Gary: | ||
| + | |||
| + | * I题逆元求错了 （真的zz） | ||
| + | * 需要好好维护一下板子库 | ||
| + | |||
| + | |||
2020-2021/teams/mian/nowcoder_training/2020_multi-university_training_contest_7.1596290161.txt.gz · 最后更改: 2020/08/01 21:56 由 withinlover
