CF2069C Beautiful Sequence 解题报告

_mi_ka_ · 2025-02-21 16:41:34 · 题解

题目传送门

题目大意

有一个只有 1、2、3 组成的序列 a，找漂亮子序列（对于非首元素，左边都有比它小的元素，非尾元素，右边都有比它大的元素）的个数，答案对 998244353 取模。

解题思路

对于只有 1、2、3 组成的序列，不难想出这个漂亮子序列的形式：首元素是 1，尾元素是 3，中间必须全是 2。

对于每一个 1，遍历它后面的这个序列时，当它遇到 3 时，它和这个 3 对答案的贡献为 2^{cnt2}-1（cnt2 为当前 1 和当前 3 之间的 2 的个数）。则这个 1 对答案的总贡献为

其中 [bool] 为这个布尔表达式的值。

显然这个式子是需要 n^2 的复杂度实现的，如何简化时间复杂度呢？

考虑将第一个 1 所贡献的答案求出为 ans1，在遍历时想要在 ans1 的基础上进行运算得出后面的 1 对答案的贡献：

• 用一个 3 的个数的后缀 cnt3 代表 a_i 后面的 3 的个数，显然每遇到一个 3，cnt3 的个数减一；
• 每遇到一个 2，对于这个 2 后面的每个 3，它对答案的贡献都要从 2^{cnt2}-1 变为 2^{cnt2-1}-1，操作为 -1 再 \times \frac{1}{2}。则遇到这个 2，对 ans1 的总变化为 -cnt3 再 \times \frac{1}{2}。
• 每遇到一个 1，此时的 ans1 就是它对答案的变化，直接加到答案上即可。

预处理求出 ans1 和 cnt3 的时间复杂度为 O(n)，遍历序列的复杂度为 O(n\log m)，其中 m 为模数 998244353。

总时间复杂度 O(n\log m)。

AC Code

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
int n;
int a[200005]; 
int re()//快读 
void wr(int x)//快写 
int ksm(int a,int b)//快速幂 
{
    int ans=1;
    for(;b;a*=a,a%=mod,b>>=1)
        if(b&1)
            ans*=a,ans%=mod;
    return ans;
}
signed main(){
    int T=re();
    while (T--)
    {
        int n=re(),ans=0;
        for(int i=1;i<=n;i++)
            a[i]=re();
        int cnt2=0,cnt3=0;
        int ans1=0,pos=n;//pos为第一个1的位置 
        for(int i=1;i<=n;i++)
            if(a[i]==1)
            {
                pos=i;
                break;
            }
        for(int i=pos;i<=n;i++)
            if(a[i]==2)
                cnt2++;
            else if(a[i]==3)
            {
                ans1+=ksm(2,cnt2)-1;//这个3对答案的贡献 
                ans1%=mod;
                cnt3++;
            }
        ans+=ans1;
        for(int i=pos+1;i<=n;i++)
            if(a[i]==2)//遇到2 
                ans1-=cnt3,ans%=mod,ans+=mod,ans%=mod,ans1*=ksm(2,mod-2),ans1%=mod;
            else if(a[i]==1)
                ans+=ans1,ans%=mod;
            else
                cnt3--;//遇到3 
        wr(ans),puts("");
    }
    return 0;
}