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

· · 题解

先考虑建出来的图长什么样，我们会发现一定是若干个连通块，且每个连通块内部的点是一段连续区间。证明是显然的，因为一定不可能存在 i<j<k 使得 p_i<p_j\land p_j<p_k\land p_i>p_k。而且，一个连通块中的所有 p 一定大于它前面的所有 p，否则它就会与前面的连通块合并。

先不管 S 的限制，考虑 dp，设 dp_i 表示 [1,i] 形成连通块的所有方案的贡献之和。下面所提到的 p 都是相对大小，插入一个新的 p 将它后面的统一平移即可。

我们枚举删掉 i 之后的第一个连通块 [1,j]，其中所包含的 p 也一定是 [1,j]，这样才能保证 [j+1,i-1] 中的所有 p 都大于 [1,j] 中的。

因为加入 i 之后要使得前面的所有连通块合并，所以必须满足 p_i\le j，这样 i 就会向第一个连通块连边，同时也一定会向 [j+1,i-1] 中的所有点连边。

接下来，还需要枚举 p_i 的值具体是多少，也就相当于枚举 i 向 [1,j] 中的多少个点连边，然后枚举 [j+1,i-1] 中的点的相对大小，这会决定它们内部的连边方式，具体转移如下：

dp_i=\sum_{j=1}^{i-1}dp_j\cdot(\sum_{k=i-j}^{i-1}a_i^k)\cdot(\prod_{k=j+1}^{i-1}\sum_{l=0}^{k-j-1}a_k^l)

直接转移是 O(n^4) 的，显然可以通过预处理将时间复杂度降到 O(n^2)，设：

pre_{i,j}=\sum_{k=0}^j a_i^k\\ f_{l,r}=\prod_{i=l}^r\sum_{j=0}^{i-l}a_i^j=f_{l,r-1}\cdot pre_{r,r-l}

那么转移就会变成：

dp_i=\sum_{j=1}^{i-1}dp_j\cdot(pre_{i,i-1}-pre_{i,i-j-1})\cdot f_{j+1,i-1}

现在考虑 S 对答案的影响，我们发现，如果一个图满足 S 中的 k 个限制，它对答案的贡献是 2^k，那么，只需要将 S 中的位置的 dp 值乘 2 即可，也就是：

dp_i=(1+[i\in s])\cdot \sum_{j=1}^{i-1}dp_j\cdot(pre_{i,i-1}-pre_{i,i-j-1})\cdot f_{j+1,i-1}

最后统计答案时枚举第一个连通块的右端点即可：

ans=\sum_{i=1}^n dp_i\cdot f_{i+1,n}

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

:::info[参考代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+5,mod=998244353;
int T,n,ans,a[N],dp[N],f[N][N],pre[N][N];
string s;
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        cin>>s;
        s=" "+s;
        for(int i=1;i<=n;i++){
            pre[i][0]=1;
            int sum=1;
            for(int j=1;j<=n;j++){
                sum=sum*a[i]%mod;
                pre[i][j]=(pre[i][j-1]+sum)%mod;
            }
            f[i][i-1]=f[i+1][i]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                f[i][j]=f[i][j-1]*pre[j][j-i]%mod;
            }
        }
        for(int i=1;i<=n;i++){
            dp[i]=(i==1?1:0);
            for(int j=1;j<i;j++){
                dp[i]=(dp[i]+dp[j]*(pre[i][i-1]-pre[i][i-j-1])%mod*f[j+1][i-1])%mod;
            }
            if(s[i]=='1'){
                dp[i]=dp[i]*2%mod;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            ans=(ans+dp[i]*f[i+1][n])%mod;
        }
        cout<<(ans+mod)%mod<<"\n";
    }
    return 0;
}

:::