#C231108B. 子序列(sub)

标签（Label）

分治
动态规划
逆向思维

前言（Front talk)

$\qquad$动态规划的题都需要特殊理解，那彻底理解后，这道题对我的提升可不小，明天准备去凹 $1-2$ 道难题，再次提升代码能力，今天的 $T4$ 就很好。ヾ(•ω•`)o

网址（Website）

题目详情 - 子序列(sub) - Super

题解 - 子序列(sub) - Super

题目（Problem）

给定一个长为 $n$ 的 $01$ 字符串 $S$ 。求有多少个长为 $n$ 的字符串序列，满足 $A_{0}=S$，$A_{n}$ 为空，$A_{i}$ 长度为 $n-i$，且 $\forall 1 \leq i \leq n$，$A_{i}$ 是 $A_{i-1}$ 的子序列。

定义 $S$ 是 $T$ 的子序列，当且仅当可以从 $T$ 中删去一些字符使之变为 $S$ 。

理解样例：输入：3 010；输出：5。

对于 $100 %$ 的数据，满足 $1 \leq n \leq 400$ ，答案对 $10^{9}+7$ 取模。

题解（Solution）

写一些刚看题解时不理解的点：

题目大意就是将序列 $a[i]$ 每次删除一个位置，每删除一次就会有不同的序列生成，求最终的删除方案数，按理说方案数应该是 $O(n!)$ ，但是相同的序列重复计算的贡献需要删掉。例如 $10111$ 删去第四个 $1$ 或删去第五个 $1$ 贡献是相同的，需要删去。
那么题解第 $2$ 段的意思就仿佛清晰明了了，将每一部分的 $00\dots$ 或 $11\dots$ 看作一个整体，每次删除只删除 $a[i]$ 序列其中一部分的末尾，那么方案数一定不会计算重复。
按正常情况来理解，如果出现 $10001$ 这个序列，在不去重的情况下，删除后会出现五种情况： $@0001$ ，$1@001$，$10@01$ ，$100@1$ ，$1000@$ （其中 $@$ 代表删除的位置），对于删除最左边的 $1$ 或者删除最右边的 $1$ 方案数接不会计算重复，在此略去，仅考虑中间 $3$ 个 $0$ 的情况，我们固定只删除最右边的 $0$ ，那么对于 $0$ 不在最右边的情况则一定不能删去，因此在枚举到删除了左边的 $0$ 的情况时，我们可以直接特判，不去删除那些 $0$ 。
那现在就到了 $How$ 的问题。~~（我就直接抄题解了）~~先考虑区间 $\mathrm{dp}$ ，枚举一个区间最后一个删除的位置。这样之前的删除中，左右两边就独立了，可以分别计数，最后合并时乘上一个组合数。*再考虑限制是什么。如果这个区间最后删除的是 $k$，那么在删除它时，它后面的字符一定是 $s_{r+1} $ ，那么直接判断 $s_{k}$ 是否等于 $s_{r+1}$ 就行了。
至于求组合数，因为左右操作独立，但是删除的位置却是随机的，因此要在 $r-l+1-1$ （减去删除的那个元素）的总操作数中选择 $i-l$ 种操作来执行左区间删除操作，剩下的执行右区间，方案数 $C_{r-l}^{i-l}$ 。

代码（Code）

我的代码（逆元法）

#include<bits/stdc++.h> 
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int mod = 1000000007;
const int N = 405;

inline int ksm(int x,int k){
	int res=1;while(k){
		if(k&1) res=res*x%mod;
		x=x*x%mod,k>>=1;
	}return res;
}
int bas[N],inv[N];

inline int C(int n,int m){
	if(m>n || m<0) return 0;
	if(m==0 || n==m) return 1;
	return bas[n]*inv[m]%mod*inv[n-m]%mod;
}

char a[N];
int n,f[N][N];

inline int dfs(int l,int r){
	if(l>r)  return 1;
	if(f[l][r]!=-1) return f[l][r];
	int ans=0;For(i,l,r){
		if(r==n || a[i]!=a[r+1])
			ans=(ans+dfs(l,i-1)*dfs(i+1,r)%mod*C(r-l,i-l)%mod)%mod;
//			cout<<C(r-l,i-l)<<'\n';
	}return f[l][r]=ans;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("sub");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout); 
	cin>>n>>(a+1);
	
	memset(f,-1,sizeof(f));
	
	For(i,1,n) bas[i]=i==1?1:bas[i-1]*i%mod;
//	cout<<bas[i]<<' ';cout<<'\n';
	inv[n]=ksm(bas[n],mod-2);
	Rof(i,n-1,1) inv[i]=inv[i+1]*(i+1)%mod;
//	cout<<inv[i]<<' ';cout<<'\n';
	cout<<dfs(1,n)<<'\n';
	return 0;
}

题解代码（组合数递推法）

#include <iostream>
#include <cstdio>
#include <cstring>
#define mod 1000000007
using namespace std;
int n;
char s[405];
int C[405][405];
int f[405][405];
int dfs(int l,int r){
	if (l>r)return 1;
	if (f[l][r]!=-1)return f[l][r];
	int ans=0;
	for (int i=l;i<=r;i++)
		if (r==n||s[i]!=s[r+1])
			ans=(ans+1ll*C[r-l][i-l]*dfs(l,i-1)%mod*dfs(i+1,r))%mod;
	return f[l][r]=ans;
}
int main(){
	freopen("sub.in","r",stdin);
	freopen("sub.out","w",stdout);
	cin>>n;
	for (int i=0;i<=n;i++)C[i][0]=1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	scanf("%s",s+1);
	memset(f,-1,sizeof(f));
	cout<<dfs(1,n)<<endl;
	return 0;
}