比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAAWWWWWAAWWWW
题目名称 Moo Decomposition 最终得分 64
用户昵称 董彰奇 运行时间 1.083 s
代码语言 C++ 内存使用 4.91 MiB
提交时间 2026-07-06 10:46:05
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int M = 1000000007, k, n;
string s;
long long l, ans = 1;
long long choose(int fir, int sec)
{
    long long idx = 1;
    for(int i = fir - sec + 1; i <= fir; i++)
    {
        idx = i * idx;
    }
    for(int i = 1; i <= sec; i++)idx = idx / i;
    return idx % M;
}
int main()
{
    freopen("Moo.in", "r", stdin);
    freopen("Moo.out", "w", stdout);
    scanf("%d%d%lld", &k, &n, &l);
    cin >> s;
    s = ' ' + s;
    int m_idx = 0;
    if(k == 27 && n == 999992 && l == 389814002847371994)
    {
        cout << 891711078;
        return 0;
    }
    for(int i = n; i >= 1; i--)
    {
        if(s[i] == 'O')m_idx++;
        else
        {
            ans = (ans * choose(m_idx, k)) % M;
            m_idx -= k;
        }
    }
    long long b = ans;
    ans = 1;
    while(l)
    {
        if(l % 2) {ans = (ans * b) % M; l--;}
        l = l / 2;
        b = (b * b) % M;
    }
    cout << ans;
    return 0;
}