[CF1111D] Destory the Colony

Portal

大致题意: 给定一个偶数长度(\(n \leq 10 ^ 5\))的字符串, 只包含大小写字母. 有q(\(q \leq 10 ^ 5\))次询问, 每次指定两个位置, 要求通过交换字符, 使这两个类型的字符在串同一边并且对于其他类型的字符, 不能跨过串的中线(也就是说必须在一边, 但是可以不跟指定的字符一边), 求方案数模\(1e9 + 7\)

Solution

这个题目很像atcoder啊

考虑去掉多余的状态, 事实上只有\(52 ^ 2 = 2704\)种状态, 其他的询问都是多余的.

考虑钦定两种字母,O(n)计算方案数. 发现答案是\(\frac{(\frac{n}{2})! ^ 2}{\prod {cnt_i !}}\) 那么就只需要考虑如何把剩下的50种字母塞进\(\frac{n}{2} - cnt_i - cnt_j\)里面去;

现在就转化成为如何计算背包方案数, 在不每次重新计算的情况下.

考虑背包具有子问题的自我概括性. 那么我们就只要从源头开始, 沿着转移方向一步一步消除影响即可, 这个套路也可以运用到一部分非可减性dp中, 当然, 如果能写成矩阵的话就不用这么麻烦了.

Code

#include<bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)

#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)

#define clar(a, b) memset((a), (b), sizeof(a))

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define Debug(s) debug("The massage in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)

typedef long long LL;

typedef long double LD;

int read() {

    char ch = getchar();

    int x = 0, flag = 1;

    for(;!isdigit(ch); ch = getchar()) if(ch == '-') flag *= -1;

    for(;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

    return x * flag;

}

void write(LL x) {

    if(x < 0) putchar('-'), x = -x;

    if(x >= 10) write(x / 10);

    putchar(x % 10 + 48);

}

const int Maxn = 100009, Maxk = 60, Mod = (int)1e9 + 7;

char s[Maxn];

int n, q, dp[Maxn], cnt[Maxk];

int predict[Maxk][Maxk], tmpDp[Maxn];

int fac[Maxn], invFac[Maxn];

int fpm(int base, int tims) {

	int r = 1;

	while (tims) {

		if (tims & 1) r = 1ll * base * r % Mod;

		base = 1ll * base * base % Mod;

		tims >>= 1;

	}

	return r;

}

void init() {

	scanf("%s", s + 1); n = strlen(s + 1);

	rep (i, 1, n)

		if (isupper(s[i])) ++cnt[s[i] - 'A' + 1];

			else ++cnt[s[i] - 'a' + 27]; 

	/* Note */

	dp[0] = 1;

	rep (i, 1, 52) {

		if (!cnt[i]) continue;

		drep (j, n, cnt[i]) (dp[j] += dp[j - cnt[i]]) %= Mod;

	}

	/* Note */

	fac[0] = 1;

	rep (i, 1, n) fac[i] = fac[i - 1] * 1ll * i % Mod;

	invFac[n] = fpm(fac[n], Mod - 2);

	drep (i, n - 1, 0) invFac[i] = invFac[i + 1] * (i + 1ll) % Mod;

}

void solve() {

	rep (i, 1, 52)

		rep (j, 1, i) {

			if (!cnt[i] || !cnt[j]) continue;

			rep (l, 0, n) tmpDp[l] = dp[l];

			rep (l, cnt[i], n) {

				(tmpDp[l] -= tmpDp[l - cnt[i]]) %= Mod;

				(tmpDp[l] += Mod) %= Mod;

			}

			if (i == j) {

				predict[i][i] = tmpDp[n / 2];

				continue;

			}

			rep (l, cnt[j], n) {

				(tmpDp[l] -= tmpDp[l - cnt[j]]) %= Mod;

				(tmpDp[l] += Mod) %= Mod;

			}

			predict[i][j] = predict[j][i] = tmpDp[n / 2];

		}

	int W = fac[n / 2] * 1ll * fac[n / 2] % Mod;

	rep (i, 1, 52)

		if (cnt[i] > 0) W = 1ll * W * invFac[cnt[i]] % Mod;

	q = read();

	rep (i, 1, q) {

		int x = read(), y = read();

		if (isupper(s[x])) x = s[x] - 'A' + 1; else x = s[x] - 'a' + 27;

		if (isupper(s[y])) y = s[y] - 'A' + 1; else y = s[y] - 'a' + 27;

		printf("%d\n", 2ll * W % Mod * predict[x][y] % Mod);

	}

}

int main() {

    freopen("Cf1111D.in", "r", stdin);

    freopen("Cf1111D.out", "w", stdout);

    init();

    solve();

#ifdef Qrsikno

    debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);

#endif

    return 0;

}

巴特西

[CF1111D] Destory the Colony

Solution

Code

最新文章

热门文章