Educational Codeforces Round 114 (Rated for Div. 2) E. Coloring T11 D43

[传送门]( Problem - E - Codeforces (Unofficial mirror site, accelerated for Chinese users) )

思路

（思路借鉴牛客群犇

观察到： 若第一行为 11000 或 1010110 这种有连续的两个 1 或 0 的串，那么下一行只能与上一行取反，状态是确定的；若为 101010 或 010101 这种01间隔的串，下一行的串可以与之相等或相反

先考虑第一种情况,下一行与上一行取相反，那么我们把所有行压缩到两行，看这两行的状态，对于某一列：

1. 若这列有两个连续的1或0，则这种情况是无解的。
2. 若这列没有确定的 1和0，则这列是*的（即可以选择 010101或101010这样排列）
3. 否则这列就是固定的

那么答案就是 \(2^{*列个数}\)。

考虑第二种情况，101010，下一行有两种状态，相反的状态上面以求得，只考虑相同的状态，相同的状态相当于把行列颠倒，计算相反的状态。

最后两种结果的出来的答案加起来再减去重复的个数。

考虑重复的个数，对于二维矩阵，只有$\begin{matrix}
0&1\
1&0\
\end{matrix} 和 \begin{matrix}
1&0\
0&1\
\end{matrix} $这两种会出现重复情况，那么扩展后会发现，重复情况只会取 {0，1，2} 三种情况。

自己实现非常乱。

下面参考代码为 Heltion 的代码，代码太精致优美了，做详细注释 //代码太妙了，膜拜

参考代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int maxn = 1000000 + 1;
constexpr LL mod = 998244353;
LL pw[maxn];
struct {
    int c[3];
    // c[0]表示不合法的数量
    // c[1]表示固定列的数量
    // c[2]表示*列的数量
    int s[maxn][2];
    //s 表示把这一列的状态压缩到两行
    // 考虑 s[x]
    // 若s[x][0]和s[x][1] 都有值，说明压缩的列中有连续相同的数字，不合法
    // 其中有一个有值，是固定列
    // 都无值，是*列
    void erase(int x, int y, int z) {
    	
        c[not s[x][0] + not s[x][1]] -= 1; 
        s[x][(y ^ z) & 1] -= 1; //状态数量 -1
        c[not s[x][0] + not s[x][1]] += 1; 
        //上面一种状态转移到下面一种状态
       
    }
    void insert(int x, int y, int z) {
    	
        c[not s[x][0] + not s[x][1]] -= 1;
        s[x][(y ^ z) & 1] += 1;
        c[not s[x][0] + not s[x][1]] += 1;
        //同上
    }
    LL ans() {
        return c[0] ? 0 : pw[c[2]];
    }
    void init(int n) {
        c[2] = n;
    }
}R, C;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    //map保存每个点的状态
    map<pair<int, int>, int> mp;
    //计算 2的次方
    for (int i = 0; i < maxn; i += 1) pw[i] = i ? pw[i - 1] * 2 % mod : 1;
    int n, m, k;
    cin >> n >> m >> k;
    R.init(n); //初始化*列/行的个数
    C.init(m);
    int c[2] = {}; //记录重复的值
    // c[0]表示1010这种情况出现过没有
    // c[1]表示0101这种情况出现过没有
    for (int i = 0; i < k; i += 1) {
        int x, y, z;
        cin >> x >> y >> z;
        if (mp.count({x, y})) {//若之前被赋值了，先删去
            
            c[(x ^ y ^ mp[{x, y}]) & 1] -= 1;
            R.erase(x, y, mp[{x, y}]);
            C.erase(y, x, mp[{x, y}]);
            mp.erase({x, y});
        }
        if (z != -1) {
            //关于 (x ^ y ^ z) & 1  考虑一行
            //若是 101010  则值为 1 1 1 1 1 1 对应为c[1]=5,c[0]=0;
            //表示有一种情况出现了，重复值为 1 下面同理
            //若是 010101  则值为 0 0 0 0 0 0 重复值为 1
            //若是 110010  则值为 1 0 0 1 1 1 重复值为 0
            c[(x ^ y ^ z) & 1] += 1;
            R.insert(x, y, z);
            C.insert(y, x, z);
            mp[{x, y}] = z;
        }
        //c[1]和c[2]都等于0 ，说明矩阵中没有已填充数字，重复值为2
        //有一个>0,另一个等于0 ，重复值为1
        //两个都>0，说明矩阵中有连续相同的数字，重复值为0
        cout << (R.ans() + C.ans() + mod - not c[0] - not c[1]) % mod << "\n";
    }
    return 0;
}