2020-team11-C09
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2020-team11 返回]
== 概述 ==
solved: 5/13 dirt: 38%
rank: 5
== ==
== 总结 ==
开场Qza去看I，Zhw看A。然后Qza猜出了I的一部分结论，而Zhw已经在写A了。Zhw写A时TLE了一发并表示自己不会线性递推求逆元，而Qza口胡出一个奇怪但确实是O(n)的递推求逆元的方法，Qza遂上机把这个方法写了出来。而在Qza求逆元时，Zhw接着Qza的结论得到了化简方法。Qza写完逆元后样例过不去，遂换Zhw上来调。而Qza自己开始继续化简I，并得到了最初的结论。Zhw过掉A后Qza立刻上机写I，写完WA了一发并思考一会儿后，Zhw发现了问题所在，Qza对着原程序改了改便过掉了I。
然后Zhw去开L，Qza去开C。Qza发现C的模拟的思路后便上机开始乱搞。很遗憾一开始思路不清晰，没有写出来。冷静了一会儿后得到了较为好写的模拟方法。而此时Zhw想出了L的做法，边上机先写L。Qza在纸上写好了C的模拟代码，而Zhw的L卡了一会儿。Qza上机WA了一发C后，造出了卡掉自己的数据并发现了bug。改掉bug后交了一发PE（为什么会有格式错误这种玩意？），删掉末尾空格后就过了C。
Zhw和Qza讲了L的思路，Qza换了种思路还是得到了一样的结果，遂对照代码静态查错。然后发现Zhw有一次乘法没有取模，改掉后又PE了一发。删了末尾空格就过了L。
然后Qza去开G，Zhw开G和H。两人一起讨论得出了G的树形dp的做法，便由Qza写G，Zhw继续想H。Qza的G写挂掉后，Zhw有了H的做法，遂上机写。调通H后便一发AC了，而此时Qza的dp也基本在纸上成形。写完后WA了样例，调通后又交了一发WA，至比赛结束也没有找到问题所在。
== 题解 ==
A.根据点到面的距离公式可得h=|Ax+By+Cz+D|/sqrt(A^2+B^2+C^2) 所求答案1/h^2=(A^2+B^2+C^2)/D.令D=1,可得A=-1/a,B=-1/b,C=-1/c,即求1/a^2+1/b^2+1/c^2的期望。又因为a，b，c等价，所求答案即为3*1/a^2的期望。预处理sum1~n 1/i^2的总和，求期望即可。
B.
C. 按照题意模拟纸的对折情况，存每个位置对应线段的左端点、右端点、是否翻转、属于哪张纸，然后模拟对折即可。
D.
E.
F.
G. 还没调通。
H. 设dp[i][j]为执行了若干次删除之后，前i个已删除，还剩余j次删除机会的方案数。则dp[i+1][j-1]+=dp[i][j]*j，dp[i+1][j+k]+=dp[i][j]，分别为用前面i个删除剩余的删除机会删除i+1、新增一次删除删除掉i+1，并得到k次删除机会。对于第i个元素，它能够最终留下的方案对应的dp数组是确定的，因为删除的总次数是确定的，所以删除1~i-1后，i后面能够删除几个是确定的。假设后面还剩n-i=x个，要删除k个，则方案为dp[i-1][k]*C(x,k)*k!，如果1~i-1没有全部被删除，则枚举第一个没被删除的点为 j，j后面需要留下i这个位置不能删除，故答案为dp[j-1][k]*C(x-1,k)*k!。两个加起来就是i的答案。
I. 猜测横向对折和竖向对折相互独立，进一步发现向某个方向对折i次再从另一个方向剪，可以将纸剪为2^i^+1片，故枚举i从0到n，j=n-i，我们要求的就是Σ(2^i^+1)(2^j^+1)*C(n,i)*2^n^，除以4^n^即为期望。
J.
K.
L.考虑i元素的前面有x的元素，后面有y个元素，如果x<y，则i不可能留下。否则，y应被前面x中的某些元素删掉，则有C(x,y)y!种方案。剩余d=x-y个元素中，选d/2对对应关系即可。
M.[/wiki/2020-team11 返回]
概述
solved: 5/13 dirt: 38%
rank: 5
总结
开场Qza去看I，Zhw看A。然后Qza猜出了I的一部分结论，而Zhw已经在写A了。Zhw写A时TLE了一发并表示自己不会线性递推求逆元，而Qza口胡出一个奇怪但确实是O(n)的递推求逆元的方法，Qza遂上机把这个方法写了出来。而在Qza求逆元时，Zhw接着Qza的结论得到了化简方法。Qza写完逆元后样例过不去，遂换Zhw上来调。而Qza自己开始继续化简I，并得到了最初的结论。Zhw过掉A后Qza立刻上机写I，写完WA了一发并思考一会儿后，Zhw发现了问题所在，Qza对着原程序改了改便过掉了I。
然后Zhw去开L，Qza去开C。Qza发现C的模拟的思路后便上机开始乱搞。很遗憾一开始思路不清晰，没有写出来。冷静了一会儿后得到了较为好写的模拟方法。而此时Zhw想出了L的做法，边上机先写L。Qza在纸上写好了C的模拟代码，而Zhw的L卡了一会儿。Qza上机WA了一发C后，造出了卡掉自己的数据并发现了bug。改掉bug后交了一发PE（为什么会有格式错误这种玩意？），删掉末尾空格后就过了C。
Zhw和Qza讲了L的思路，Qza换了种思路还是得到了一样的结果，遂对照代码静态查错。然后发现Zhw有一次乘法没有取模，改掉后又PE了一发。删了末尾空格就过了L。
然后Qza去开G，Zhw开G和H。两人一起讨论得出了G的树形dp的做法，便由Qza写G，Zhw继续想H。Qza的G写挂掉后，Zhw有了H的做法，遂上机写。调通H后便一发AC了，而此时Qza的dp也基本在纸上成形。写完后WA了样例，调通后又交了一发WA，至比赛结束也没有找到问题所在。
题解
A.根据点到面的距离公式可得h=|Ax+By+Cz+D|/sqrt(A2+B2+C2) 所求答案1/h2=(A2+B2+C2)/D.令D=1,可得A=-1/a,B=-1/b,C=-1/c,即求1/a2+1/b2+1/c2的期望。又因为a，b，c等价，所求答案即为3*1/a2的期望。预处理sum1~n 1/i2的总和，求期望即可。
B.
C. 按照题意模拟纸的对折情况，存每个位置对应线段的左端点、右端点、是否翻转、属于哪张纸，然后模拟对折即可。
D.
E.
F.
G. 还没调通。
H. 设dp[i][j]为执行了若干次删除之后，前i个已删除，还剩余j次删除机会的方案数。则dp[i+1][j-1]+=dp[i][j]*j，dp[i+1][j+k]+=dp[i][j]，分别为用前面i个删除剩余的删除机会删除i+1、新增一次删除删除掉i+1，并得到k次删除机会。对于第i个元素，它能够最终留下的方案对应的dp数组是确定的，因为删除的总次数是确定的，所以删除1~i-1后，i后面能够删除几个是确定的。假设后面还剩n-i=x个，要删除k个，则方案为dp[i-1][k]*C(x,k)*k!，如果1~i-1没有全部被删除，则枚举第一个没被删除的点为 j，j后面需要留下i这个位置不能删除，故答案为dp[j-1][k]*C(x-1,k)*k!。两个加起来就是i的答案。
I. 猜测横向对折和竖向对折相互独立，进一步发现向某个方向对折i次再从另一个方向剪，可以将纸剪为2i+1片，故枚举i从0到n，j=n-i，我们要求的就是Σ(2i+1)(2j+1)*C(n,i)*2n，除以4n即为期望。
J.
K.
L.考虑i元素的前面有x的元素，后面有y个元素，如果x M.