「HSEFZ OI 181028」Links

我在 2018 年搬自己 2016 年搬的 2014 年的题目……

Task 3,似乎还是挺有意思的一道计数问题。


问题

任务

有编号 11NNNN 个点排成环形,需要依次选择其中 KK 个,同时须保证任意时刻「团」的数目不超过 GG

所谓「团」,是指已经选择的点形成的极大连续段。

给定 NNKKGG 的值,计算满足条件的方案数目除以 109+710^9 + 7 的余数。两个方案不同,当且仅当存在 ii 使得两个方案中按时间顺序第 ii 个被选点的编号不同。

输入

输入的第一行包含一个整数 CC 表示该测试点包含的数据组数。不同组数据互相独立,两组数据间不包含多余的空行。

每组数据的输入为一行,包含三个正整数 NNKKGG

输出

输出 CC 行。其中第 ii 行包含一个正整数,表示对于第 ii 组数据不同的方案数除以 109+710^9 + 7 的余数。

样例

输入
1
2
3
4
5
4
4 2 1
5 4 2
6 4 4
42 23 7
输出
1
2
3
4
8
120
360
917668006

在第一组数据中,满足条件的方案有 1-2,2-3,3-4,4-1,1-4,4-3,3-2,2-1 共 88 种。

在第三组数据中,以任意顺序选择任意 44 个点即符合要求,方案共 6×5×4×3=3606 \times 5 \times 4 \times 3 = 360 种。

数据规模与约定

对于所有数据有 1GKN1 \leq G \leq K \leq N2N2 \leq N

测试点编号 CC NN 附加条件
1 - 3 55 8\leq 8 G=1G = 1
4 - 8 55 8\leq 8 -
9 - 15 55 20\leq 20 -
16 - 20 55 2000\leq 2\,000 G20G \leq 20
21 - 23 55 2000\leq 2\,000 -
24 - 25 1010 2000\leq 2\,000 -

题解

tl;dr 直接跳到「算法五」

为什么结束时满足条件并不意味着整个过程满足条件

看一个🌰

N=4N = 4K=3K = 3G=1G = 1
第一步(选择 11,一个团):● ○ ○ ○ (其实是个环)
第二步(选择 33,两个团):● ○ ● ○ ← 违反限制
第三步(选择 22,一个团):● ● ● ○ ← 满足限制

大概需要读完题才能着手的算法一

12% 的数据满足 G=1G = 1

这意味着第一个选择的点可以任选,之后每一个点必须与之前点形成的团相邻,即左边或右边。于是答案为 N2K1N \cdot 2^{K-1}

似乎过了样例就能信心满满的算法二

32% 的数据满足 N8N \leq 8

枚举所有至多 N!N! 种选择顺序并时刻检查是否违反了团数不超过 GG 的限制。单组数据时间复杂度 O(NN!)O(N \cdot N!)

样例的前三组数据是不是很良心吖~~

可能程序也挺容易写的算法三

60% 的数据满足 N20N \leq 20

考虑状态压缩 DP。用 f[s]f[s] 表示「选择二进制数 ss 所表示集合中的所有点」且「中途不违反团数限制」的方案数(取模)。从 002N22^N - 2 枚举 ss,对于每个 ss,枚举一个不在集合 ss 中的元素 uu 尝试加入,并检查是否超过了 GG 个团;若没有超过,则令 f[su]f[s \cup u] 增加 f[s]f[s]

【为什么枚举到 2N22^N - 2?因为 2N12^N - 1 时已经全部安排上啦 ╮( ̄▽ ̄"")╭】

最后找出二进制下 11 的位数不超过 KK 的所有 ss,累加 f[s]f[s] 即为答案。

状态数 O(2N)O(2^N),转移 O(N)O(N),总时间复杂度 O(N2N)O(N \cdot 2^N)

好像终于不能继续暴力下去的算法四

另外 16% 的数据满足 G20G \leq 20

一脸 DP 的样子,考虑 DP 吧!

