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