A-等火车

输出即可。

B-数字游戏

容易证明第一次擦掉的是奇数，甲必败，否则甲必胜。

当第一次擦掉是奇数的时候，黑板上一个有个偶数，甲最多擦掉个偶数，所以乙必胜。

当第一次擦掉是偶数的时候，设为

那么把个整数分为

当乙擦掉一组中的某一个数的时候，甲把另一个擦掉。

最后只会剩下同一组的两个整数，它们互质，甲必胜。

所以答案输出

C-最大生成树

发现首先把和连边，然后至要不和连边，要不和连边。

容易证明这样的答案是最大的。

用存储即可。

D-求和

。

其中

考虑组合数意义，相当于从走到的方案数。

那么相当于从至这个矩阵中选择一个点，走到至中选择一个点，走过去的方案数。

然后就把所有起点，出来走到每一个终点的值，然后累加一下每一个矩阵的答案即可。

时间复杂度。

E-树

设表示从的深度。

那么

那么前部分可以直接计算。

后面两个部分，枚举。

也就是要计算的这样的数对个数，以及这些数对的。

设表示这颗子树的大小。

数对个数即为

设表示这颗子树的之和。

那么之和即为

时间复杂度。

F-字符串

可以转化为一个的矩阵，不能经过一条斜率为的线段的方案数。

那么把所有障碍点按照轴从大到小排序。

设表示从第个不能到达的点开始，不经过终点的方案数。

由于斜率为，所以。

设

把都看成一个多项式。

也就是。

那么直接多项式求逆即可。

最后

时间复杂度。

std:
a:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513174
b:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513176
c:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513178
d:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513180
e:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513183
f:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42513185