自动搬运

查看原文

来自洛谷，原作者为

	donaldqian **

搬运于2025-08-24 23:12:15，当前版本为作者最后更新于2025-04-18 17:09:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个数据范围很吓人啊！

但是我们冷静思考一下，如果一个字符串中 $\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;
}