hdu7191

题目描述

有 个环，从每个环中选出若干条不相邻的边，问选出 条边一共有多少种选法

解题思路

首先考虑 个数中任何两个数不相邻的组合，可以将问题转化，即从 个数中选出 个，然后再向这 个数中间插入 个数，即可保证两两不相邻。再考虑环的答案。环与链的不同仅仅在于 和 也不能相邻。我们考虑正难则反的思想，钦定 和 必须被选择，如此 和 必定不能被选择，问题转化为 和 的情况，故答案为：

之后我们使用dp的方法来统计答案，但是直接dp时间复杂度为 ，必定会超时。我们考虑分治FFT合并答案，每次FFT合并的时间复杂度为 ，总时间复杂度近似为 。给出部分合并代码：

ll ans[21][2][N];
void divide(int l, int r, int k, int dep, int rson) {
	if (l == r) {
		ans[dep][rson][0] = 1;
		ans[dep][rson][1] = circle_sz[l];
		for (int i = 2; i <= min(circle_sz[l] >> 1, k); ++i) {
			ans[dep][rson][i] = (C(circle_sz[l] - i + 1, i) - C(circle_sz[l] - i - 1, i - 2) + MOD) % MOD;
		}
		ans_sz[dep][rson] = min(circle_sz[l] >> 1, k);
		return;
	}
	int mid = (l + r) >> 1;
	divide(l, mid, k, dep + 1, 0);
	divide(mid + 1, r, k, dep + 1, 1);
	FFT::Work(ans[dep + 1][0], ans[dep + 1][1], ans_sz[dep + 1][0], ans_sz[dep + 1][1], ans[dep][rson]);
	ans_sz[dep][rson] = min(k, ans_sz[dep + 1][1] + ans_sz[dep + 1][0]);
}

tips：在本题中，使用了一个比较大的数组来存储每一层的答案以反馈给上一层的FFT使用。需要注意的是，因为同一层的数组被反复复用，因此当进行FFT时，假设当前数组的宽度是 ，卷积和的长度是 ，我们需要对 到 的内容进行清零，防止导致答案错误。