# | Who | = | Penalty | A | B | C | D | E | F | G | H | I | J | Dirt |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 大吉大利,今晚吃 mian(); | 4 | 246 | + 01:03 | -4 | +1 00:07 | +1 00:37 | + 01:39 | 33% 2/6 |
Solved | A | B | C | D | E | F | G | H | I | J |
---|---|---|---|---|---|---|---|---|---|---|
Pantw | √ | √ | √ | |||||||
Withinlover | O | O | ||||||||
Gary | √ | O |
(√ for solved, O for upsolved, - for tried but not solved)
应当学学打表的新姿势了(
赛后过题 + 1
直接暴搜的复杂度太高了,然后就贪心的想最大值可能都是十分接近边界的点
于是想到按点到原点的距离排个序,只用前30个搜
然后愉快的WA了
后来改成40个过了(据说可以直接搜过去然而没有成功)
尽量选最大的吧 具体没太证
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; } } }
主要是1和3操作,2操作单独记一下就解决了
1操作可以转化到根节点上,但是会把根节点到被操作节点的整颗子树的答案算错。修正的方法是加一个等差数列,由于只会查询单点的值所以可以差分一下变成区间加法和单点查询。
本来想写 py,后来想一想直接猜只有 $n=1$ 和 $n=24$ 这两个解,就直接过了
这个题就是求
$$\sum\limits_{k=1}^{n}\left(2\lfloor\cfrac{n}{k}\rfloor+\left[n\bmod{k}\neq 0\right]\right)$$
直接数论分块即可。
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$
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; } }
直接按题意模拟即可。
ptw:
Withinlover:
Gary: