比赛 26暑假集训模拟赛3 评测结果 AAAAAAAAAAAAAWWWWWWWWWWWW
题目名称 Moo Decomposition 最终得分 52
用户昵称 zcx 运行时间 0.857 s
代码语言 C++ 内存使用 9.13 MiB
提交时间 2026-07-06 10:08:19
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;

int k,n,l,sum = 0;

int a[N];

int qk(int val,int p){
    int tot = val,ans = 1;
    for(int i = 0;i <= 63;i++){
        if((p>>i) & 1) ans *= tot;ans %= mod;
        tot *= tot;tot %= mod;
    }
    return ans;
}

signed main()
{
    freopen("Moo.in","r",stdin);
    freopen("Moo.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>k>>n>>l;
    for(int i = 1;i <= n;i++){
        char c;cin>>c;
        if(c == 'M') a[i] = 1;
        else a[i] = 2;
    }
    int ans = 1;
    for(int i = n;i >= 1;i--){
        if(a[i] == 2){
            sum++;
            continue;
        }
        int C = (k == 1? sum: sum * (sum - 1) / 2) % mod;
        ans *= C;
        ans %= mod;
        sum -= k; 
    }
    cout<<qk(ans,l)<<endl;
    return 0;
 }