「SDOI2019」染色 题解

核心代码解析

1. 状态转移矩阵

inline void CalcG0() {
    // 定义5种状态间的转移关系
    g0[0][0] = 0, g0[0][1] = 1, g0[0][2] = 0, g0[0][3] = 2*(m-2), g0[0][4] = (m-2)*(m-3);
    g0[1][0] = 1, g0[1][1] = 0, g0[1][2] = 2*(m-2), g0[1][3] = 0, g0[1][4] = (m-2)*(m-3);
    g0[2][0] = 0, g0[2][1] = 1, g0[2][2] = (m-2), g0[2][3] = (m-3)+(m-2), g0[2][4] = (m-3)*(m-3);
    g0[3][0] = 1, g0[3][1] = 0, g0[3][2] = (m-3)+(m-2), g0[3][3] = (m-2), g0[3][4] = (m-3)*(m-3);
    g0[4][0] = 1, g0[4][1] = 1, g0[4][2] = 2*(m-3), g0[4][3] = 2*(m-3), g0[4][4] = ((m-4)*(m-4)+(m-3));
}

2. 动态规划转移

inline void CalcF(int i, int j) {
    static LL g[5];
    memset(g, 0, sizeof g), g[0] = 1;
    
    // 计算连续段的转移矩阵
    for (int k = i; k < j; k++)
        CalcG(g);
    
    // 根据当前列颜色情况更新状态
    if (!a[i][0] == !a[j][0]) {
        // 处理同侧有颜色的情况
        if (x0 == x1) {
            LL sum = F.QuerySum();
            F.ModifyAll((g[0]-g[2]+P)%P, sum*g[2]%P);
        } else {
            LL f0 = F.QueryNode(x1);
            LL sum = (F.QuerySum()-f0+P)%P;
            F.ModifyAll((g[2]-g[4]+P)%P, (sum*g[4]+f0*g[3])%P);
            F.ModifyNode(x0, (sum*g[3]+f0*g[1])%P);
        }
    }
}

3. 高效的状态维护

struct LCT {
    struct Vector {
        LL a, b, inv;  // 线性变换: f(x) = a*x + b
        Vector() : a(1), b(0), inv(1) {}
        Vector(LL _a, LL _b) : a(_a), b(_b), inv(Inv(_a)) {}
    };
    
    LL f[N], sum;
    Vector tag;
    int ti[N], nw;
    
    // 批量更新所有状态
    inline void ModifyAll(LL a, LL b) {
        if (a) tag *= Vector(a, b);
        else Clear(), tag.b = b;
    }
    
    // 查询单个颜色状态
    inline LL QueryNode(int x) {
        return ti[x] < nw ? tag.b : (f[x]*tag.a+tag.b)%P;
    }
};

算法思路

1. 状态定义：将相邻两列的颜色关系分为5种状态，通过矩阵描述状态转移
2. 分段处理：将网格按已染色列分段，每段内使用矩阵快速幂计算方案数
3. 线性变换：使用线性变换批量更新DP状态，避免逐个修改
4. 边界处理：特殊处理首尾段和单点染色情况

复杂度分析

• 时间复杂度：O(n + m)，线性处理每个段
• 空间复杂度：O(n + m)，存储网格状态和DP数组

该方法通过状态压缩和矩阵优化，高效解决了大规模网格染色计数问题。