考场上傻逼没做出来这题，于是来写个题解
首先发现复杂度在 (2^k imes k) 的时候是能过的（
考虑 dfs 每个字符的删除状态，发现瓶颈在于如何求出删除后相邻两个字符的贡献。
这个贡献可以先考虑一个 naive 的 (n^2) 预处理，枚举两个点对 ((i,j)) ，发现只有在 ([i+1,j-1]) 字符全部删除的时候才能造成贡献，于是算一下 ([i+1,j-1]) 字符的状态。然而，点对 ((i,j)) 也可以对以 ([i+1,j-1]) 字符为子集的删除状态造成贡献。对于这部分的贡献直接上 FWT 即可。
然而还有一个限制是 (i) 字符和 (j) 字符不能被删除任意一个，套上一个小容斥即可。具体看代码。
考虑怎么把 (n^2) 优化。枚举 (i) 的过程中，同时有两个点 (j_1),(j_2) 满足 (ch_{j_1}=ch_{j_2}) 时，显然这个 (j_2) 是没有用处的。
所以每个字符只需要找一遍即可，也就是说我们可以以 (mathcal{O}(nk)) 的复杂度去预处理。
时间复杂度为 (mathcal{O}(2^k imes k))，瓶颈在于 FWT。顺便一提 FWT 在 (kle 22) 的时候都是能过的，(k=23) 就不行。自己sb觉得过不去就没写头铁去刚另一题
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define poly vector<int>
typedef long long ll;
const int N=2e5+5,M=30;
int chr[N],R[N];
ll b[M][M],a[M],val[1<<22],vv[M];
int vis[M],n,k,T,ans,all;
void dfs(int x,int st,ll sum){
if(sum>T) return;
if(x==k) return (void)(ans+=(sum+val[st]<=T && st!=all));
if(vis[x]) dfs(x+1,st|(1<<x),sum+a[x]);
dfs(x+1,st,sum+vv[x]);
}
poly pos[M];
pii p[M];int cnt;
void FWT(ll *f,int n){
for(int p=2;p<=n;p<<=1){
int len=p>>1;
for(int i=0;i<n;i+=p)
for(int st=i;st<i+len;++st)
f[st+len]+=f[st];
}
}
signed main(){
//freopen("untitled.in","r",stdin);
//freopen("untitled.out","w",stdout);
cin>>n>>k>>T;char ch;
for(int i=1;i<=n;++i){
cin>>ch;
chr[i]=ch-'A';
vis[chr[i]]=1;
all|=(1<<chr[i]);
pos[chr[i]].push_back(i);
}
for(int i=0;i<k;++i)
sort(pos[i].begin(),pos[i].end());
for(int i=0;i<k;++i)
cin>>a[i];
for(int i=0;i<k;++i)
for(int j=0;j<k;++j)
cin>>b[i][j];
for(int i=2;i<=n;++i)
if(chr[i]==chr[i-1]) vv[chr[i]]+=b[chr[i]][chr[i-1]];
else R[i]=i+1;
for(int i=1;i<n;++i){
if(chr[i]==chr[i+1]) continue;
int st=0;
cnt=0;
for(int j=0;j<k;++j)
if(!pos[j].size() || pos[j].back()<=i) continue;
else{
int Pos=lower_bound(pos[j].begin(),pos[j].end(),i)-pos[j].begin();
if(chr[i]==j && pos[j].size()>1) p[++cnt]=make_pair(pos[j][Pos+1],j);
else p[++cnt]=make_pair(pos[j][Pos],j);
//cout<<i<<" "<<char(j+'A')<<" "<<pos[j][Pos]<<endl;
}
sort(p+1,p+cnt+1);
for(int j=1;j<=cnt;++j){
if(i==p[j].fi) continue;
int tmp=b[chr[i]][p[j].se];
// cout<<i<<" "<<p[j].fi<<" "<<char(p[j].se+'A')<<" "<<tmp<<" "<<st<<" shabi
";
val[st]+=tmp;
val[st|(1<<chr[i])]-=tmp;
val[st|(1<<p[j].se)]-=tmp;
val[st|(1<<p[j].se)|(1<<chr[i])]+=tmp;
if(p[j].se==chr[i]) break;
st|=(1<<p[j].se);
}
}
// for(int i=0;i<1<<k;++i)
// cout<<val[i]<<" ";cout<<endl;
FWT(val,(1<<k));
// for(int i=0;i<1<<k;++i)
// cout<<val[i]<<" ";cout<<endl;
dfs(0,0,0);
cout<<ans;
return 0;
}