E - Swap
首先我们注意到，加入我们想要一个串T，那么最小步数是唯一的。
设\(f[i][j][e][y]\)表示当前到第i个字符，一共用掉了j次，前面有e个E，y个Y。
然后转移即可，因为k不会大于\(n^2\)，预处理第x个字符的位置即可。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
const int N=30+5;
const int M=1000;
ll f[N][M][N][N];
int n,tot,x,pos,z;
char s[N];
int a[N],t[N][4],p[N][4],k;
int main() {
// #ifdef LOCAL
// freopen("data.in","r",stdin);
// freopen("out.txt","w",stdout);
// #endif
scanf("%s",s+1);
n=strlen(s+1);
fo(i,1,n) {
if (s[i]=='K') a[i]=0;
if (s[i]=='E') a[i]=1;
if (s[i]=='Y') a[i]=2;
}
scanf("%d",&tot);
tot=min(tot,n*(n-1)/2);
fo(i,1,n) {
fo(j,0,2) t[i][j]=t[i-1][j];
t[i][a[i]]++;
p[t[i][a[i]]][a[i]]=i;
}
f[0][0][0][0]=1;
fo(i,0,n-1) {
fo(j,0,tot) {
fo(e,0,min(i,t[n][1])) fo(y,0,min(i-e,t[n][2])) {
k=i-e-y;
if (k<0 || k>t[n][0]) continue;
if (k+1<=t[n][0]) { // k
pos=p[k+1][0];
z=max(0,t[pos][1]-e)+max(0,t[pos][2]-y);
if (z+j<=tot) f[i+1][z+j][e][y]+=f[i][j][e][y];
}
if (e+1<=t[n][1]) { //e
pos=p[e+1][1];
z=max(0,t[pos][0]-k)+max(0,t[pos][2]-y);
if (z+j<=tot) f[i+1][z+j][e+1][y]+=f[i][j][e][y];
}
if (y+1<=t[n][2]) { //y
pos=p[y+1][2];
z=max(0,t[pos][0]-k)+max(0,t[pos][1]-e);
if (z+j<=tot) f[i+1][z+j][e][y+1]+=f[i][j][e][y];
}
}
}
}
ll ans=0;
fo(i,0,tot) ans+=f[n][i][t[n][1]][t[n][2]];
printf("%lld",ans);
return 0;
}