题解：P12028 [USACO25OPEN] Moo Decomposition G

· · 题解

这个数据范围很吓人啊！

但是我们冷静思考一下，如果一个字符串中 \text O 的个数不是 \text M 的个数的 K 倍，那么答案显然是 0。所以如果 T 不满足上述条件，S 也一定不满足，即无解。首先把这种东西判掉。

其次，考虑 S 中最后一个 T 串。容易发现我们只能将 T 完整地划分成若干子序列。证明如下：

假设某种划分方案跨过了最后一个 T 串。那么相当于用掉了最后一个 T 串中的若干个 \text O，cnt\text O = k\times cnt\text M 的条件就不满足了，得证。

于是就好做了，考虑对于单个 T 串怎么做，显然倒序枚举，算出每个 \text M 后面有多少个还没用过的 \text O，组合数学一下即可。最后输出答案的 L 次幂。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1e6 + 10, mod = 1e9 + 7;
int k, n, fac[maxn], inv[maxn], sum, ans;
char s[maxn]; ll l;

int quickpow (int a, ll b) {
    int x = 1; while (b) {
        if (b & 1) x = 1ll * x * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return x;
}
int C (int x, int y) { return (y < 0 || y > x) ? 0 : 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod; }

signed main () {
    scanf("%d%d%lld%s", &k, &n, &l, s + 1), fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[n] = quickpow (fac[n], mod - 2), ans = 1;
    for (int i = n - 1; ~i; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
    for (int i = n; i >= 1; i--) {
        if (s[i] == 'O') sum++;
        else ans = 1ll * ans * C (sum, k) % mod, sum -= k;
    }
    ans *= (sum == 0);
    printf("%d", quickpow (ans, l));
    return 0;
}