526互联

CF785D Anton and School - 2

发布时间 2023-12-07 11:47:17作者: cxqghzj

题意

给定一个长度为 \(n\) 的括号序列，求该括号序列满足下列条件的子序列个数。

  • 长度为偶数
  • 设长度为 \(2m\)，则 \(s_{1 \ldots m} =\) (，\(s_{m + 1 \ldots 2m} =\) )。

Sol

设 \(i\) 为最后一个 (，\(a\) 表示 \(\sum_{j = 1} ^ {i - 1} [s_i = '(']\)。\(b\) 表示 \(\sum_{j = i + 1} ^ n [s_i = ')']\)

显然可得：

\[ \begin{aligned} ans &= \sum_{i = 1} ^ {len} \sum_{k = 0} ^ {min(a + 1, b)} C_a ^ k C_b ^ {k + 1} \end{aligned} \]

我们都知道：

\[ \begin{aligned} \sum_{j = 0} ^ {k} C_n ^ {k - i} C_m ^ i = C_{n + m}^k \end{aligned}\]

这个很显然吧，考虑组合意义。

在 \(n + m\) 个物品里面共选 \(k\) 个。

发现这两个式子长得很像。

考虑随便乱搞下。

\[ \begin{aligned} ans &= \sum_{i = 1} ^ {len} \sum_{k = 0} ^ {min(a + 1, b)} C_a ^ k C_b ^ {k + 1} \\ &= \sum_{i = 1} ^ {len} \sum_{k = 0} ^ {min(a + 1, b)} C_a ^ {a - k} C_b ^ {k + 1} \\ &= \sum_{i = 1} ^ {len} C_{a + b} ^ {a + 1} \end{aligned} \]

这道题就做完了，时间复杂度 \(O(n)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
string read_() {
	string ans;
	char c = getchar();
	while (c != '(' && c != ')')
		c = getchar();
	while (c == '(' || c == ')') {
		ans += c;
		c = getchar();
	}
	return ans;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}

const int N = 2e5 + 5, mod = 1e9 + 7;

namespace Mth {

array <int, N> fac, inv;

int pow_(int x, int k, int p) {
	int ans = 1;
	while (k) {
		if (k & 1) ans = ans * x % p;
		x = x * x % p;
		k >>= 1;
	}
	return ans;
}

void init() {
	fac[0] = 1; int n = 2e5;
	for (int i = 1; i <= n; i++)
		fac[i] = fac[i - 1] * i % mod;
	inv[n] = pow_(fac[n], mod - 2, mod);
	for (int i = n; i; i--)
		inv[i - 1] = inv[i] * i % mod;
}

int C(int n, int m) {
	if (n < m) return 0;
	return fac[n] * inv[m] % mod * inv[n - m] % mod;
}

void Mod(int& x) {
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}

}

array <int, N> h;

signed main() {
	string s = " " + read_();
	int n = s.size() - 1;
	for (int i = n; i; i--)
		h[i] = h[i + 1] + (s[i] == ')');
	Mth::init();
	int ans = 0, tp = 0;
	for (int i = 1; i <= n; i++) {
		if (s[i] == ')') continue;
		ans += Mth::C(tp + h[i], tp + 1), Mth::Mod(ans);
		tp++;
	}
	write(ans), puts("");
	return 0;
}