agc060 B – Unique XOR Path

题意：

在 \(n\times m\) 矩阵中，从左上角走到右下角，每一步只能向下或向右的路径用一个长为 \(n+m-2\) 的只含 \(D,R\) 两种字母的字符串 \(str\) 表示。给定整数 \(n, m, k\) 和串 \(str\)，问能否构造这样一个矩阵，矩阵的每个元素为 \([0,2^k-1]\) 中的整数，且 \(str\) 是从左上角走到右下角的唯一一条异或和为 \(0\) 的路径

\(1\le T\le 100, 2\le n, m \le 30, 1\le k\le 30\)

思路：

定义：若一个集合的元素都为 \([1,2^d-1]\) 间的整数，且其任一子集的异或和都不为 \(0\)，则该集合称为 “d好集”；元素最多的k好集称为 “最大d好集”

发现1.1：最大d好集的子集的异或和取遍 \([1,2^d-1]\)

解释：假设最大d好集 \(S\) 没有任何子集的异或和为某数 \(x\)，则 \(S\cup x\) 也是d好集，则 \(S\) 不是最大d好集

发现1.2：最大d好集 \(S\) 的不同子集 \(A,B\) 的异或和不同

解释：假设 \(A,B\) 的异或和相等，则 \((A-B)\cup (B-A)\in S\) 的异或和为 \(0\)，则 \(S\) 不是最大d好集

发现1.3：最大d好集的大小为 \(d\)

解释：由发现2.1和发现2.2，并注意到大小为 \(d\) 的集合有 \(2^d-1\) 个非空子集

发现2：只需考虑题中路径 \(str\) 上的数全为 \(0\) 的情况

解释：若存在某符合题意的矩阵 \(M\)，则对于路径 \(str\) 上的每个数 \(M_{i,j}=v\)，令 \(M_{i,j}\) 所在对角线（左下-右上对角线）上的每个数异或上 \(v\)，即 \(\forall i'+j'=i+j, M_{i',j'}\leftarrow M_{i',j'}\oplus v\)。这样处理以后所有路径的异或和不变，且路径 \(str\) 上的每个数全为 \(0\)

发现4：合法矩阵中不同正数的个数大于等于 “拐角数”

解释：记不相交拐角数为 \(d\)。考虑一个拐角RD，即下图中的路径 \(0\to 0\to 0\)

显然要求 \(x\neq 0\)，且所有这种 \(x\) 必须两两不同。进一步地，\(x\) 的取值集合 \(S\) 是一个d好集。理想情况下 \(S\) 应是一个最大k好集，可取 \(S=\{2^0,2^1,\cdots , 2^{k-1}\}\)

注意！形如RDR的路径只计一个拐角，因为在下图中

\(x\) 可以等于 \(y\)。因此拐角数为 \(s\) 中不相交的LR和RL子串的个数

发现5：存在一种构造方案，不同正数恰有拐角数个

解释：给每个拐角处的 \(x\) 位置赋值 \(2^0,2^1,\cdots ,2^{k-1}\)。若不相交拐角数大于 \(k\) 则没有答案。

矩阵被路径 \(str\) 分成两侧（即两个连通块）。对每个上述 \(x\)，把与 \(x\) 同侧且在 \(x\) 所属左下-右上的对角线上的位置全赋成 \(x\)

（也可以不仅赋单侧，即把 \(x\) 所属对角线上的全部位置赋成 \(x\)）

两个例子：

void sol() {
    int n, m, k; string s;
    cin >> n >> m >> k >> s;
    for(int i = 0; i + 1 < s.length(); i++)
        if(s[i] != s[i + 1]) k--, i++;
    cout << (k < 0 ? "No\n" : "Yes\n");
}