嘤嘤的可爱（easy）

看到题解说没想到高复杂度的解法

于是我来分享一下菜鸡的$O(n\cdot k)O(n\backslash cdot\; k)$的解法吧

$d{p}_{a,k}dp\_\{a,k\}$表示有a个可爱字符情况下施法$kk$次得到的期望

状态转移方程从代码里可以看出来，就不赘述了，为了方便写的记忆化搜索

#include<bits/stdc++.h>
using namespace std;
long long n,k;
const long long mod=1e9+7;
long long dp[2023][2023];
int f[200];
void exgcd(long long a, long long b, long long& x, long long& y) { 
  if (b == 0) {
    x = 1, y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
long long inv(long long a){
	long long x,y;
	exgcd(a,mod,x,y);
	return (x%mod+mod)%mod;
}
long long invn,inv26;
long long dfs(int a,int k){
    if(dp[a][k]!=-1)return dp[a][k];
    if(k==0)return a;
    dp[a][k]=dfs(a,k-1)*a%mod*invn%mod*5*inv26%mod;
    dp[a][k]%=mod;
    if(a>0)dp[a][k]+=dfs(a-1,k-1)*a%mod*invn%mod*21%mod*inv26%mod;
    dp[a][k]%=mod;
    if(a<n)dp[a][k]+=dfs(a+1,k-1)*(n-a)%mod*invn%mod*5%mod*inv26%mod;
    dp[a][k]%=mod;
    dp[a][k]+=dfs(a,k-1)*(n-a)%mod*invn%mod*21%mod*inv26%mod;
    dp[a][k]%=mod;
    return dp[a][k];
}
int main(){
    f['y']=f['k']=f['a']=f['w']=f['i']=1;
    string s;
    memset(dp,-1,sizeof(dp));
    int a=0,b=0;
    cin>>n>>k;
    invn=inv(n);
    inv26=inv(26);
    cin>>s;
    for(auto c:s)
        if(f[c])a++;
    cout<<dfs(a,k)<<endl;
}