序列奇偶

题目描述：

有 $n$ 个数字，第 $i$ 个数字 $v_i$ 的范围在 $[x_i,y_i]$ ，有 $m$ 个限制，第 $i$ 个限制要求 $(\sum\limits_{i=l}^r v_i)\bmod 2=s$ 。

求有多少合法序列以及最小字典序合法序列。

$n\le 10,m\le 40,0\le x_i,y_i\le 10^9$ 。

暴力可以获得 $10\%$ 的分数。

我们发现 $m$ 个条件都与 $\bmod 2$ 有关，于是我们考虑之前确定每一个数字的奇偶性，并计算每一个数字为偶数的方案数 $a_{i,0}$ ，奇数的方案数 $a_{i,1}$ ，计算公式如下：

$$\begin{aligned} a_{i,1}&=\lfloor\frac{(y_i-x_i+1)+(x_i\bmod 2)}{2}\rfloor\\ a_{i,0}&=(y_i-x_i+1)-a_{i,1} \end{aligned}$$

于是原问题被转化为一个 $01$ 序列，要求一段区间的异或值为定值，求方案数和转化为原序列之后的最小字典序序列。

直接枚举可以获得 $50\%$ 的分数。

然后我们可以作一遍前缀异或和，记 $V_i=(\sum\limits_{j=1}^i v_j)\bmod 2$ 。

然后限制条件就变为 $V_{l_i-1}\oplus V_{r_i}=s_i$ 。这个时候我们可以考虑将 $l_i-1$ 向 $r_i$ 连边权值为 $s_i$ 。之后用带权并查集维护 $val_i$ 表示 $i$ 和 $i$ 所在集合的根的奇偶性相同/不同。

带权并查集：

如果设 $w_i$ 表示 $i$ 和并查集中 $i$ 的父亲 $f_i$ 的奇偶性的异或情况，那么 $val_i$ 应该为 $i$ 到根的边的异或值。

那么执行 $\text{getf}$ 函数时，设当前 $\text{getf}$ 的参数为 $x$ ，则应该有 $val_i=val_{f_i}\oplus w_i$ 。时时刻刻维护这个值就行。

实际实现时可以偷懒，因为合并时必然是 $x$ 和 $y$ 之间直接执行 $f_y=x$ ，所以我们可以把 $w$ 数组和 $val$ 数组合并为一个数组。

注意每次调用 $val_i$ 前要先用 $\text{getf}$ ，不然可能使用的是一个未更新的值。

int getf(int x){
    if(f[f[x]]==f[x])return f[x];
    int t=getf(f[x]);
    val[x]^=val[f[x]];
    return f[x]=t;
}

然后是合并函数 $\text{add(x,y,s)}$ 。

不妨设 $x,y$ 的根为 $rt_x,rt_y$ ，表示 $x$ 和 $y$ 的奇偶性的异或为 $s$ 。

首先如果说 $rt_x$ 和 $rt_y$ 不相等，此时只需要知晓 $rt_x$ 和 $rt_y$ 之间的关系就行。容易发现 $w_{rt_y}=s\oplus val_x\oplus val_y$ 。

然后就是 $rt_x$ 和 $rt_y$ 不相等。此时需要判断有没有矛盾出现。若 $val_x\oplus val_s$ 则没有矛盾，反之亦然。

void add(int x,int y,int S){
    int X=getf(x),Y=getf(y);
    if(X!=Y){
        val[Y]=S^val[x]^val[y];
        sz[X]+=sz[Y];
        f[Y]=X;
    }
    else{
        if(val[x]^val[y]^S)
            flag=1;
    }
}

此时如果出现了矛盾，可以直接判断出无解。

接着考虑如何计数。

注意到所有的点分为两类：

• 没有点与这个点有关系，这是自由点。
• 不是自由点，即连通块大小至少为 $2$ 。

注意到第一种完全独立，很好处理；第二种连通块的个数不超过 $\frac{n}{2}$ ，即 $20$ 。此时可以暴力枚举所有可能性，然后 DP 第一种即可。

具体的，设 $f_{i,j}$ 表示前 $i$ 个点， $V_i=j$ 。则：

• 若 $i$ 属于第一种，则枚举 $k$ ，有 $f_{i-1,k}\times a_{i,j\oplus k}\to f_{i,j}$ 。
• 否则，设 $i$ 必须选 $j$ ，则只能枚举 $k$ ，有 $f_{i-1,k}\times a_{i,j\oplus k}\to f_{i,j}$ 。且 $f_{i,j\oplus 1}=0$ 。

然后此时最终答案就是 $f_{n,0}+f_{n,1}$ ，边界条件 $f_{0,0}=1$ 。

第一问就做完了。

第二问比较简单。你可以从前往后贪心选择，容易发现每个点只会有两个选择，即 $x_i$ 和 $x_i+1$ 。

每次先选 $x_i$ ，然后使用带权并查集看是否有矛盾。如果有则 $x_i$ ，否则 $x_i+1$ 。

这样就做完了。

$50$ pts is very easy, I'll don't say anything.

Easily notice that we should used DSU to confirm if it is valid (solution exists).

So, as we all know 扩展并查集可用带权值替代。

Let $p_i$ as $i$ 的前缀异或的值，$f_i$ 为并查集的基础数组,目标数组为 $a_i$

若让 $S_i = \sum_{j=1}^{j=i}{a_j}$ $\mod 2$。

则 $S_i = S_{f_i}\ xor \ p_i$。

显然随便维护。

所以，不难发现，我们如果确定联通块的根，显然确定整个联通快。

Counting problem:

DP,DFS,calculate

如果直接决策孤立点，枚举其他的根。发现复杂度正确 $O(2^{\frac{n}{2}})$。

随后，计算非孤立点的值。

最后，DP即可。令 $dp_{i, j}$ 表示第 $i$ 个的 $S_i = j$的方案数。

转移显然，孤立点随便，非孤立点满足 $j = V_i$ 。

此时，注意当前 $a_i$ 的取值需要乘法一下。记录 $a_i$ 为奇数，$a_i$ 为偶数是简单的。区间多少个奇数/偶数

第一问做完。

第二问类似，反过来 DP, 再从前向后决策就行了。