| 比赛 |
26暑假集训模拟赛3 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
Moo Decomposition |
最终得分 |
100 |
| 用户昵称 |
KKZH |
运行时间 |
2.769 s |
| 代码语言 |
C++ |
内存使用 |
14.89 MiB |
| 提交时间 |
2026-07-06 10:10:15 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
const int mod=1e9+7;
int all[N],inv[N];
int k,n,l;
string s;
int ksm(int x,int y){
int cnt=x,res=1;
while(y>0){
if(y%2==1)
res=(cnt*res)%mod;
cnt=(cnt*cnt)%mod;
y=y/2;
}
return res;
}
int c(int x,int y){
if(x==y) return 1;
return (all[y]*inv[y-x])%mod*inv[x]%mod;
}
signed main(){
freopen("Moo.in","r",stdin);
freopen("Moo.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>k>>n>>l>>s;
all[0]=1,inv[0]=1;
for(int i=1;i<=n;i++){
all[i]=(all[i-1]*i)%mod;
inv[i]=ksm(all[i],mod-2)%mod;
// cout<<all[i]<<" "<<inv[i]<<'\n';
}
int cnt=0,ans=1;
for(int i=s.size()-1;i>=0;i--){
if(s[i]=='O') cnt++;
else{
ans=(ans*c(k,cnt)%mod)%mod;
cnt-=k;
}
// cout<<ans<<" ";
}
cout<<ksm(ans,l)<<'\n';
return 0;
}