题解：P12028 [USACO25OPEN] Moo Decomposition

· · 题解

题解：P12028 [USACO25OPEN] Moo Decomposition

视频题解。

此题重点：看数据范围。

Preface

第一场 USACO \text{\color{gold}Au}，481 pts，本来自我感觉良好，及格线一出，850！？直接喷血而亡。

不过第一题完全没有 25 年金组该有的难度，后两题也偏简单，及格线这么高倒是可以理解。

Problem

P12028

Solution

首先 USACO 估计是脑子没转过来，居然把 L 定了个 10^{18}，乍一看很吓人，听起来也很厉害。但是稍微想想就知道，L 这么大只有一种可能，就是每一段互相独立，最后结果用快速幂乘起来。接下来就好算了。

但是这毕竟是一篇题解，考场上可以直接开始写代码了，但我们这里还是得证明一下的。

首先发现题目给定了一定至少有一个解，说明整个串中的 M 和 Ｏ 的数量一定是 1 比 K 的，说明每一段中 M 和 Ｏ 的比例也是一定的。所以从最后一段开始匹配，发现每匹配完一段一定是一个 M 和 Ｏ 都不会剩下。也就是说每一段匹配是都是完全独立的。

现在我们就只需要求出匹配一段的方案数，再算个快速幂就行了。

如何求出每一段匹配方数？我们从后往前遍历。记录 cnt 表示目前有几个未匹配的 O，每遇到一个 M 就把答案乘上 {cnt \choose K}，也就是所有 cnt 个 O 里选出 K 个与这个 M 匹配的方案数，然后 cnt = cnt - K，因为现在就只剩 cnt - K 个 O 了。而遇到一个 O 就直接 cnt + 1。

现在最后一个问题，如何计算 {cnt \choose K}？直接预处理一个阶乘数组 fac_i 表示 i !，根据排列组合的定义 {cnt \choose K} 就是

\dfrac{cnt !}{K! \cdot (cnt - K)!}

但是由于要取余做除法自然就需要求逆元，我既然都写了快速幂就直接用了费马小定理。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k, n, l, P = 1e9 + 7, cnt, fac[1000005], ans = 1;
//fac = factorial = 阶乘
string s;
int fasp(int x, int y){
    //x to the yth
    if(y == 1)return x;
    if(y == 0)return 1;
    int val = fasp(x, y / 2);
    if(y % 2)return (val % P * val % P * x % P) % P;
    else return (val % P * val % P) % P;
}
signed main(){
    cin>>k>>n>>l;
    cin>>s;
    fac[0] = 1;
    for(int i = 1; i <= n; i++){
        fac[i] = (fac[i - 1] % P * i % P) % P;
    }
    for(int i = n - 1; i >= 0; i--){
        if(s[i] == 'O'){
            cnt++;
            continue;
        }
        //否则就需要开始配对了
        //对于这个 M 一共有 （cnt 选 k） 种方案
        //选完后将 cnt 也就是能选的 O 的数量减 k
        //选择 = cnt! / ((cnt - k)! * k!)
        int div = (fac[cnt - k] % P * fac[k] % P) % P;
        //除法得用乘法逆元做
        //不过反正都有快速幂了
        int inv = fasp(div, P - 2) % P;
        ans = (ans % P * (fac[cnt] % P * inv % P) % P) % P;
        cnt -= k;
    }
    cout<<fasp(ans, l) % P;
    return 0;
}

Result

Result。

还是得吐槽一句 USACO 但凡聪明一点把 L 定一个 10^3 肯定会卡掉一大堆尝试其他方式优化，没证出来每部分独立的人，及格线也就不用 850 了。

求赞。