题解：CF1984F Reconstruction

· · 题解

对于一个对 s 赋值的合法方案，我们可以确定这一方案下 a 中所有数的总和。这是因为如果 s_1=\texttt{S} 或 s_n=\texttt{P}，我们就可以得到所有数的总和，否则的话 s 中一定存在子串 PS，也可以得到所有数的总和。由以上的分析可以得到，可能可以成为 a 中所有数的总和的数为：b_1,b_1+b_2,b_2+b_3,\cdots,b_{n-1}+b_n,b_n 这 n+1 个数。

因此我们依次考虑这 n+1 个数。假设当前考虑的数为 sum，我们需要计算出使得 a 中所有数的总和为 sum 的合法 s 的方案数。观察到我们可以根据 sum 把所有后缀限制转变为前缀限制。考虑 DP，设 f_{i,0/1} 表示考虑到第 i 位且第 i 位的 s 填 P 或 S 的方案数，转移则枚举 i-1 位填什么。如果 i-1 和 i 位填 PP，则能够转移过来当且仅当 b_i-b_{i-1}\in[-m,m]，如果填 SP，则限制是 b_i-(sum-b_{i-1})\in[-2m,2m]，如果填 PS 则限制是 b_{i-1}+b_i=sum，如果为 SS 则限制是 (sum-b_i)-(sum-b_{i-1})\in[-m,m]。当然还有一些边界条件。

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+5,P=998244353;
int T,n,f[N][2],ans;
long long b[N],sum,m;
char s[N];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m>>(s+1);
        for(int i=1;i<=n;i++)   cin>>b[i];
        b[n+1]=b[n+2]=b[n+3]=0;
        ans=0;
        unordered_set<long long> st;st.clear();
        for(int _=1;_<=n+1;_++){
            sum=b[_]+b[_-1];
            if(st.find(sum)!=st.end())  continue;
            st.insert(sum);
            f[1][0]=(b[1]>=-m&&b[1]<=m);
            f[1][1]=(b[1]==sum);
            if(s[1]=='P')   f[1][1]=0;
            if(s[1]=='S')   f[1][0]=0;
            for(int i=2;i<=n;i++){
                f[i][0]=f[i][1]=0;
                if(b[i]-b[i-1]>=-m&&b[i]-b[i-1]<=m) f[i][0]=(f[i][0]+f[i-1][0])%P;
                if(b[i]-(sum-b[i-1])>=-2*m&&b[i]-(sum-b[i-1])<=2*m) f[i][0]=(f[i][0]+f[i-1][1])%P;
                if(b[i-1]==sum-b[i])    f[i][1]=(f[i][1]+f[i-1][0])%P;
                if(sum-b[i]-(sum-b[i-1])>=-m&&sum-b[i]-(sum-b[i-1])<=m) f[i][1]=(f[i][1]+f[i-1][1])%P;
                if(s[i]=='P')   f[i][1]=0;
                if(s[i]=='S')   f[i][0]=0;
            }
            if(b[n]==sum)   ans=(ans+f[n][0])%P;
            if(b[n]>=-m&&b[n]<=m)   ans=(ans+f[n][1])%P;
        }
        cout<<ans<<endl;
    }
    return 0;
}