嘤嘤的可爱（hard）

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

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

C++(g++ 7.5.0) 解法, 执行用时: 30ms, 内存消耗: 3120K, 提交时间: 2023-04-14 23:02:23

#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;
}

C++(clang++ 11.0.1) 解法, 执行用时: 9ms, 内存消耗: 1624K, 提交时间: 2023-04-14 20:12:09

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll ksm(ll x,ll p){
	ll res=1;
	for(;p;p>>=1,x=x*x%mod) if(p&1) res=res*x%mod;
	return res;
}
ll inv(ll x){
	return ksm(x,mod-2);
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	ll n,m;
	cin>>n>>m;
	string s;
	cin>>s;
	ll x=0;
	for(int i=0;i<n;i++) if(s[i]=='y'||s[i]=='k'||s[i]=='a'||s[i]=='w'||s[i]=='i') x++;
	ll k=(mod-inv(n)+1)%mod;
	ll b=5*inv(26)%mod;
	x=(ksm(k,m)*x+b*(1-ksm(k,m))%mod*inv(1-k)%mod+mod)%mod;
	cout<<x;
}

pypy3 解法, 执行用时: 105ms, 内存消耗: 49388K, 提交时间: 2023-04-14 19:25:02

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)

详情