T2打了个6维的数位DP直接求了所有萌数.....我说为啥你们的比我快这么多
by lichangdongtw @ 2016-11-13 21:47:35
T2懒得想了，直接上分块打表拿60……
by Desire丶 @ 2016-11-13 21:49:48
留名
by huhuhuhaha @ 2016-11-13 21:55:41
补充t3出题人题解：
设f[u->v]表示u、v之间有边的情况下，从u到v的期望距离。考虑从u出发第一步走到哪里可以列出方程f[u->v]=1/d[u]+sum{(1+f[k->u]+f[u->v])/d[u]}(u、k之间有边且k!=v)，d[u]表示u的度数。解方程得f[u->v]=d[u]+sum{f[k->u]}(u、k之间有边且k!=v)。把f[k->u]一层层代入，可得f[u->v]=sum{d[i]}(i在以v为根时u的子树内)。考虑每条边被计算了多少次，化简得f[u->v]=2siz[v][u]-1，siz[v][u]表示以v为根时u的子树大小。只需要计算出所有的siz[1][i]，那么判断一下u和v谁是父亲就可以O(1)的计算出siz[v][u]，进而计算出f[u->v]。
接下来考虑如何计算答案。因为期望的线性性，路径长度的期望等于每条边长度期望的和，所以考虑每条边在多少条路径中出现过，即可得出一条有向边u->v对答案的贡献是siz[v][u]\*siz[u][v]\*f[u->v]/n/n。对每条边各计算一次即可，时间复杂度O(n)。
by kkksc03 @ 2016-11-13 21:58:31
T2要怎么对一个1000位的数取余？该不会是用高精度罢（喷水）
by PVYCVJ @ 2016-11-13 22:12:11
我是初学数位DP的蒟蒻，T2快搞死我了，求代码
by zx2003 @ 2017-01-24 15:10:05
@[Created\_equal1](/space/show?uid=3182)
by zx2003 @ 2017-01-24 15:10:51