edu118
讲道理这场我的体验是挺魔幻的。
讲道理这应该是个简单场，然后被我玩出了4切，哈哈哈哈，不愧是我这个SB.
A写了能有5min我直接大受震撼。
B,C无感，写的慢是我SB。
D开到的时候你告诉我就6,7个人对？？此时 DEF 都只有6,7个人对。。。
然后发现这不SB dp?但是调了好久好久，伞兵样例 * 1
E开到时候也就100-人对？？？
然后一眼，这部伞兵bfs???但是调了好久，伞兵样例 * 2
F最后剩20min，看DX 7min切了，以为是性质题，，，
想了个容斥dp(\(\mathcal{O(n^2)}\))。
然后写了一遍，，就，，就过样例了？？？？？？交一法直接跑到了 pretest 13。。。。挺魔幻的，要是DE也这样就好了。。。
开始狂想性质，能不能根号。。然后卒。。。
最后 D因为 \(ret-1\) 没有取模导致
expected 998244352,Output -1惨案。
F发现dp了个寂寞，树上合并了个寂寞，都是生成函数直接乘法，我直呼自己SB，并且心中对那些粘板子的直接开骂。
挺魔幻的把，应该因为昨天太困了。。。。。
一个比较简短的做法就是，我们先把他们后面公共的0减去，然后看剩下那个\(10^k\) 的 \(k\) 是不是小于 6,如果是暴力，如果不是肯定是乘上了大。
这题铁伞兵。
给你互不相同的 \(n\) 个数，让你找出 n/2 个 互不相同 满足 \(x\in S,y\in S,x\bmod y \not \in S\)。
直接sort，然后输出 \(a_i\ \ \ a_1\) 原因显然。
直接binary serach 即可。。。。细节没啥。。。
被伞兵榜吓到了。。。。。
考虑 SG(a) = x，这个a还合法的情况只有俩。
- \([1,x-1]+\{x+1\}\)
- \([1,x-1]\)
然后直接套路转移 \(f(x)\) 表示前面选的子序列使得SG=x的方案数。
注意 case 1是转移不了了，他就憋死了。
所以开俩dp数组，有点细节需要考虑。
取模一定要取干净！
这题更是纯傻逼。
考虑最终状态，其实是个方程，如果 \((i,j)\) 能一步到达的地方最多有一个不能迫使他回去，那 \((i,j)\) 就能被迫使回去。。
然后，然后你发现这个直接bfs是，是对的。。。。。。
草了。
这个真说难度应该就是个 Easy+ 的。。。
首先，应该不难有容斥的想法。
然后发现我擦，这容斥了个马呀，现在就算容斥所形成的连通块连上了也屁事没有。
所以不难想到这个其实本质上就是要你对每一个 \(i\leq n\) 算随便选 \(i\) 个点，不存在俩有一个爹的方案数。
所以一个比较愚笨的dp出来了，（你要用dp std 就直接对你进行一个对SB的辱骂） \[ f_x(i)=\sum_{j\leq i} f_y(j)f_x(i-j) \] 很经典的树dp合并，然后最后你要 \(f_x(i)=f_x(i)+f_x(i-1)\) 因为你只可以在这个点连一条边，哈哈。
然后你发现woc，这他马不就是: \[ F_x=\prod_{x\rightarrow y} F_y\times(1+\text{son}\cdot x) \] 你会发现你dp了个寂寞，你只想要根的答案，所以根的答案就是 \(\prod(1+\text{son}\cdot x)\)。
然后，然后暴力卷，分治着卷，卷死他们！！！！！！