十三联测 #7
B
已知有一棵树，有 \(n-1\) 次操作，每次操作之前没有操作过的点 \(x\)：
新建节点 \(x+n\)，并扫描原树上与 \(x\) 连接的点 \(j\)，若存在 \((j+n, x)\) 的边就删掉，换成 \((j+n,x+n)\)。
否则，加入 \((x+n,j)\) 这条边。每次操作完询问生成树的个数。
\(n\le 5000\)。
非常难一道题。首先生成树个数是不能用矩阵树定理算了，考虑挖掘图的性质。
相当于有两棵树，有若干个 \(j\) 连接着 \(x\) 和 \(x+n\)。
先考虑 \(x\) 形成连通块的情况，我们称原树和新树上的不连接 \(j\) 的叫做红边，连接 \(j\) 的叫蓝边。
红边和蓝边都是成对的。先考虑保留全部红边的情况，那么蓝边有且仅有一对没有被删成一条。
考虑删某对红边中的一条，那么会形成两个连通块，于是每个连通块都需要删一对蓝边中的一条。
直接将其放到一棵树上考虑，也就是删红边所形成的连通块中每个都需要保留一对蓝边，这个可以 dp。
考虑 \(x\) 不形成连通块呢？事实上还是一样的，每个连通块分别 dp 即可。
考虑设 \(f_u,g_u\) 表示当前子树内所在连通块存在/不存在保留的一对蓝边的方案数，简单 dp。
C
给出序列 \(a\)，你可以使其所有数取模某个数进行若干次，问最后不同的序列有多少种。\(n,a_i\le 500\)。
我们先考虑 \(a_i=i\) 的情况，设我们取模的数是 \(x\)，需要满足 \(x_{i}>x_{i+1}\)。
考虑 \(x\) 从小到大加入查看其变化：
\(x=3\) 时，\(a=012,012...\)，\(x=5\) 时，\(a=01201,01201...\)，\(x=7\) 时，\(a=0120101,0120101,...\)。
每次操作也就是也就是令周期改为 \(x\)，且把第 \(x\) 位设为 \(0\)。所以我们断言 \(a\) 可以如此构造出来：
存在一个正整数 \(x\)，对于 \(i\in [0,x)\) 都有 \(a_i=i\) 且 \(a_x=0\)；
对于 \(i>x\)，有 \(a_i<x\)，且 \(a_i=0\) 或 \(a_i=a_{i-1}+1\)。这里的 \(x\) 指的是最后一次取模的数。
所以我们枚举 \(x\) 来计数即可。可以记录 \(f_{i,j}\) 表示前 \(i\) 位合法且 \(a_i=j\) 的方案数。
现在考虑普通情况，还是考虑枚举 \(x\)，但是可能会算重复，不算重的话要钦定 \(x-1\) 出现即可。