专栏文章

Luogu P14031 【MX-X20-T5】「FAOI-R7」连接时光 II

rrizynvu
P14031题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minwgpai
此快照首次捕获于
2025/12/02 09:29
3 个月前
此快照最后确认于
2025/12/02 09:29
3 个月前
查看原文
cnblogs。
首先因为 fS(p)f_S(p) 的限制都是对于前缀的图的限制，所以先来考察前缀的图的结构和变化情况。
经过手玩能够知道，对于前 ii 个数的图，根据值域划分，连通块就为一些相邻的区间 。
然后在最后加入了一个数 ai+1=xa_{i + 1} = x（此时考虑的是相对大小）后，就相当于是加入了 [x,x+1)[x, x + 1) 这个区间，并且把区间右端点大于 xx 的区间都合并到一起。
此时能够发现，合并的一定都是这些区间里的后缀。
再结合这个限制，相当于是要求只有一个区间。
贪心的考虑，因为每次合并都是合并一段后缀，那么前 ii 个数形成的连通块如果不是一个区间（不满足限制），最靠前的区间的左端点一定不为 ii。
于是会发现在过程中只关心最靠前的区间的右端点，那就可以考虑设计 dp 了。
设 fi,jf_{i, j} 表示前 ii 个数，最靠前的区间的右端点是 jj（前 ii 个的相对顺序）的答案。
考虑如果加入了 ai+1=xa_{i + 1} = x（前 i+1i + 1 个的相对顺序），此时 jj 的变化是什么。
经过分讨容易知道有 j′={i+11≤x≤jjj<x≤i+1j' = \begin{cases}i + 1 & 1\le x\le j\\j & j < x \le i + 1\end{cases}。
那么转移就很好写出了：fi+1,i+1←fi,j×∑k=1jai+1i+1−k,fi+1,j←fi,j×∑k=j+1i+1ai+1i+1−kf_{i + 1, i + 1}\gets f_{i, j}\times \sum\limits_{k = 1}^j a_{i + 1}^{i + 1 - k}, f_{i + 1, j}\gets f_{i, j}\times \sum\limits_{k = j + 1}^{i + 1} a_{i + 1}^{i + 1 - k}。
因为这都对应的是 ai+1ka_{i + 1}^k 的前缀和或后缀和，所以容易优化到 O(1)\mathcal{O}(1)。
当然也可以把 fi+1,i+1f_{i + 1, i + 1} 视作“不合法”的方案数，类似总和减掉合法方案数，求出 fi+1,j(j≤i)f_{i + 1, j}(j\le i) 有 fi+1,i+1=∑j=1ifi,j∑j=0iai+1j−∑j=1ifi+1,jf_{i + 1, i + 1} = \sum\limits_{j = 1}^i f_{i, j}\sum\limits_{j = 0}^i a_{i + 1}^j - \sum\limits_{j = 1}^i f_{i + 1, j}，这样就只需要关心 ai+1ka_{i + 1}^k 的前缀和，会方便写一些。
对于 si=1s_i = 1 的位置，要求前缀必须为一个连通块，把不合法的 fi,j(j<i)f_{i, j}(j < i) 都置为 00 即可。
最后套上外层的 ∑T⊆S\sum\limits_{T\subseteq S}，对于 si=1s_i = 1 的位置，可以是为 11，就只保留 fi,if_{i, i}；也可以为 00，所有数都不变。
于是扩展到 ∑T⊆S\sum\limits_{T\subseteq S} 只需要加上一个 fi,i←fi,i×(1+si)f_{i, i}\gets f_{i, i}\times (1 + s_i)。
时间复杂度 O(n2)\mathcal{O}(n^2)。
CPP
#include <bits/stdc++.h>

using ll = long long;

constexpr ll mod = 998244353;
constexpr int maxn = 5000 + 10;

int n, a[maxn];
char s[maxn];
ll f[maxn];

inline void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%s", s + 1);

    f[1] = 1 + (s[1] - '0');
    for (int i = 2; i <= n; i++) {
        ll pw = 1, sum = 1, sumf = 0;
        for (int j = i - 1; j >= 1; j--) {
            sumf = (sumf + f[j]) % mod;
            f[j] = f[j] * sum % mod;
            pw = pw * a[i] % mod;
            sum = (sum + pw) % mod;
        }
        f[i] = sumf * sum % mod;
        for (int j = 1; j < i; j++) {
            f[i] = (f[i] - f[j] + mod) % mod;
        }
        f[i] = f[i] * (1 + s[i] - '0') % mod;
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + f[i]) % mod;
    }
    printf("%lld\n", ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...