#C231108B. 子序列(sub)

前言（Front talk)

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

网址（Website）

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

题解 - 子序列(sub) - Super

题目（Problem）

给定一个长为的字符串。求有多少个长为的字符串序列，满足，为空，长度为，且，是的子序列。

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

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

对于的数据，满足，答案对取模。

题解（Solution）

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

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

代码（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;
}