算法
场上也是把所有需要的性质全部都推出来了, 但是计数类型的底子太差, 直接也是没把答案式子表示出来啊
容易的, 我们可以知道, 对于一个长度为 \(n\) 的序列, 其中每一个 \([l_i, r_i]\) 确定, 那么不管怎样排列, 最终都是合法的
我们还可以知道, 如果每一个点, 作为左端点还是右端点, 那么不管左右端点如何组合, 最终也都是合法的
无论怎样, 就算想的是歪解, 也会在操作过程中发现这两个性质, 这是简单的
那么考虑接下来怎么做, 考场上我的想法是, 令 \(1\) 表示当前点为左端点, \(-1\) 表示当前点为右端点, 那么这个点是白色还是黑色相当于限制了前缀的奇偶性, 特别的, 如果当前点是 \(-1\) , 那么这个点的前缀和不计算这个 \(-1\) , 原因是显然的, 就算这是右端点, 你也还是被取反了一次是吧
那么对于每个点, 取 \(1\) 和 \(-1\) 会产生奇偶性的变化, 显然的, 这样可以确定每个点应该填 \(1\) 还是 \(-1\) , 这以后我的做法就偏差很多了, 当时我在想记忆化搜索??? 本质上是因为没有考虑到这里可以确定 \(1\) 和 \(-1\) 的取值
那么好, 现在我们知道每个点应当取左端点还有右端点, 那么怎么计算一共有多少种配对方式呢?
然后场上的我就开始 \(\rm{dfs}\) 了, 糖
显然的, 我们可以用组合数学的方法来解决这个问题,
记 \(Cntl_i\) 表示 \([0, i]\) 中左端点的出现次数, \(Cntr_i\) 表示 \([0, i]\) 中右端点的出现次数, \(pos_i\) 表示第 \(i\) 个右端点的位置
对于每一个右端点, 我们显然可以取 \({Cntl}_{i - 1} - {Cntr}_{i - 1}\) 种左端点
那么显然的, 最终的答案式子可以写成:
\[n! \times \prod_{i = 1}^{{Cntr}_{n}} \left(Cntl_{pos_i - 1} - i + 1\right) \]至此, 可以通过本题
代码
#include <bits/stdc++.h>
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 20;
int n;
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
std::string Col;
std::cin >> Col;
long long ans = 1;
for (int i = 1; i <= n; i++)
ans = ans * i % MOD;
std::vector<int> a(2 * MAXN);
for (int i = 0; i < 2 * n; i++)
a[i] = (Col[i] == (i % 2 ? 'B' : 'W'));
int sum = 0;
for (int i = 0; i < 2 * n; i++) {
if (!a[i])
++sum;
else {
ans = ans * sum % MOD;
--sum;
}
}
if (sum != 0) // 左右端点数量不等
ans = 0;
printf("%lld\n", ans);
}
}
总结
推了很多, 卡在一个地方, 可以考虑统筹所有信息再来一遍
组合数学要多练
标签：Inversion,那么,int,sum,Cntl,Cell,qual,端点,ans From： https://www.cnblogs.com/YzaCsp/p/18586408