然后 lsq 在一个纸箱上躺了半天也没想出针对这些数据的算法(´ - `)【忽略那些奇怪的细节吧】

或许是超级无敌旋转棒棒的算法五

如前所述,DP!

考虑点的编号的话,状态会不那么容易表示。不妨将「已经选择的点数目」与「目前的组数」放入状态中。用 f[i][j]f[i][j] 表示选择了 ii 个点,形成 jj 个组的方案数。

一个问题是,点以编号区分,但状态并不加以记录。状态中究竟认为点在哪些方面相同,将直接影响状态转移方程的设计,因此我们需要提前考虑。

略去心路历程,这里给出我们最终发现可行的定义:对于 f[i][j]f[i][j] 所表示的状态,认为所有选择的点依选择次序编为 11nn 号,它们之间的排列顺序不同则认为方案不同;这个编号与实际编号无关,我们只是考虑了一个虚构的点集,最后再尝试将这个点集对应到实际编号上。此外,状态中两个团之间间隔的点数是不确定的。

这样一来状态转移便很明晰了,对于 f[i][j]f[i][j],考虑第 ii 个加入的点:

  1. 若它紧贴之前的某一个团,则当前状态有 f[i1][j]2jf[i - 1][j] \cdot 2j 的增量;2j2j 的因子是由于之前也有 jj 个团,贴在其中每一个逆时针或顺时针方向(或者说左边/右边)都是一种可能的情况。
  2. 若它将之前的两个团连接起来,则当前状态有 f[i1][j+1](j+1)f[i - 1][j + 1] \cdot (j + 1) 的增量;j+1j + 1 的因子是由于之前 j+1j + 1 个团中任意相邻两个都可以被连接,且排列成一个环。
  3. 若它自成一个新的团,则当前状态有 f[i1][j1](j1)f[i - 1][j - 1] \cdot (j - 1) 的增量;j1j - 1 的因子是由于之前 j1j - 1 个团中任意相邻两个之间都可以插入一个新的团。

状态数 O(GK)O(GK),状态转移 O(1)O(1),于是时间复杂度为 O(GK)O(GK)

这一部分结束后,考察所有 f[K][i]f[K][i],其中 1iG1 \leq i \leq G。对于这样的 f[K][i]f[K][i],需要计算将 KK 个点对应到原本的 NN 个点中 KK 个的方案数。不妨认为状态中的 11 号点可以任取为实际任意一个点;此后状态中 22KK 号点的顺序,以及它们之间是否相邻(同一个团的相邻,不同团的不相邻;尽管没有记录在状态中,但是体现于方案的计算过程),均已确定。也即:需要将剩余 NKN - K 个点划分为 ii 个连续的段(亦即「团」),作为团之间的分隔。根据插板法,这个值为 (nk1i1)\binom {n-k-1} {i-1}。【(nm)\binom n m 也写作 Cnm\mathrm{C}_n^m

因此,遍历 iGi \leq G,累加 f[K][i]n(nk1i1)f[K][i] \cdot n \cdot \binom {n-k-1} {i-1} 即为答案。

时间复杂度为 O(GK)O(GK)。【好像数据范围 NN 可以出得更大的样子??】

废话几句

感谢大家能读到这里啦。

这道题目应该还是比较精妙的一道 DP 问题,部分分似乎好像可能大概…… 也给的挺足吧?希望 NOIP 前能给大家带来一次不那么坑的比赛 > <

嘛要说为什么想到最后这个状态表示…… 可能核心还是在于「先计算后对应」的思路吧【原谅伦无语次的 lsq QAQ】其实好多 DP 问题都是多试试几种状态表示法说不定哪个就走通了呢(笑)总之程序还是超好写的……

对于这个 idea 有兴趣的话,欢迎来尝试这个题~ 「JOI Open 2016」摩天大楼

三道题都是从以前的比赛中搬的… 命题人是岛娘 (xiaodao),在此表示感激!

还有金老师两年前对于校内模拟赛的支持,以及给 lsq 提供机会重新审视这道埋藏多年的题目;以及 chy (@watermelly) 同学近日抽出时间给前两题补足了题解,也一并致谢啦。

以上。祝一切安好!

标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstring>

typedef long long int64;

static const int MAXN = 2005;
static const int MODULUS = 1e9 + 7;
#define _ % MODULUS

int n, k, g;
int f[MAXN][MAXN] = {{ 0 }};

inline int qpow(int base, int exp)
{
int64 ans = 1;
for (; exp; exp >>= 1) {
if (exp & 1) ans = (ans * base)_;
base = (int64)base * base _;
}
return (int)ans;
}

inline int inv(int x)
{
return qpow(x, MODULUS - 2);
}

int fact[MAXN], fact_inv[MAXN];

inline int binom(int n, int m)
{
if (n < m || n < 0 || m < 0) return 0;
return (int64)fact[n] * fact_inv[m]_ * fact_inv[n - m]_;
}

void work()
{
scanf("%d%d%d", &n, &k, &g);
if (k == n) k = n - 1;

memset(f, 0, sizeof f);
f[0][0] = f[1][1] = 1;
for (int i = 2; i <= k; ++i) {
for (int j = 1; j <= g; ++j)
f[i][j] = (
(int64)f[i - 1][j] * j _ * 2 +
(int64)f[i - 1][j - 1] * (j - 1)_ +
(int64)f[i - 1][j + 1] * (j + 1)_
)_;
}

int ans = 0;
for (int i = 1; i <= g; ++i)
ans = ((int64)f[k][i] * binom(n - k - 1, i - 1)_ * n _ + ans)_;
printf("%d\n", ans);
}

int main()
{
freopen("links.in", "r", stdin);
freopen("links.out", "w", stdout);

fact[0] = 1;
for (int i = 1; i < MAXN; ++i)
fact[i] = (int64)fact[i - 1] * i _;

fact_inv[MAXN - 1] = inv(fact[MAXN - 1]);
for (int i = MAXN - 2; i >= 0; --i)
fact_inv[i] = (int64)fact_inv[i + 1] * (i + 1)_;

int T; scanf("%d", &T);
do work(); while (--T);

fclose(stdin); fclose(stdout);
return 0;
}
作者:Shiqing
链接:https://kawa.moe/2018/10/links-sol/
版权:文章在 CC BY-NC-SA 4.0 许可证下发布。转载请注明来自 quq