题解：P10816 [EC Final 2020] Namomo Subsequence

wujingfey · 2024-09-29 22:03:48 · 题解

传送门

~~所实话这题真的只有绿题难度吗？道心破碎了。~~

挑战本题最详细题解，求通过。

题意（人话版）

给你一个字符串 s，找其中一个长度为 6 的序列满足ABCDCD形式的方案数，对 998244353 取模。

n\leqslant 10^6

题解

观察ABCDCD的形式，可以把此题分成两部分考虑：AB+CDCD。详细地说，我们枚举每一位 i，分别求出 [1,i-1] 中形如AB的方案数，然后在 [i,len] 中求出形如CDCD的方案数。

对于前者

我们可以预处理：先开个桶 t_{i,j} 表示前 i 位，字符 j 出现了多少次。再设 g_{i} 表示前 i 个字母能有多少种 AB 方案。

桶的转移很简单，就不细说了。考虑 g：每个 g_i 从定义出发，就可以枚举每种字符出现的次数，然后乘以其他字符出现的次数：

for(int j=0;j<=61;j++){
    t[i][j]=t[i-1][j];//继承
    if(a[i]==j) t[i][j]++;//更新桶 
    g[i]+=t[i][j] * (i-t[i][j]);
    //枚举i,有i*(i-t[i][j])种AB方案 
}
g[i]>>=1;//AB、BA都会被计算，去除重复贡献

对于后者

我们从后往前枚举 i，维护CDCD方案数，同时记录答案。

记录CDCD的方案数，我们采用最朴素的“拼接法”。（设现在枚举到的字符是 p）。

如果我要知道 CDCD 的方案数，并且把 p 固定成第一个 C，那么我们要在后面拼接 DCD。
如果我要知道后面 DCD 有多少种可行方案，我就要同时维护一个 DCD 的方案数。与上面类似，如果把 p 固定成第一个 D，那我只需要再后面拼接 CD。
如果我要知道后面 CD 的方案数，同上，我需要记录 D 的方案数，也就是个桶了。

所以我用 f1,f2,f3 分别记录：p 固定成最后一个 D、最后一个 C、第一个 D 的方案数。

那么转移就不难想了。

现在知道了后面拼接 DCD 的方案数，第一个 C 也固定了，现在只需要解决前面 AB 的方案数就好。方案数已经预处理好了，现在只需要容斥掉 ABCD 出现相等的情况。
利用第一个桶中的信息和 p 的位置，不难容斥出 AB 方案数。

for(int i=n;i>=1;i--){
    int p=a[i];
    f1[p]++;//f1记录D方案数 
    for(int j=0;j<=61;j++){
        //当前字母为p，也就是说：C固定为p，枚举所有CDC 
        if(j==p) continue;//重复不能计入 
        f3[p][j]+=f2[j][p], f3[p][j] %=mod;//f3记录DCD方案数 
        f2[p][j]+=f1[j], f2[p][j] %=mod;//f2记录CD方案数 
        //----------------------------容斥过程 
        int x1=t[i-1][j] * (i-1-t[i-1][j]) %mod;
        int x2=t[i-1][p] * (i-1-t[i-1][p]) %mod;
        int x3=t[i-1][j] * t[i-1][p] %mod;
        int x=(g[i-1] -x1 -x2 +x3 +mod) %mod;
        ans+=f3[j][p] * x, ans %= mod;
    }
}

两份核心代码加在一起就是 AC 代码了。

CODE：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,mod=998244353;
char s[N];
int n,ans,a[N],t[N][65];
int g[N],f1[65],f2[65][65],f3[65][65],f4[65][65];//dp数组 
void init(){//初始化 
    n=strlen(s+1);
    for(int i=1;i<=n;i++){
        if('A'<=s[i]&&s[i]<='Z') a[i]=s[i]-'A';
        else if('a'<=s[i]&&s[i]<='z') a[i]=s[i]-'a'+26;
        else a[i]=s[i]-'0'+52;
        for(int j=0;j<=61;j++){
            t[i][j]=t[i-1][j];//继承
            if(a[i]==j) t[i][j]++;//更新桶 
            g[i]+=t[i][j] * (i-t[i][j]);
            //枚举i,有i*(i-t[i][j])种AB方案 
        }
        g[i]>>=1;//AB、BA都会被计算，去除重复贡献 
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>(s+1);
    init();
    for(int i=n;i>=1;i--){
        int p=a[i];
        f1[p]++;//f1记录D方案数 
        for(int j=0;j<=61;j++){
            //当前字母为p，也就是说：C固定位p，枚举所有CDC 
            if(j==p) continue;//重复不能计入 
            f3[p][j]+=f2[j][p], f3[p][j] %=mod;//f3记录DCD方案数 
            f2[p][j]+=f1[j], f2[p][j] %=mod;//f2记录CD方案数 
            //----------------------------容斥过程 
            int x1=t[i-1][j] * (i-1-t[i-1][j]) %mod;
            int x2=t[i-1][p] * (i-1-t[i-1][p]) %mod;
            int x3=t[i-1][j] * t[i-1][p] %mod;
            int x=(g[i-1] -x1 -x2 +x3 +mod) %mod;
            ans+=f3[j][p] * x, ans %= mod;
        }
    }
    cout<<ans;
    return 0;
}

~~这么好的题解真的不点个赞再走吗？~~