<h2>题目大意</h2>

给出一个由前 $k$ 个大写字母组成的字符串，每次可以花费 $t_i$ 代价删去该字符串中所有的第 $i$ 个大写字母，一个字符串的代价为该字符串每对相邻字符的代价，给出 $k\times k$ 的矩阵表示两个相邻的大写字母的代价矩阵，问有多少种删除方案使得删除的代价以及剩余字符串的代价之和不超过$T$，注意剩余字符串需非空。
其中 $n \leq 2 \times 10^5,k \leq 22,T \leq 2 \times 10^9$

<h2>题解</h2>

这个题上来就没思路了。。还是靠 Alpha 巨佬教我的
首先考虑如果我们处理出 $f_S$ 表示删除 $S$ 中的字母后的序列的价值，那么就可以直接得出答案了。但是可惜暴力算是 $O(n2^k)$ 的。
考虑优化：我们首先可以看出一个操作的价值取决于使用操作的价值和剩下的东西的价值，我们其实只需要专注于求后者就可以了。（前者可以简单前缀和出来）
我们考虑两个字符 $s_i,s_j$ ，设 $M$ 为 $s_{i+1\cdots j-1}$ 的字符集，这两个字符不相邻的条件是 $s_i \in M$ 或 $s_j \in M$，所以我们考虑有序对 $(i,j)$ 表示 $s_i$ 和 $s_j$ 相邻的数量，这个数量是 $O(nk)$ 的。
我们考虑枚举这些对，将答案贡献进去。考虑一个删除操作是若干个 $M$ 的并，我们对于一个删除操作 $S$ 可以枚举所有的 $M \subseteq S$ 然后计算相邻对的贡献，但是考虑到这样可能会重复计算：例如现在 $M \not\in x$ 但是 $S \in x$ 就会错误的将 $x$ 的相邻贡献计算入答案。所以我们在统计 $M$ 的时候需要做一步容斥，大概代码是

f[pre[x]] += mx;
f[pre[x]|(1<<x)] -= mx;
f[pre[x]|(1<<y)] -= mx;
f[pre[x]|(1<<x)|(1<<y)] += mx;

然后做高维前缀和就不会出现计算到不应该的位置的问题了，这样就解决了这个问题。(又是一道我估计这辈子都不会的题)

/*
 * Author: RainAir
 * Time: 2019-08-28 16:24:39
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 2e5 + 5;
const int MAXK = 22+2;

int n,k,T;
char str[MAXN];
int pre[MAXN],t[MAXK],mMAXK;
int f[(1<<MAXK)+3];

inline void FMT(){
    FOR(i,0,k-1){
        FOR(S,0,(1<<k)-1){
            if(((1<<i)&S))
                f[S] += f[S^(1<<i)];
        }
    }
}

signed main(){
    scanf("%lld%lld%lld",&n,&k,&T);
    scanf("%s",str);
    FOR(i,0,k-1) scanf("%lld",t+i);
    FOR(i,0,k-1) FOR(j,0,k-1) scanf("%lld",&mi);
    FOR(i,0,k-1) f[1<<i] = t[i]; // init
    CLR(pre,-1);int S = 0;
    FOR(i,0,n-1){
        int y = str[i]-'A';
        S |= (1<<y);
        FOR(x,0,k-1){
            if(pre[x] >= 0){
                if(!(pre[x]&(1<<x)) && !(pre[x]&(1<<y))){
                    f[pre[x]] += mx;
                    f[pre[x]|(1<<x)] -= mx;
                    f[pre[x]|(1<<y)] -= mx;
                    f[pre[x]|(1<<x)|(1<<y)] += mx;
                }
            }
            pre[x] |= (1<<y);
        }
        pre[y] = 0;
    }
    FMT();int ans = 0;
    FOR(i,0,(1<<k)-1){
        if((i&S) == i && f[i] <= T && i != S) ans++;
    }
    printf("%lldn",ans);
    return 0;
}