题解 P4708 【画画】
去年差不多这个时间弄出的题，感觉这道题还是比较有灵性的。自己写个题解。
先考虑一个辅助问题： n 个点的无标号图的个数 ans 。网上资料很多。直接套用 Burnside 引理，枚举点的置换（一种点的置换对应 ans * n! 种带标号方案的置换，这才是实际枚举的东西），可以将点划分为若干个循环节，考虑每个循环节内的点可以怎样连边，以及两个循环节间的点可以怎样连边。发现循环节大小的多重集合相同时，累加量一定，所以只需要枚举分拆方案，再乘上这个分拆方案对应的置换个数。
现在回到这个问题。同样的，我们枚举循环节的多重集合。
先考虑循环节内的连边：对大小为 2s+1 的循环节，有 s 种边可以连，一种边的连接会形成一个换，对点的度数的奇偶性不造成影响；对大小为 2s 的循环节，有 s-1 种边对点的度数的奇偶性不造成影响，一种边对循环节内所有点的奇偶性造成影响，这启发我们把一个循环节看做一个大点，对于 2s+1 的情况，有一次机会按它一下，把它的奇偶性改变。
再考虑循环节之间的连边，大小分别为 a、b 的两个循环节，有 (a, b) 种连边方案，每种连边方案总共连 ab/(a, b) 条边，对 a 中的每个点连 n1 = a/(a, b) 条，n2 = b/(a, b) 条。若 n1,n2 都是偶数，则不造成影响。若 n1 为奇数，n2 为偶数，相当于拥有了一次改变 a 奇偶性的机会。若 n1 为偶数，n2 为奇数，相当于拥有了一次改变 b 奇偶性的机会。若 n1 为奇数，n2 为奇数，则在 a, b 之间连上一条边，表示有一次机会将二者的奇偶性一同改变。
综上，我们可以建出一张图，点权最初全是 0 。对每个点，有 d[i] 次机会使其异或 1 ，对于一条边 e ，有 n[e] 次机会使两边异或 1 。问有多少种方案使得最终所有点的点权为 0 。
我们分连通块来考虑，然后累乘。设总共可以进行 p 次点操作，q 次边操作。这是一个经典问题：存在边操作能使点操作成立，当且仅当点操作的次数为偶数。可以直接构造 DFS 树，利用树形 DP 来证明可行性。至于必要性，因为每次边操作之后所有点的和的奇偶性不变。总之，就是在 p 次操作中选择偶数次的方案，乘上 2^q 。对于前者，等于 2^(p-1) ，因为考虑前 p-1 次操作任意，最后一次操作有且仅有一种方式对应。
突然觉得去年的自己很nb，可惜太浪了不认真训练，也不认真学字符串，我的集训队和THU就这样没了。