| 比赛 |
26暑假集训模拟赛3 |
评测结果 |
AAAAAAAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
Moo Decomposition |
最终得分 |
100 |
| 用户昵称 |
ChenBp |
运行时间 |
2.983 s |
| 代码语言 |
C++ |
内存使用 |
12.33 MiB |
| 提交时间 |
2026-07-06 08:41:54 |
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1e6+6;
const ll mod=1e9+7;
string s;
int a[N];
ll ksm(ll x,ll y){
x%=mod;
ll res=1;
while(y){
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int jc[N],ni[N];
int main() {
freopen("Moo.in","r",stdin);
freopen("Moo.out","w",stdout);
ll k,n,l;
cin>>k>>n>>l>>s;
s=" "+s;
jc[0]=ni[0]=1;
for(ll i=1;i<=n;i++){
jc[i]=jc[i-1]*i%mod;
ni[i]=ksm(jc[i],mod-2);
}
ll ans=1;
for(int i=n; i>=1; i--) {
a[i]=a[i+1];
if(s[i]=='O') a[i]++;
else {
ans*=1ll*jc[a[i]]*ni[k]%mod*ni[a[i]-k]%mod;
// cout<<jc[a[i]]<<" "<<ni[k]<<" "<<ni[a[i]-k]<<endl;
ans%=mod;
a[i]-=k;
}
}
// cout<<ans<<endl;
ans=ksm(ans,l);
cout<<ans;
return 0;
}