Atcoder Rugular Contest 115
D - Odd Degree
题意
给定一个图，询问满足度数为奇数的点的个数恰好为 $k(1\sim n)$ 的生成图数量。
其中生成图的定义为原图的点集 $+$ 原图的边集的子集。
题解
首先考虑图是树的情况，有结论：如果 $k$ 为奇数，显然生成图不存在；如果 $k$ 为偶数，则生成图数量为 ${n\choose k}$。
下面用数学归纳发证明：对所有 $n\ge 1$，任意指定树上 $k(2\mid k)$ 个点作为度数为奇数的结点则满足条件的生成图唯一：
$n=1$ 时只有 $k=0$ 的情况，显然生成图唯一。
下面考虑从 $n+1$ 个点的树上任意指定 $k(2\mid k)$ 个点作为度数为奇数的结点。
任取一个度数为 $1$ 的点，如果该点被指定为度数为奇数的点，则该点与树的连边一定保留。
考虑无视该点和该边，则等价于与该点相邻的另一个点在生成树中的奇偶性改变，于是有 $k'=k$ 或 $k'=k-2$。
如果该点被指定为度数为偶数的点，则该点与树的连边一定不保留，考虑无视该点和该边，于是有 $k'=k$。
然后等价于找 $n$ 个点中有 $k’$ 个点的生成图，根据数学归纳法，这是唯一的。
接下来考虑连通图的情况，假设图中有 $n$ 个点和 $m$ 条边，先确定一棵生成树。
对于非树边，有选于不选两种方案，同时非树边选与不选同时改变两个点的奇偶性。
当 $k$ 为偶数时，任意指定 $k$ 个点为度数为奇数的点，先考虑所有非树边选与不选对所有点奇偶性的影响，共 $2^{m-n+1}$ 种情况。
最后等价于构造图有 $k'$ 个点是度数为奇数的点的生成树的子图，此时方案数唯一。于是总方案数为 $2^{m-n+1}{n\choose k}$。
对于不连通图，考虑分治 $\text{NTT}$ 处理背包的合并，时间复杂度 $O(n\log^2 n)$。
E - LEQ and NEQ
题意
给定序列 $A$，求所有满足下列条件的序列 $X$ 数目：
- $1\le X_i\le A_i$
- $X_i \neq X_{i+1}$
题解
设 $\text{dp}(i,j)$ 表示满足限制条件且 $X_i=j$ 的序列 $X_{1\sim i}$ 的数目，$S_i=\sum_{j=1}^{A_i}\text{dp}(i,j)$。
于是对于 $j\le \min(A_i,A_{i+1})$，有 $\text{dp}(i+1,j)=S_i-\text{dp}(i,j)$。
如果 $A_i\lt A_{i+1}$，对于 $A_i\lt j\le A_{i+1}$，有 $\text{dp}(i+1,j)=S_i$。
于是维护一棵支持区间取负，区间加，区间赋值的线段树即可，时间复杂度 $O(n\log n)$。
