CWOI2020 BZOJ-DP 杂题选讲 题解

难难

BZOJ 4316 isn

给出一个序列 A，每次删除序列中一个数，直到序列变得非降。

求删除方案数。

对于所有 A 中的元素，被删除的时间如果相同，则两个方案是一样的。

dp，树状数组，容斥。

假设我们已经算出来了 g(i) 表示原序列中长度为 i 的非降序列个数。

那么答案可以考虑为 \sum g(i) * (n - i)!。

然而明显，有可能在删除到 i 个数之前的某个时刻，序列已经非降。根据题意此情况不再贡献答案。

考虑容斥。

我们只用考虑在长度为 i + 1 时序列已经非降的情况，因为对于长度大于 i + 1 的非降序列，在删除到 i + 1 时必定也非降，即贡献会在此时计算。

根据定义，长度为 i + 1 的非降序列个数为 g(i + 1)，其对应的删除方案有 g(i + 1) * (n - (i + 1))! 个，对于每一种方案，任意再删除剩下的 i + 1 个数中的任意一个数，都仍为非降。即不合法贡献为 g(i + 1) * (n - i - 1)! * (i + 1)。

那么对于每一个 g(i)，其对答案贡献为 g(i) * (n - i)! - g(i + 1) * (n - i - 1)! * (i + 1)。

然后我们考虑如何计算 g(i)。

令 f(i, j) 表示以 i 结尾（离散后），长度为 j 的非降序列个数，则有 g(i) = \sum_{j = 1}^{n} f(j, i)。

那么有：

其中 x_{id} 表示离散后值为 x 的数的下标。

我们发现这就是一个二位数点的问题，通过 BIT 优化即可。

时间复杂度 O(n^2\log n)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 2000 + 10, P = 1e9 + 7;
int n, arr[MAXN], f[MAXN][MAXN], cpy[MAXN], rk[MAXN], val[MAXN], g[MAXN], prod[MAXN];

struct BIT {
    int bit[MAXN];
    void add(int x, int val) { val %= P; for (; x <= n + 1; x += x & (-x)) (bit[x] += val) %= P; }
    int sum(int x) { int ret = 0; for(; x; x -= x & (-x)) (ret += bit[x]) %= P; return ret; }
} bit[MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]), cpy[i] = arr[i];
    }
    sort(arr + 1, arr + n + 1);
    int m = unique(arr + 1, arr + n + 1) - arr - 1;
    for (int i = 1; i <= n; ++i) rk[i] = lower_bound(arr + 1, arr + m + 1, cpy[i]) - arr + 1, val[rk[i]] = cpy[i];
    f[0][0] = 1, bit[0].add(1, 1);
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j >= 1; --j) {
            (f[j][i] += bit[j - 1].sum(rk[i])) %= P, bit[j].add(rk[i], f[j][i]);
        }
    }
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) (g[i] += f[i][j]) %= P;
    int ans = 0;
    prod[1] = 1;
    for (int i = 2; i <= n; ++i) prod[i] = (1ll * prod[i - 1] * i) % P;
    for (int i = n; i >= 1; --i) {
        ll tmp1 = 1ll * g[i] * prod[n - i] % P;
        ll tmp2 = 1ll * g[i + 1] * prod[n - i - 1] % P * (i + 1) % P;
        (ans += ((tmp1 - tmp2) % P + P) % P) %= P;
    }
    printf("%d\n", ans);
    return 0;
}

做的时候发现自己还是没有理解二位维点 dp 的细节，比如循环顺序之类的。

BZOJ 1566 管道取珠

给出两个串 S, T，均由 'A', 'B' 组成，每次操作可以取出某个串最右边的字符并添加到输出字符串 U 的最左边。令 a_i 表示对于所有可能的输出字符串中字典序第 i 大的字符串，有多少种不同的操作方式能得到 。求 \sum a_i^2。

两种不同的方式定义为存在某次操作，使得第一种取的 S，第二种取的 T；或第一种取的 T，第二种取的 S。

|S|, |T| \leq 500

dp

加法具有交换律，故可以不考虑字典序。

一个重要的观察是，a_i^2 等价于对于第 i 种串，两个人互相独立地取，最终均得到第 i 种串的方案数。（即 a_i \times a_i）。

则有一个奇妙重重的 dp 状态与转移（可能是个套路）：

令 f(i, j, k) 表示两个人均取了 i 个字符，第一个人取 S 取了 j 个，第二个人取 S 取了 k 个。则有第一人取 T 取了 i - j 个，第二人取 T 取了 i - k 个。且最后两串相同的方案数。

不难发现，一种状态是所有符合定义的 a_i^2 的和，且没有重复与遗漏。

那么有转移：

滚动数组即可。

时间复杂度 O(n^3)

#include <bits/stdc++.h>
using namespace std;

const int P = 1024523;

const int MAXN = 500 + 10;
int n, m, s[MAXN], t[MAXN], f[MAXN][MAXN], g[MAXN][MAXN];
char str[MAXN];

void add(int& a, int b) { a = a + b > P ? a + b - P : a + b; }

int main() {
    scanf("%d %d", &n, &m);
    scanf("%s", str + 1);
    for (int i = 1; i <= n; ++i) s[i] = str[i] == 'A';
    s[0] = -1, t[0] = -2;
    scanf("%s", str + 1);
    for (int i = 1 ;i <= m; ++i) t[i] = str[i] == 'A';
    f[0][0] = 1;
    for (int i = 1; i <= n + m; ++i) {
        for (int j = 0; j <= n; ++j) for (int k = 0; k <= n; ++k) g[j][k] = f[j][k], f[j][k] = 0;
        for (int j = max(0, i - m); j <= min(n, i); ++j) {
            for (int k = max(0, i - m); k <= min(n, i); ++k) {
                if (j && k && s[j] == s[k]) add(f[j][k], g[k - 1][j - 1]);
                if (j && s[j] == t[i - k]) add(f[j][k], g[j - 1][k]);
                if (k && t[i - j] == s[k]) add(f[j][k], g[j][k - 1]);
                if (t[i - j] == t[i - k]) add(f[j][k], g[k][j]);
            }
        }
        if (i == n + m) { printf("%d\n", f[n][n]); return 0; }
    }
    return 0;
}

玄妙状态与转移。