嘤嘤的可爱（easy）

第一行给出两个整数 $n(1 \le n \le 1024),k(0 \le k \le 1024)$ ，分别表示嘤嘤的字符串的长度和可以使用魔法次数。

第二行给出一个长度为 $n$ 的只由小写字母组成的字符串 $s$ ，表示嘤嘤的字符串。

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 476K, 提交时间: 2023-04-15 14:18:45

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

const LL M = 1e9+7;

int main(){
	LL n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	auto ksm = [&](LL x,LL y){
		LL ans = 1;
		while(y){
			if(y&1) ans = ans * x % M;
			x = x * x % M;
			y >>= 1;
		}
		return ans;
	};
	LL ans = 0;
	LL p0 = 1 * ksm(n-1 , k) * ksm(ksm(n,k) , M-2) % M;
	LL t = 5 * ksm(26 , M-2) % M;
	LL p1 = (1 - p0 + M) % M;
	for(auto &i : s){
		if(i=='y' || i=='k' || i=='a' || i=='w' || i=='i') ans += p0;
		ans += p1*t;
		ans %= M;
	}
	cout<<ans<<endl;
	return 0;
}

pypy3 解法, 执行用时: 78ms, 内存消耗: 22460K, 提交时间: 2023-04-14 19:24:50

import sys
import os
import io

input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.buffer.write


def print(*values, sep=" ", end="\n"):
    output(sep.join(str(value) for value in values).encode())
    output(end.encode())


mod = 1000000007
n, k = map(int, input().split())
p = pow(1 - pow(n, mod - 2, mod), k, mod)
q = 5 * pow(26, mod - 2, mod)
ans = (1 - p) * q * n % mod
for c in input().strip():
    if c in b"kawyi":
        ans += p
print(ans % mod)

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 436K, 提交时间: 2023-04-15 08:05:30

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll P=1e9+7;
ll ni(ll x)
{
	ll re=1;
	for (int y=P-2;y;y>>=1,x*=x,x%=P) if(y&1)re*=x,re%=P;
	return re;
}
ll a;
string s;
int main()
{
	ll n,k;
    cin>>n>>k;
	cin>>s;
    for (auto c : s) if (c=='y'||c=='k'||c=='a'||c=='w'||c=='i') a++;
	while (k--) a=((a+5*ni(26)%P-a*ni(n)%P)%P+P)%P; 
	cout<<a<<endl;
    return 0;
}

详情