题解 P5164 【xtq的定向越野】

· · 题解

这里出题组......来水一下社区贡献

首先考虑一个包含2^k个点的图，每个点对应一个任务子集。两个点之间连一条无向边，当且仅当这两个点对应的任务子集大小差为1.

那么，满足条件的一种安排任务的方式，就对应着一条从某个节点开始，经过图中所有边恰好一次再回到这个节点的路径，或者说，一条欧拉回路。

由小学奥数的经典结论（），一个无向图中存在欧拉回路，当且仅当每个点的度数均为偶数。

假设某个点对应的任务子集的大小为t，那么它将向所有对应集合大小为t-1和t+1的点连边。不难发现，这样的边共有C_{k}^{t-1}+C_{k}^{t+1}条。

进行简单的推导可以得出，使得每个点的度数均为偶数的k会满足将C_{k}^{0},C_{k}^{1},\dots,C_{k}^{k}排成一列之后是奇偶相间的。

然后怎么做呢？ 做为一名合格的OIer，我们要拥有良好的打表找规律能力。

于是写一个50pts的暴力，观察一下答案，发现满足条件的k必然可以表示为2^m-2，其中m是一个大于等于2的整数。

提交，AC，皆大欢喜（

为什么这个规律是这样呢？

考虑模2意义下的杨辉三角的第k行，不难发现这一行是10101\dots10101等价于第k+2行是1000\dots0001。

下证k是2的整数次幂且4\le k是杨辉三角的第k行为1000\dots0001的充要条件（以下所有推导中，k/2表示其向下取整的值）。

先证充分性：

假设对于所有k\le 2^m充分性成立。 当k=2^{m+1}时：

由Lucas定理得C_{2^{m+1}}^{t}=C_{2^m}^{t/2}

再证必要性： 假设对于所有$k\le 2^m$必要性成立。 若存在$2^m<k<2^{m+1}$满足条件，则对于任意$0<t<k$均有$C_{k}^{t}=0$。那么由Lucas定理可得，$C_{k/2}^{t/2}C_{k\%2}^{t\%2}

为0，即C_{k/2}^{t/2}=0或C_{k\%2}^{t\%2}=0.

考虑k的奇偶性：

若k为偶数，则对于任意一个偶数t，0<t/2<k/2。又由对于所有k\le 2^m必要性成立且2^{m-1}<k/2<2^m，则必然存在t/2使得C_{k/2}^{t/2}=1，矛盾。

若k为奇数，则C_{k/2}^{t/2}=C_{(k-1)/2}^{t/2}，其中k-1是一个偶数。 若k>2^m+1，那么由之前k为偶数的讨论可以得出上式必不总为0，则产生矛盾；若k=2^m+1，由上证充分性可推出k不满足条件。

综上，对于k\le 2^{m+1}必要性，由归纳法得证。

那么，k是2的整数次幂且4\le k是杨辉三角的第k行为1000\dots0001的充要条件得证，也就是说本题的答案就是所有满足k=2^t-2的2\le k\le n，其中k,t是一个整数。

第一次写长篇数学证明，不足之处请多指教！