P9400 「DBOI」Round 1 三班不一般 做题笔记

题目链接

最近搬运一些洛谷上的题解到这里来，一是增加我的博文数量，二是缓解一下我的博客园冷清的气氛。

我的做法和题解里的做法不一样，麻烦了许多。

首先看到连续的几盏灯刺眼就不行了，当然能够想到动态规划，设 $f[i][j]$ 为看到第 $i$ 个宿舍，末尾有连续 $j$ 个灯刺眼，且前面的灯都合法的方案数。

当前这盏灯，可以刺眼也可以不刺眼，刺眼：

$f[i][j]=f[i - 1][j - 1]\times\text{当前灯刺眼的方案数}$。

不刺眼的话，前面再多连续的刺眼都废了，所以：

$f[i][0] = (f[i - 1][1] + f[i - 2][2] + \cdots + f[i - 1][a - 1]) \times \text{当前灯不刺眼的方案数}$。

然后就能得到 $O(n^2)$ 的做法了：

#include <iostream>
#define int long long
using namespace std;
int n, a, b;
int l[200005], r[200005];
int f[1005][1005];//前 i 盏，末尾有连续 j 盏刺眼 
const int mod = 998244353;
int fun (int x, int y, int z) {
    if (y <= z) return 0;
    if (x <= z) return y - z;
    return y - x + 1;
}
int fun_ (int x, int y, int z) {//x 到 y 中小于等于 z 的数的个数 
    if (x > z) return 0;
    return min (y, z) - x + 1;
}
signed main () {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i ++) cin >> l[i] >> r[i];
    if (a == n + 1) {
        long long ans = 1;
        for (int i = 1; i <= n; i ++) {
            ans *= long (r[i] - l[i] + 1);
            ans %= mod;
        }
        cout << ans << "\n";
    } else if (a == 1) {
        long long ans = 1;
        for (int i = 1; i <= n; i ++) {
            if (l[i] > b) ans = 0;
            else ans *= long (min (r[i], b) - l[i] + 1);
            ans %= mod;
        }
        cout << ans << "\n";
    } else {
        long long ans = 0;
        f[0][0] = 1;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j < a; j ++) {
                f[i][j] = f[i - 1][j - 1] * fun (l[i], r[i], b) % mod;
            }
            for (int j = 0; j < a; j ++) {
                f[i][0] += f[i - 1][j];
                if (f[i][0] > mod) f[i][0] -= mod;
            }
            f[i][0] = f[i][0] * fun_ (l[i], r[i], b) % mod;
        }
        for (int i = 0; i < a; i ++) ans = (ans + dp[n][i]) % mod;
        cout << ans << "\n";
    }
    return 0;
}

接着来考虑怎么优化呢？我试了半天，这个东西不能用斜率，不能用四边形不等式，好像没啥好优化的，这时就要转换状态了。

根据正难则反的经典套路，我们再设 $F[i]$ 为到第 $i$ 个宿舍，刺眼的方案数，就发现可以了。

为了不重复的统计每一个刺眼的方案，如果一个方案有多个连续的 $a$ 盏刺眼的灯，它只会被第一个连续 $a$ 个刺眼的灯来统计。

所以：$F[i] = F[i - 1] \times \text{当前这个灯乱填(前面已经不满足了加上这个也不满足)}$

$+\text{最近 a 个全部刺眼的方案数}\times \text{第 i - a 个不刺眼的方案数 (或者第 i - a 个是 0 号宿舍)}\times \text{(i - a - 1 以及再之前的灯都不刺眼的方案数)}$。

乱搞的方案数显然是 $r[i] - l[i] + 1$，后面呢？

最近 $a$ 个灯全部刺眼和第 $a - 1$ 个灯不刺眼也好弄，而 $i-a-1$ 以及前面的灯都不刺眼的方案数，其实就是 $f[i - a - 1]$。

$f$ 怎么求呢？根据刚刚的正难则反，显然 $f$ 等于全部乱填减去不合法的方案数。

状态转移方程：

$f[i] = luangao[i] - F[i]$

$F[i] = F[i - 1] \times (r[i] - l[i] + 1) + ciyan[i] \times inv (ciyan[i - a] \times buciyan (l[i - a], r[i - a], a) \times f[i - a - 1])$，其中 $buciyan (l, r, k)$ 求的是 $l$ $r$ 中有多少数小于等于 $k$。

其实把 $f$ 的方程带回 $F$ 更简单了，可以自己试下。

初始化细节很多，大家仔细看下。状态转移方程较麻烦，不过代码还行：

#include <iostream>
#define int long long
using namespace std;
int n, a, b;
int l[200005], r[200005];
int f[200005], F[200005];
int luangao[200005];
int ciyanfangan[200005], zero[200005];
const int mod = 998244353;
int ciyande (int x, int y, int z) {
    if (y <= z) return 0;
    if (x <= z) return y - z;
    return y - x + 1;
}
int buciyande (int x, int y, int z) {
    if (x > z) return 0;
    return min (y, z) - x + 1;
}
int q_pow (int x, int y) {
    if (y == 0) return 1;
    if (y & 1) return x * q_pow (x * x % mod, y >> 1) % mod;
    return q_pow (x * x % mod, y >> 1);
}
int inv (int x) {return q_pow (x, mod - 2);}
signed main () {
    cin >> n >> a >> b;
    luangao[0] = 1;
    for (int i = 1; i <= n; i ++) {
        cin >> l[i] >> r[i];
        luangao[i] = luangao[i - 1] * (r[i] - l[i] + 1) % mod;
        if (ciyande (l[i], r[i], b) == 0) zero[i] = 1;
        zero[i] += zero[i - 1];
    }
    for (int i = 1; i + a - 1 <= n; i ++) {
        if (zero[i + a - 1] - zero[i - 1] != 0) continue;
        if (ciyanfangan[i - 1] != 0) {
            ciyanfangan[i] = ciyanfangan[i - 1] * inv (ciyande (l[i - 1], r[i - 1], b) ) % mod * ciyande (l[i + a - 1], r[i + a - 1], b) % mod;
            continue;
        }
        ciyanfangan[i] = 1;
        for (int j = i; j <= i + a - 1; j ++) ciyanfangan[i] = ciyanfangan[i] * ciyande (l[j], r[j], b) % mod;
    }
    for (int i = 0; i < a; i ++) f[i] = luangao[i];
    f[0] = 1;
    F[a] = ciyanfangan[1];
    f[a] = ( (luangao[a] - F[a]) % mod + mod) % mod;
    for (int i = a + 1; i <= n; i ++) {
        F[i] = (F[i - 1] * (r[i] - l[i] + 1) % mod + f[i - a - 1] * ciyanfangan[i - a + 1] % mod * buciyande (l[i - a], r[i - a], b) % mod);
        f[i] = ( (luangao[i] - F[i]) % mod + mod) % mod;
    }
    cout << f[n] << "\n";
    return 0;
}