题解：P17337 【MX-X30-T3】宇宙分解

· · 题解

从来没有见过这么一眼的 DP。

题意

P17337 【MX-X30-T3】宇宙分解

你有一个长度为 n 的 01 序列 a 和两种操作：

  • 选择 a_i<a_{i+1} 并删去 a_{i+1}。
  • 选择 a_i<a_{i+1} 并交换这两个数。

可以进行若干次这两种操作（可以不进行），求得到的序列数，对 998244353 取模，多测。

设 s 为序列中 1 的个数。

1\le\small{\sum n}\le 10^5\quad 0\le\small{\sum s}\le 2000

思路

大概可以想象成把一堆 1 往左挪，途中可以删掉一些数。

首先上来发现一个东西，最开头的那一段 1 无法做任何操作，不影响答案，直接去掉。

然后发现，在固定最后剩下的 1 的个数为 k 的情况下，只要我选最右边的 k 个 1 往左移动，一定可以覆盖所有情况。

简单证明一下，挺显然的。

把选出来不删除的 k 个 1 从左到右编号为 1_1,1_2,\ldots,1_k。

设 id_i 为 1_i 前面的 0 的个数，每次移动操作就是让某个 id_i\gets id_i-1。

设要求最后的 id=id'。

::::info[proof]

那么看看 id' 和原 id 之间有什么关系。

由于每次都是减少，所以：

id'_1\le id_1\quad id'_2\le id_2\quad\cdots\quad id'_k\le id_k

直接对比。我们设 idr 为最优方案（选最右边的 k 个 1）的 id。

显然有：

id_1\le idr_1\quad id_2\le idr_2\quad\cdots\quad id_k\le idr_k

显然有：

id'_1\le id_1\le idr_1\quad id'_2\le id_2\le idr_2\quad\cdots\quad id'_k\le id_k\le idr_k

所以 id' 对于 idr 来说满足条件。

所以直接取 idr 能覆盖所有情况。

::::

然后，1 和 1 之间不能对换。我们俩都是 1，开始我在你左边，结束了我不可能到你右边去。所以：

id'_1\le id'_2\le \cdots \le id'_k

把 id' 看作 x，简单来说，就是求满足：

x_1\le x_2\le \cdots\le x_k\quad x_1\le id_1\quad x_2\le id_2\quad\cdots\quad x_k\le id_k

解的个数，要求解为非负整数，k 取遍 1 到 s。

显然是把 id 从右到左一个一个加进去求个数的，因为刚刚证了，一定是选最右边的 k 个。

看起来不好求，但是这道题允许了 O(ns) 做法，所以直接多记一维，记什么呢？

因为你要求 x_i\le x_{i+1}，所以第二位肯定是表示上一个 x。

稍微转换一下，设 dp_{i,j} 为从右到左处理完 x_i 到 x_s，然后 x_i=j 的方案数。

咋转移？要求 x_i\le x_{i+1} 且 x_i\le id_i，所以：

dp_{i,0},dp_{i,1},\ldots ,dp_{i,\min\{j,id_i\}}\gets dp_{i+1,j}

答案就是所有 dp_{i,j} 的和，因为这里 (s-i+1) 其实就是刚刚说的 k。结束。

复杂度

如果你真的傻乎乎的一个一个给 dp_{i-1} 赋值，那复杂度是 O(n^2 s) 的。

这是区间加，直接差分优化掉一个 O(n)，时间复杂度是 O(ns)。

空间如果你直接开 O(ns) 会炸，把 k 维滚掉就行了，复杂度 O(n)。

代码

只能说没有任何难度。

static constexpr int MAXN = (int)(1e5) + 10;

int n, k0, k1, ans;
string s; bool flag;
int il[MAXN], dp[MAXN], id[MAXN];

void init(int n) {
    std::fill(dp, dp + n + 6, 0);
    k0 = 0, k1 = 0, ans = 0, flag = false;
}

void solve() {
    cin >> n >> s, init(n);
    s = ' ' + s, n = 0;
    for (int i = 1; i < s.size(); i++) { // 用 flag 先把开头的 1 筛掉
        if (!flag && s[i] == '1') continue;
        il[++n] = s[i] - '0', flag = true;
        il[n] == 1 ? (id[++k1] = k0) : k0++; // 记录 id
    }
    dp[k0] = 1, ans = 1; // 注意 k = 0 的时候有一种方案
    for (int i = k1; i >= 1; i--) {
        for (int j = 0; j <= k0; j++) {
            int tmp = dp[j]; dp[j] = 0;
            Add(dp[min(id[i], j)], tmp);
        }
        int res = 0;
        for (int j = k0; j >= 0; j--)
            Add(dp[j], dp[j + 1]), Add(res, dp[j]);
        Add(ans, res);
    }
    cout << ans << '\n';
}

signed main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n0; cin >> n0;
    while (n0--) solve();

    return 0;
}