首页 > 其他分享 >SS241107B. 子序列们(sub)

SS241107B. 子序列们(sub)

时间:2024-11-07 15:43:23浏览次数:1  
标签:SS241107B sub 删除 int rep 区间 序列 数字

SS241107B. 子序列们(sub)

题意

给你一个仅含有 \(0,1\) 的序列 \(A\),定义序列 \(B\) 为每个元素是序列 \(A\) 的一个子序列的序列,满足第 \(i\) 个元素的长度是 \(n-i+1\),且 \(\forall j > i\),第 \(j\) 个元素是第 \(i\) 个元素的子序列。

问有多少种本质不同的序列 \(B\),对 \(998244353\) 取模。\(n \le 400\)。

思路

刻画一下这个 \(B\),就是 \(B_1=A\),然后 \(B_i\) 为 \(B_{i-1}\) 删除一个数字形成。

考虑一个序列 \(S\) 删除一个数字,可以生成多少个本质不同的子序列,思考如何去重。

容易发现我们可以钦定删除的数字只可以对于一段连续的相同数字,删除最前面那个数字,这样可以保证不重不漏。

那么就可以写暴力了,直接暴力可以跑完 \(n=30\) 的数据,时间是 \(O(2^n poly(n))\) 的,但是显然长度为 \(i\) 的本质不同的子序列个数不到 \(2^n\) 次,究竟是多少次我也不知道。

不过由于我使用了 map 导致 TLE 了一个点,如果写哈希表应该就可以过吧?

特殊性质你手模一下就可以发现 \(a_i=0\) 直接输出 \(1\),\(a_{1 \sim \lfloor \frac{n}{2} \rfloor} =0,a_{\lfloor \frac{n}{2} \rfloor +1 \sim n} =1\) 的性质答案是 \(\binom{n}{\frac{n+1}{2}}\)。

然后我就往组合数上想了?

正解是,考虑给 \(A\) 的每个位置赋一个删除时间。考虑怎样的删除时间是不重不漏的。

在一段连续的相同的数字中,必须先删除了前面才能删除后面。如果两段相同的数字之间不同的数字在早的时间已经被删掉了,那么前面那段数字的删除时间就必须在后面那段之前。

也就是说对于两个相同的数字,要么他们之间有东西还没有删掉,要么前面的必须先删掉。

那么结论就是对于每个数字,其之前离它最近的删除时间大于它的数字必须与它不同。我们把之前离它最近的删除时间大于它的点叫做它的关系点。

然后区间 DP。

设 \(f_{l,r}\) 表示区间 \([l,r]\) 的方案。枚举区间时间最大的点 \(k \in [l,r]\),那么 \([k+1,r]\) 里面的点要么关系点在 \([k+1,r]\),要么关键点就是 \(k\),而 \(k\) 的时间是最大的,因此 \(k\) 涂什么颜色对后面有影响。而对于区间 \([l,k-1]\) 显然点 \(k\) 对它没有影响,而因为 \(k\) 是区间时间最大的点,所以 \(k\) 没有关键点。那么我们钦定 \(f_{l,r}\) 表示 \(l-1\) 的时间是最大值的时候区间 \([l,r]\) 的答案,这样就要求 \(k\) 的颜色不等于 \(l-1\) 的颜色。这样转移是正确的。

还要乘上一个组合系数,表示 \(r-l+1\) 个时间,最大的时间给了 \(k\),剩下的 \(r-l\) 个时间选 \(k-l\) 个给左边,剩下给右边。

实质是笛卡尔树吧,更好理解?

建立大根堆笛卡尔树。区间 \([1,n]\) 的答案可以由区间 \([1,k-1],[k+1,n]\) 的答案得到(枚举 \(k\)),那么 \(k\) 对区间 \([1,k-1]\) 没有影响,对于区间 \([k+1,n]\),其最大点是 \(p\),即笛卡尔树上 \(k\) 的右儿子是 \(p\),那么 \(k,p\) 不同颜色。\(p\) 的左儿子 \(q\),要求 \(q,k\) 也不同颜色。

也就是说区间最大点不能和区间左端点减 \(1\) 的位置同样颜色。

时间复杂度 \(O(n^3)\)。

code

代码非常好写,但是感觉这个转化,这个状态和转移比较难想。

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace coin_collecting_foundation {
    constexpr int N=407,mod=998244353;
    int add(int a,int b) { return a+b>=mod ? a+b-mod : a+b; }
    void _add(int &a,int b) { a=add(a,b); }
    int n;
    char a[N];
    int f[N][N];
    int c[N][N];
    void init() {
        c[0][0]=1;
        rep(i,1,n) {
            c[i][0]=1;
            rep(j,1,i) c[i][j]=add(c[i-1][j-1],c[i-1][j]);
        }
    }
    void solve() {
        rep(i,1,n+1) f[i][i]=a[i]!=a[i-1],f[i][i-1]=1;
        per(l,n,1) rep(r,l+1,n) rep(k,l,r) if(a[k]!=a[l-1]) _add(f[l][r],1ll*f[l][k-1]*f[k+1][r]%mod*c[r-l][k-l]%mod);
    }
    void main() {
        sf("%d%s",&n,a+1);
        init();
        solve();
        pf("%d\n",f[1][n]);
    }
}
int main() {
    #ifdef LOCAL
    freopen("my.out","w",stdout);
    #else 
    freopen("sub.in","r",stdin);
    freopen("sub.out","w",stdout);
    #endif
    coin_collecting_foundation :: main();
}

