2020-team8-1211

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(standings.png,1000px)]]
[[Image(submissions.png,1000px)]]
== 流水账 ==
开场看到B，szy表示这题有个很好写的写法,让cy上机写，Ebola和szy机下想D和F，cy1h过了B，ebola推出了D积分的式子，上机写发现精度炸了，再一观察，发现答案就是4n-1/3，改了一下过了，三个人一起想F，最后szy决定去爆搜一发，第一发T了，cy加了个记忆化过了，之后szy想出了c，很好写，cy调了调精度过了，之后szy又想出了I，cy上机也过了，G和H都处于不会的状态，最后Ebola上机敲H的快速插值尝试挣扎一下，可惜快速插值太慢了.

== 个人总结 ==


== 题解 ==

A:

B:动态虚树，树的大小是dfs序相邻节点距离再加上第一个和最后一个距离除以二 

C:先推一波式子，发现贡献跟每个点度有关，先把确定度的点贡献算完，然后不确定的点是等价的，所以期望度就是平均值.

D:4n-1/3不会证明

E:

F:爆搜，记忆化

G:考虑L到R的答案实际上就是L到R的对原根取对数的值的gcd再和p-1取gcd，再用p-1除以这个数，注意gcd(al,al+1,..,ar,p-1)=gcd(gcd(al,p-1),(al+1-al,p-1),gcd(al+2-al+1,p-1)...(ar-ar-1,p-1)),每个数和p-1的gcd可以分解质因数之后两个log计算，计算方法大概是寻找每个数的模P意义下最小循环节，可以对每一个质因数独立考虑，如果p^k不是循环节，那么p^(k+1)也不可能是，考虑完后乘起来即可，最后再用p-1除以这个数即可，因(x*u)%(p-1)=0,u最小为(p-1)/gcd(x,p-1).

H:推式子FFT

I:卢卡斯定理转化成p进制，发现每一位贡献独立的，乘起来就可以了

J:

K:

L:

流水账

开场看到B，szy表示这题有个很好写的写法,让cy上机写，Ebola和szy机下想D和F，cy1h过了B，ebola推出了D积分的式子，上机写发现精度炸了，再一观察，发现答案就是4n-1/3，改了一下过了，三个人一起想F，最后szy决定去爆搜一发，第一发T了，cy加了个记忆化过了，之后szy想出了c，很好写，cy调了调精度过了，之后szy又想出了I，cy上机也过了，G和H都处于不会的状态，最后Ebola上机敲H的快速插值尝试挣扎一下，可惜快速插值太慢了.

个人总结

题解

A:

B:动态虚树，树的大小是dfs序相邻节点距离再加上第一个和最后一个距离除以二

C:先推一波式子，发现贡献跟每个点度有关，先把确定度的点贡献算完，然后不确定的点是等价的，所以期望度就是平均值.

D:4n-1/3不会证明

E:

F:爆搜，记忆化

G:考虑L到R的答案实际上就是L到R的对原根取对数的值的gcd再和p-1取gcd，再用p-1除以这个数，注意gcd(al,al+1,..,ar,p-1)=gcd(gcd(al,p-1),(al+1-al,p-1),gcd(al+2-al+1,p-1)...(ar-ar-1,p-1)),每个数和p-1的gcd可以分解质因数之后两个log计算，计算方法大概是寻找每个数的模P意义下最小循环节，可以对每一个质因数独立考虑，如果pk不是循环节，那么p(k+1)也不可能是，考虑完后乘起来即可，最后再用p-1除以这个数即可，因(x*u)%(p-1)=0,u最小为(p-1)/gcd(x,p-1).

H:推式子FFT

I:卢卡斯定理转化成p进制，发现每一位贡献独立的，乘起来就可以了

J:

K:

L:

附加文件