牛客练习110-D

题目链接：https://ac.nowcoder.com/acm/contest/54129/D

比赛的时候dp状态方程想错了，一直在做无用攻。

思路：设\(dp[i]\)为用了i次魔法的期望值，递推地做即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
map<char,int>M;
long long qmod(long long x,long long y){
    long long res = 1;
    while(y){
        if (y&1) res = res*x%mod;
        y = y>>1;
        x = x*x%mod;
    }
    return res;
}
long long dp[2000];
int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    M['y'] = 1;
    M['w'] = 1;
    M['i'] = 1;
    M['a'] = 1;
    M['k'] = 1;
    long long v1 = 5*qmod(26,mod-2)%mod;
    long long v2 = 21*qmod(26,mod-2)%mod;
    long long t = qmod(n,mod-2);
    for (int i=0;i<n;i++){
        if (M.count(s[i])) dp[0]++;
    }
    for (int i=1;i<=k;i++){
        dp[i] = dp[i-1];
        dp[i] = (dp[i]-dp[i-1]*t%mod*v2%mod+mod)%mod;
        dp[i] = (dp[i]+(n-dp[i-1]+mod)*t%mod*v1%mod)%mod;
    }
    cout<<dp[k]<<'\n';
}