「PA 2020」Malowanie płotu 题解

算法思路

本题使用动态规划结合前缀和优化来解决栅栏涂色方案计数问题。核心思想是通过维护两个方向的DP数组和前缀和来高效计算满足连续性和相交性约束的方案数。

关键观察

1. 问题约束

• 每根木条的涂色段必须是连续的
• 相邻木条的涂色段必须有非空交集
• 每段要么全涂要么不涂

2. 状态设计

定义两个DP数组：

• $f[j]$：当前木条涂色段从某位置开始，到位置 $j$ 结束的方案数
• $g[j]$：当前木条涂色段从位置 $j$ 开始，到某位置结束的方案数

代码解析

初始化

for (int i = 1; i <= m; i++)
    f[i] = i, pre[i] = (pre[i - 1] + f[i]) % mod;

for (int i = m; i >= 1; i--)
    g[i] = m - i + 1, suf[i] = (suf[i + 1] + g[i]) % mod;

第一根木条：长度为 $j$ 的连续段有 $j$ 种选择（从不同位置开始）

动态规划转移

for (int i = 2; i <= n; i++) {
    int sum = 0;
    
    // 计算 f[j]：从左到右扫描
    for (int j = 1; j <= m; j++) {
        inc(sum, pre[j - 1]);
        f[j] = ((ll)mod - (ll)suf[j + 1] * j % mod + 
                (ll)pre[m] * j % mod + mod - sum) % mod;
    }
    
    sum = 0;
    
    // 计算 g[j]：从右到左扫描  
    for (int j = m; j >= 1; j--) {
        inc(sum, suf[j + 1]);
        g[j] = ((ll)mod - (ll)pre[j - 1] * (m - j + 1) % mod + 
                (ll)pre[m] * (m - j + 1) % mod + mod - sum) % mod;
    }
    
    // 更新前缀和
    for (int j = 1; j <= m; j++)
        pre[j] = (pre[j - 1] + f[j]) % mod;
        
    for (int j = m; j >= 1; j--)
        suf[j] = (suf[j + 1] + g[j]) % mod;
}

算法正确性

状态转移解释

对于第 $i$ 根木条的涂色段 $[l, r]$：

• 连续性约束：$l \leq r$
• 相交约束：必须与第 $i-1$ 根木条的涂色段有交集

转移公式通过容斥原理计算满足条件的方案数：

• $pre[m]$：前一根木条的所有方案
• $suf[j+1]$：前一根木条开始位置大于 $j$ 的方案
• $pre[j-1]$：前一根木条结束位置小于 $j$ 的方案

前缀和优化

• $pre[j]$：$f[1]$ 到 $f[j]$ 的前缀和
• $suf[j]$：$g[j]$ 到 $g[m]$ 的后缀和

复杂度分析

• 时间复杂度：$O(n \cdot m)$
• 空间复杂度：$O(m)$

由于 $n \cdot m \leq 10^7$，该复杂度是可接受的。

关键技巧

1. 双向DP：分别维护从左到右和从右到左的DP值
2. 前缀和优化：避免重复计算，将转移优化到 $O(1)$
3. 模运算处理：正确处理负数和取模
4. 容斥原理：通过加减法处理约束条件