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

· · 题解

维护数字之间的相对顺序，考虑从左往右依次插入数字。

不难发现有两个性质：

  1. 如果将数放在当前的最高位，那么就会造成最大值和其他数不连通，我们姑且叫他缺口。（可以有多个缺口）
  2. 如果我们将数插入在 i 与 i+1 之间，那么所有 > i 的数字都会联通，我们称为补上缺口。

继续观察，我们发现当前只有最小的缺口是重要的，因为最小的缺口一定不早于更大的缺口被补上。

那么我们的状态设计就变得简单了：设 f_{i,j} 表示当前在第 i 个数，缺口最小在 j 和 j+1 之间（特别的，j=0 意味着没有缺口）。

那么再从在最上面，最小缺口上还是最小缺口下方数等分类讨论即可，代码如下，其中 z_{i,k} 表示 a_i^k：

f[1][0]=1*((s[1]=='1')+1);
    for(int i=2;i<=n;i++)
    {
        f[i][i-1]+=f[i-1][0];//在最上面放数
        f[i][i-1]%=mod;
        for(int j=1;j<=i-1;j++)
        {
            f[i][0]+=f[i-1][0]*z[i][i-j]%mod;//在除了最上面的地方放数
            f[i][0]%=mod;
        }
        for(int j=1;j<i;j++)//最小缺口
        {
            for(int k=1;k<=i;k++)//插入位置
            {
                if(j<k)
                {
                    f[i][j]+=f[i-1][j]*z[i][i-k]%mod;//在缺口上方放数
                    f[i][j]%=mod;
                }
                else
                {
                    f[i][0]+=f[i-1][j]*z[i][i-k]%mod;//在缺口下方放数
                    f[i][0]%=mod;
                }
            }
        }
        if(s[i]=='1')
        {
            f[i][0]*=2;//这里要注意，当 s_i 取 1 时没有缺口符合条件，所以要*2
            f[i][0]%=mod;
        }
    }

不难发现这个是可以使用前缀和优化的，补上即可。

最后代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5005,mod=998244353;
int a[N];
char s[N];    
int n;
int f[N][N],z[N][N],sum[N];
void solve()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    scanf("%s",s+1);
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            f[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++)
    {
        z[i][0]=1;
        for(int j=1;j<=n;j++)
        {
            z[i][j]=z[i][j-1]*a[i]%mod;
        }
    }
    f[1][0]=((s[1]=='1')+1);
    for(int i=2;i<=n;i++)
    {
        f[i][i-1]+=f[i-1][0];
        f[i][i-1]%=mod;
        for(int j=1;j<=i-1;j++)
        {
            f[i][0]+=f[i-1][0]*z[i][i-j]%mod;
            f[i][0]%=mod;
        }
        for(int j=1;j<=n;j++)
        {
            sum[j]=sum[j-1]+z[i][i-j];
            sum[j]%=mod;
        }
        for(int j=1;j<i;j++)
        {
            f[i][j]+=f[i-1][j]*(sum[i]-sum[j])%mod;
            f[i][j]%=mod;
            f[i][0]+=sum[j]*f[i-1][j]%mod;
            f[i][0]%=mod;
        }
        if(s[i]=='1')
        {
            f[i][0]*=2;
            f[i][0]%=mod;
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++)
    {
        ans+=f[n][i];
        ans%=mod;
    }
    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans);
}
signed main()
{
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}