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