本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-05 10:21:25

Link

发现应该枚举删除哪些字母，那么如何快速求出某一个删除方案的代价？

考虑拆贡献。对于一个位置 $r$ ，能与其产生代价的左边相邻点 $l$ 的个数为 $\mathrm{O(k)}$ 级别。

因为不能存在两个 $l$ 对应的字母相同。（因为这里如果需要靠前的 $l$ 与 $r$ 相邻就需要把靠后的 $l$ 删掉，但两者只能同时存在或同时被删除）

对于这个性质，可以用高维前缀和来预处理代价。所有包含在 $(l,r)$ 的字母都应被删除，还要保证 $l$ 和 $r$ 没被删除。容斥一下即可。

高维前缀和的原理是另一种处理前缀和的方式。二位前缀和一般采用容斥的方法来递推，但高维前缀和的维数太多，容斥就寄了。另一种方式是一位一位推，可以看代码。

值得注意的，两种方案不同当且仅当字符串不同，所以需要离散化。

code

const int N=2e5+5,M=24;

char s[N];

int v[M][M];

int frm[N][M];

int f[(1<<M)+5];

int w[M];

signed main(){
	int n=read(),m=read(),T=read();
	scanf("%s",s+1);
	for(int i=1;i<=m;i++)
		w[i]=read();
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			v[i][j]=read();
	for(int i=1;i<=n;i++){
		int nw=s[i]-'A'+1;
		for(int j=1;j<=m;j++)
			frm[i][j]=frm[i-1][j];
		pir tmp[M];
		for(int j=1;j<=m;j++)
			tmp[j]={-frm[i][j],j};
		sort(tmp+1,tmp+1+m);
		int S=0;
		for(int j=1;j<=m&&tmp[j].fi!=0;j++){
			f[S]+=v[tmp[j].se][nw];\/\/中间被删掉
			f[S|(1<<(nw-1))]-=v[tmp[j].se][nw];\/\/不能包含右端点
			f[S|(1<<(tmp[j].se-1))]-=v[tmp[j].se][nw];\/\/不能包含左端点
			f[S|(1<<(nw-1))|(1<<(tmp[j].se-1))]+=v[tmp[j].se][nw];\/\/同时包含被减了两次，加回来
			S|=(1<<(tmp[j].se-1));
			if(tmp[j].se==nw)\/\/不加也行
				break;
		}
		frm[i][nw]=i;
	}
	int all=(1<<m)-1;
	for(int i=1;i<=m;i++)\/\/先枚举维再枚举数字，一维一维推，不重。
		for(int k=0;k<=all;k++)
			if(k&(1<<(i-1)))
				f[k]+=f[k^(1<<(i-1))];
	int ans=0;
	for(int k=0;k<all;k++){
		int sum=0;
		for(int l=k;l;l^=lowbit(l))
			sum+=w[__lg(lowbit(l))+1];\/\/其实这个代价可以看作是删除方案包含了这一个字符，可以直接一起与前面的容斥处理
		ans+=f[k]+sum<=T;
	}print(ans),pc('\n');
	return 0;
}