专栏文章

CF2069C Beautiful Sequence 解题报告

__mi_ka_
CF2069C题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miq7etbx
此快照首次捕获于
2025/12/04 00:11
3 个月前
此快照最后确认于
2025/12/04 00:11
3 个月前
查看原文
题目传送门

题目大意

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

解题思路

对于只有 1、2、31、2、3 组成的序列，不难想出这个漂亮子序列的形式：首元素是 11，尾元素是 33，中间必须全是 22。
对于每一个 11，遍历它后面的这个序列时，当它遇到 33 时，它和这个 33 对答案的贡献为 2cnt2−12^{cnt2}-1（cnt2cnt2 为当前 11 和当前 33 之间的 22 的个数）。则这个 11 对答案的总贡献为 ∑i=1n[ai=1]∑j=i+1n[aj=3](2cnt2i,j−1)\sum_{i=1}^{n}[a_i=1]\sum_{j=i+1}^{n}[a_j=3](2^{cnt2_{i,j}}-1)
其中 [bool][bool] 为这个布尔表达式的值。
显然这个式子是需要 n2n^2 的复杂度实现的，如何简化时间复杂度呢？
考虑将第一个 11 所贡献的答案求出为 ans1ans1，在遍历时想要在 ans1ans1 的基础上进行运算得出后面的 11 对答案的贡献：
  • 用一个 33 的个数的后缀 cnt3cnt3 代表 aia_i 后面的 33 的个数，显然每遇到一个 33，cnt3cnt3 的个数减一；
  • 每遇到一个 22，对于这个 22 后面的每个 33，它对答案的贡献都要从 2cnt2−12^{cnt2}-1 变为 2cnt2−1−12^{cnt2-1}-1，操作为 −1-1 再 ×12\times \frac{1}{2}。则遇到这个 22，对 ans1ans1 的总变化为 −cnt3-cnt3 再 ×12\times \frac{1}{2}。
  • 每遇到一个 11，此时的 ans1ans1 就是它对答案的变化，直接加到答案上即可。
预处理求出 ans1ans1 和 cnt3cnt3 的时间复杂度为 O(n)O(n)，遍历序列的复杂度为 O(nlog⁡m)O(n\log m)，其中 mm 为模数 998244353998244353。
总时间复杂度 O(nlog⁡m)O(n\log m)。

AC Code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...