标签:SS241107B,sub,删除,int,rep,区间,序列,数字
From: https://www.cnblogs.com/liyixin0514/p/18532436

相关文章

  • 题解:[BZOJ2958] 序列染色
    ProblemLinkBZOJ2958序列染色题意给出一个长度为\(n\),由\(\ttB,W,X\)三种字符组成的字符串\(S\),你需要把每一个\(\ttX\)染成\(\ttB\)或\(\ttW\)中的一个。Solution字符串,染色,方案数,一眼\(dp\)。要求前半段是B,后半段是W。考虑容斥。\(f_{i,0/1},g_{i,......
  • #C. [GESP202409 三级] 平衡序列 核桃GESP考三级
    所以要从题目出发,优化代码思路是:1、前缀和,算出来累加和。2、通过tot*2==sum,判断是不是有相等的值。这个是数学上的优化。原错误的代码思路include<bits/stdc++.h>usingnamespacestd;intn;intmain(){  cin>>n;  for(inti=1;i<=n;i++)  { ......
  • Java中的序列化和反序列化是什么
    序列化是将对象转换为字节流的过程,这样对象可以通过网络传输、持久化存储或者缓存。Java提供了java.io.Serializable接口来支持序列化,只要类实现这个接口,就可以将该类的对象进行序列化。反序列化是将字节流重新转换为对象的过程,即从存储中读取数据并重新创建对象。其他应用......
  • CTF web新手解题——php反序列化 【ez_ez_unserialize】
    感受最大的就是:作为web新手,应速通并逐渐掌握php语言收获:从此题提高了我对代码的理解力【ez_ez_unserialize】NSSCTF{1ba5d701-3b8a-4a83-965d-7e912ef6f43b}分析存在__wakeup()魔术方法unserialize()会检查是否存在一个__wakeup()方法。如果存在,则会先调用__wakeup......
  • Understanding CAT ET Subscription for Work on 6NZ
    Ifyou’reconsideringusingCATCaterpillarET(ElectronicTechnician)forworkingonyour6NZengine,here’sabreakdownofhowthesubscriptionworksbasedondealerinformation: YearlySubscriptionModel-AnnualSubscription:CATEToperatesonayearl......
  • 代码随想录算法训练营第十六天|leetcode513.找树左下角的值、leetcode112.路径总和、l
    1leetcode513.找树左下角的值题目链接:513.找树左下角的值-力扣(LeetCode)文章链接:代码随想录视频链接:怎么找二叉树的左下角?递归中又带回溯了,怎么办?|LeetCode:513.找二叉树左下角的值_哔哩哔哩_bilibili思路:就是用一个东西存储result,使用后续遍历,如果遇到了最深的那一个值,就......
  • 在 Windows Server 2025 中,WSL2(Windows Subsystem for Linux 2)遇到无法使用镜像网络(mi
    在WindowsServer2025中,WSL2(WindowsSubsystemforLinux2)遇到无法使用镜像网络(mirrored)的问题,同时在使用virtioproxy模式时,子系统的IP与主机IP相同,可能是因为WSL2的网络配置与虚拟机的配置之间存在一些不匹配或不一致的设置。这里有几个可能的原因和解决方法:1. WSL......
  • 【算法】递归+深搜:106.从中序与后序遍历序列构造二叉树(medium)
    目录1、题目链接相似题目:2、题目3、解法函数头-----找出重复子问题函数体---解决子问题4、代码1、题目链接106.从中序与后序遍历序列构造二叉树(LeetCode)相似题目:105.从前序与中序遍历序列构造二叉树889.根据前序和后序遍历构造二叉树(LeetCode)2、题目3、解法......
  • 什么是java序列化?什么情况下需要序列化?
      序列化的定义Java序列化是为了保存各种对象在内存中的状态,并且可以把保存的对象状态再读出来。序列化是一种用于处理对象流的机制,它将对象的内容转换成一种可以在网络之间传输的形式。反序列化则是将这种形式的对象恢复成原来的对象。实现方式序列化是通过实现​​Seri......
  • 什么是java序列化?什么情况下需要序列化?
      序列化的定义Java序列化是为了保存各种对象在内存中的状态,并且可以把保存的对象状态再读出来。序列化是一种用于处理对象流的机制,它将对象的内容转换成一种可以在网络之间传输的形式。反序列化则是将这种形式的对象恢复成原来的对象。实现方式序列化是通过实现​​Seri......