比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAWWWWWWWWWWWW
题目名称 Moo Decomposition 最终得分 52
用户昵称 王潇翊 运行时间 1.017 s
代码语言 C++ 内存使用 9.56 MiB
提交时间 2026-07-06 10:10:09
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int M = 1e9 + 7;
long long l,a[N],ans = 1,k,n,cnt;
string s;
long long h(long long x,long long y)
{
    long long sum = 1;
    while (y > 0)
    {
        if (y & 1)
        {
            sum *= x;
            sum %= M;
        }
        x *= x;
        x %= M;
        y >>= 1;
    }
    return sum;
}
int main()
{
    freopen("Moo.in","r",stdin);
    freopen("Moo.out","w",stdout);
    cin >> k >> n >> l >> s;
    for (int i = 2;i <= n;i++)
    {
        a[i] = i * (i - 1);
        a[i] %= M;
    }
    for (int i = n - 1;i >= 0;i--)
    {
        if (s[i] == 'O')
        {
            cnt++;
        }
        else
        {
            if (k == 2)
            {
                ans *= a[cnt] / 2;
            }
            else if (k == 1)
            {
                ans *= cnt;
            }
            else
            {
                for (long long j = cnt;j >= cnt - k + 1;j--)
                {
                    if (j % k == 0)
                    {
                        ans *= (j / k);
                    }
                    else
                    {
                        ans *= j;
                    }
                    ans %= M;
                }
            }
            ans %= M;
            cnt -= k;
        }
    }
    cout << h(ans,l);
    return 0;
}