P4958 [COCI2017-2018#6] Mate 题解

分析

考虑 DP。

先考虑 \(A\) 的答案。定义状态函数 \(f_{i,j}\) 表示在子串 \(S_{1 \dots i}\) 中选 \(j\) 个，且第 \(S_i\) 必选的方案数。则有：\(f_{i,j}=C_{i-1}^{j-1}\)。

再考虑 \(B\) 的答案。枚举每一个位置 \(x\)。令 \(sum_x=\sum\limits_{i=1}^{x-1}f_{i,n-1}[S_i=A]\)。则答案为：\(\sum\limits_{x=1}^{|S|}sum_x[S_x=B]\)。复杂度 \(O(Q|S|+|S|^2)\)。

优化对 \(B\) 的答案的求法，考虑预处理。定义状态函数 \(g_{i,j}\) 在位置 \(x\) 时表示 \(\sum\limits_{k=1}^{x}f_{k,j}[S_k=i]\)（和上面的 \(sum_x\) 差不多）；定义状态函数 \(w_{i,j,k}\) 在位置 \(x\) 时表示当前对于 \(B=i,A=j,n=k\) 时的答案。则最终答案为：\(w_{B,A,n}\)。转移就很暴力了，因为定义的原因，在可能出现 \(A=B\) 的情况下先转移 \(w\)，即有：\(w_{i,j,k}=w_{i,j,k}+g_{j,k-1}\)。对于 \(g\) 的转移，有：\(g_{i,j}=g_{i,j}+f_{m_i,j}\)（其中 \(m_i\) 表示当前下标）。\(i\) 枚举时已知，只需要另外枚举 \(j,k\) 就行了。复杂度 \(O(Q+a|S|^2)\)，有 \(a=26\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define PII pair<int,int>
#define x first
#define y second

il int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}

const int N=2005,M=30,p=1e9+7;
char s[N];int len;
int f[N][N],g[N][N];
int sum[M][M][N];
int c[N][N];
int q;
char t[N];

il int C(int x,int y){
	if(!y||x==y) return 1;
	if(~c[x][y]) return c[x][y];
	return c[x][y]=(C(x-1,y)+C(x-1,y-1))%p;
}
il void solve(){
	memset(c,-1,sizeof(c));
	scanf("%s",s+1),len=strlen(s+1);
	for(re int lon=1;lon<=len;++lon)
	for(re int i=lon;i<=len;++i)
		f[i][lon]=C(i-1,lon-1);
	for(re int i=1;i<=len;++i){
		for(re int n=1;n<=i;++n)
		for(re int j=0;j<26;++j) sum[s[i]-'a'][j][n]=(sum[s[i]-'a'][j][n]+g[j][n-1])%p;
		for(re int n=1;n<=i;++n) g[s[i]-'a'][n]=(g[s[i]-'a'][n]+f[i][n])%p;
	}
	q=read();
	while(q--){
		int n=read();
		scanf("%s",t+1);
		printf("%lld\n",sum[t[2]-'a'][t[1]-'a'][n]);
	}
	return ;
}

signed main(){
	solve();
	return 0;
}

优化一下长这样：

#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline

il int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}

const int N=2001,M=27,p=1e9+7;
char s[N],t[2];
long long g[N][N],f[M][M][N];
long long c[N][N];
int q,len,n;

signed main(){
	scanf("%s",s+1),len=strlen(s+1);
	for(re int i=0;i<=len;++i)
    for(re int j=0;j<=i;++j)
        if(!j) c[i][j]=1;
        else c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
	for(re int i=1;i<=len;++i)
	for(re int n=i;n>=1;--n){
		for(re int j=0;j<26;++j) f[s[i]-'a'][j][n]=(f[s[i]-'a'][j][n]+g[j][n-1])%p;
		g[s[i]-'a'][n]=(g[s[i]-'a'][n]+c[i-1][n-1])%p;
	}
	q=read();
	while(q--) n=read(),scanf("%s",t),printf("%lld\n",f[t[1]-'a'][t[0]-'a'][n]);
	return 0;
}

注：其实 \(f_{i,j}\) 可以直接用 \(C_{i-1}^{j-1}\) 代替。