专栏文章

题解：P11655 「FAOI-R5」Lovely 139

yyezicong1104
P11655题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqclo8p
此快照首次捕获于
2025/12/04 02:36
3 个月前
此快照最后确认于
2025/12/04 02:36
3 个月前
查看原文

题目描述

对于一个 0101 串 SS（下标从 11 开始），我们定义它的一个区间 [l,r][l,r] 是极长颜色段，当且仅当它同时满足以下条件：
  • 若 l≠1l \ne 1，Sl−1≠SlS_{l-1} \ne S_l；
  • 若 r≠∣S∣r \ne \lvert S \rvert，Sr+1≠SrS_{r+1} \ne S_r；
  • ∀i∈[l,r),Si=Si+1\forall i \in [l,r),S_i=S_{i+1}。
定义 g(S)g(S) 为 SS 的不同极长颜色段数。
定义 f(n,m)f(n,m) 的值为所有恰好包含 nn 个 00 和 mm 个 11 的 0101 串 SS 的 g(S)g(S) 之和。
回答 TT 个问题，每次给出 n,mn,m 的值，求 f(n,m) mod (109+7)f(n,m) \bmod (10^9+7) 的值。

样例

输入
CPP
3
2 2
4 6
7 8
输出
CPP
18
1218
54483

算法

(组合计数、逆元)

易得 g(S)=1+∑i=1n+m−1[Si≠Si+1]g(S)=1+\sum_{i=1}^{n+m-1}[S_i \ne S_{i+1}]。
先考虑 11，由于有 Cn+mnC_{n+m}^n 个 0101 串 SS，所以一共加了 Cn+mnC_{n+m}^n 个 11。
在 SS 中，对于 ∀i∈[1,n+m)\forall i \in [1,n+m)，若 Si≠Si+1S_i \ne S_{i+1}，对答案的贡献为 11。SiS_i 和 Si+1S_{i+1} 有 0101 和 1010 两种可能，其余的 n+m−2n+m-2 个数字随便排列，有 Cn+m−2n−1C_{n+m-2}^{n-1} 中排列。 所以对于 ∀i\forall i，所有 [Si≠Si+1][S_i \ne S_{i+1}] 的和对答案的贡献为 2×Cn+m−2n−12 \times C_{n+m-2}^{n-1}， 由于一共有 n+m−1n+m-1 个 ii，所以所有 ∑i=1n+m−1[Si≠Si+1]\sum_{i=1}^{n+m-1}[S_i \ne S_{i+1}] 的和对答案的贡献为 2×Cn+m−2n−1×(n+m−1)2 \times C_{n+m-2}^{n-1} \times (n+m-1)。
综上所述，答案为 Cn+mn+2×Cn+m−2n−1×(n+m−1)C_{n+m}^n+2 \times C_{n+m-2}^{n-1} \times (n+m-1)
预处理 facfac 数组存储阶乘，invinv 数组存储逆元，facinvfacinv 数组存储阶乘的逆元，可得 Cab=a!b!(a−b)!=faca×facinvb×facinva−bC_a^b=\frac{a!}{b!(a-b)!}=fac_a \times facinv_b \times facinv_{a-b}。

时间复杂度 O(T)O(T)

C++ 代码

CPP
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 2000010, MOD = 1e9 + 7;

int fac[N], inv[N], facinv[N];

LL C(int n, int m) { //计算组合数
	return (LL)fac[m] * facinv[m - n] % MOD * facinv[n] % MOD;
}

int main() {
	fac[0] = facinv[0] = inv[1] = 1; //初始化
	for (int i = 1; i < N; i++) //计算阶乘数组
		fac[i] = (LL)fac[i - 1] * i % MOD;
	for (int i = 2; i < N; i++) //计算逆元数组
		inv[i] = MOD - (LL)inv[MOD % i] * (MOD / i) % MOD;
	for (int i = 1; i < N; i++) //计算阶乘的逆元数组
		facinv[i] = (LL)facinv[i - 1] * (LL)inv[i] % MOD; //逆元的地推公式
	int T;
	scanf("%d", &T);
	while (T--) {
		int n, m;
		scanf("%d%d", &n, &m);
		int ans = 0;
		if (!n || !m) { //特判
			puts("1");
			continue;
		}
        //计算答案
		ans = (2ll * (n + m - 1) * C(n - 1, m + n - 2) % MOD + C(n, n + m)) % MOD;
		printf("%d\n", ans);
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...