剑锋所指,心之所向。

B 向右看齐

给出 n 和序列 a,求有多少个 n 阶卡特兰序列,满足 a 是该序列的子序列。

n, |a| \leq 400


场上一直在想咋容斥(

事实上非常显然的 dp,考虑状态由 (i, j, k) 表示,表示已经填了 i 个数,并且和 a 匹配到了 j 位,然后左括号比右括号多了 k 个。直接转移即可。

const int MAXN = 400 + 10;
const int P = 998244353;

int n, m, arr[MAXN], f[MAXN][MAXN][MAXN];

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

int main() {
    IO::read(n), IO::read(m);
    rep(i, 1, m) IO::read(arr[i]);
    f[0][0][0] = 1;
    reverse(arr + 1, arr + m + 1), arr[0] = -1, arr[m + 1] = -1;
    rep(i, 0, n + n) {
        rep(j, 0, min(i, m)) {
            rep(k, 0, i) {
                if (k > 0) add(f[i + 1][j + (arr[j + 1] == 0)][k - 1], f[i][j][k]);
                add(f[i + 1][j + (arr[j + 1] == 1)][k + 1], f[i][j][k]);
            }
        }
    }
    printf("%d\n", f[n + n][m][0]);
    return 0;
}

事实上考试结束前 5 分钟我大概想到了可以 dp,可是没时间写了(

不知道为什么会去想容斥,很奇怪啊。

C 齐步走

一个矩阵,某个元素会依赖其上方或右方的点(保证该元素存在的情况下)。最左上角的点值为 1。每个元素有 p(i, j) 的概率将其依赖元素的值取反。求最外圈(第一排、列,最后一排、列)值全部为 1 的概率。

矩阵大小 10^6


a 依赖 b,则将 ab 连边。则一定是一棵树。

问题等价与,每条边会有 p 的概率将儿子的值为取反父亲,求某些关键点的值与根节点相同的概率。

考虑树形 dp,记 f_i 表示 i 的子树内的所有关键点值与 i 相同的概率。g_i 表示全部不同。直接转移即可。

const int MAXN = 1e6 + 10;
const int P = 998244353;

int n, m;

int getnum(int i, int j) { return (i - 1) * m + j; }

int head[MAXN], e_cnt;
struct Edge { int nxt, to, w; } e[MAXN];
void add(int u, int v) { e[++e_cnt].to = v, e[e_cnt].nxt = head[u], head[u] = e_cnt; }

int p[MAXN], np[MAXN];

int qpower(int a, int x) {
    int ret = 1;
    for (; x; x >>= 1, a = 1ll * a * a % P) x & 1 ? ret = 1ll * ret * a % P : 0;
    return ret;
}

int f[MAXN], g[MAXN], flg[MAXN];
void dfs(int u) {
    f[u] = g[u] = 1;
    if (flg[u]) g[u] = false;
    for (int _ = head[u], v; _; _ = e[_].nxt) {
        v = e[_].to;
        dfs(v);
        f[u] = 1ll * ((1ll * f[v] * p[v] % P) + (1ll * g[v] * np[v] % P)) % P * f[u] % P;
        g[u] = 1ll * ((1ll * f[v] * np[v] % P) + (1ll * g[v] * p[v] % P)) % P * g[u] % P;
    }
}

int main() {
    IO::read(n), IO::read(m);
    int inv = qpower(100, P - 2);
    rep(i, 1, n) rep(j, 1, m) {
        int x; IO::read(x);
        if (i == 1 && j == 1) continue;
        if (x) add(getnum(i, j - 1), getnum(i, j));
        else add(getnum(i - 1, j), getnum(i, j));
    }
    rep(i, 1, n) rep(j, 1, m) {
        if (i == 1 || j == 1 || i == n || j == m) flg[getnum(i, j)] = true;
        int x; IO::read(x);
        p[getnum(i, j)] = 1ll * (100 - x) * inv % P;
        np[getnum(i, j)] = 1ll * x * inv % P;
    }
    dfs(1);
    printf("%d\n", f[1]);
    return 0;
}

总结

感觉考试的时候智商不在线(

T2 的 dp 状态是非常显然的,可是我直到最后才想到...

不过 T3 的建树的确挺有意思的,算是学到很多吧。

国庆 Day 5 模拟赛赛后题解与总结
上一篇 «
atcoder abc 与 CF div1 B, C 做题记录
» 下一篇