连接时光 II

· · 题解

任意连通块一定是一段连续区间。考虑反证：若不连续，则存在 i<j<k，使得 (i,k) 有连边，(i,j),(j,k) 无连边，即 p_i>p_k 且 p_i<p_j<p_k，显然矛盾。此外，后面的连通块一定整体大于前面的连通快，否则会发生合并。

限制是针对一段前缀的，考虑在状态中记录 1 所在连通块的信息。记 f_{i,j} 为考虑前 i 个数，1 所在连通块大小为 j 的总贡献。转移时分讨新加入的数的相对大小：

f_{i+1,j} \leftarrow f_{i,j} \cdot \sum_{k=0}^{i-j} a_{i+1}^k f_{i+1,i+1} \leftarrow f_{i,j} \cdot \sum_{k=i-j+1}^i a_{i+1}^k

做完上述转移后，若 i \in S，则当 i \in T 时，会额外产生 f_{i,i} 的贡献。直接将 f_{i,i} 乘二即可。

答案为 \sum f_{n,1 \sim n}。预处理 a_i 的整数次幂的前缀和，复杂度 O(n^2)。

:::success[Code]{open}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5010;
const int MOD = 998244353;
ll a[MAXN], f[MAXN][MAXN], pw[MAXN][MAXN];
int n;
string s;
void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++){
        pw[i][0] = 1;
        for (int j = 1; j <= n; j++){
            pw[i][j] = pw[i][j - 1] * a[i] % MOD;
        }
        for (int j = 1; j <= n; j++){
            pw[i][j] = (pw[i][j] + pw[i][j - 1]) % MOD;
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            f[i][j] = 0;
        }
    }
    f[1][1] = 1;
    for (int i = 1; i < n; i++){
        if (s[i] == '1'){
            f[i][i] = f[i][i] * 2 % MOD;
        }
        for (int j = 1; j <= i; j++){
            f[i + 1][j] = (f[i + 1][j] + f[i][j] * pw[i + 1][i - j] % MOD) % MOD;
            f[i + 1][i + 1] = (f[i + 1][i + 1] + f[i][j] * ((pw[i + 1][i] - pw[i + 1][i - j] + MOD) % MOD) % MOD) % MOD;
        }
    }
    if (s[n] == '1'){
        f[n][n] = f[n][n] * 2 % MOD; 
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        ans = (ans + f[n][i]) % MOD;
    }
    cout << ans << "\n";
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

:::