Warning: session_start(): open(/tmp/sess_aa0df0127d8b6a433273bb0e42a854cd, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/878e000dca5c08fe55e62fff31fad8b7.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 某个最大反链问题 ======
给定一个非负整数数列 $\{t_{i}\}$，定义偏序集 $S=\prod_{i=1}^{n}\{x|0\le x\le t_{i},x\in\mathbb{Z}\}$，其中 $\vec{x}\preceq\vec{y}$ 当且仅当 $\forall 1\le i\le n,x_{i}\le y_{i}$。那么 $S$ 的最大反链的大小等于关于 $x_{i}$ 的不定方程 $\displaystyle{\sum_{i=1}^{n}x_{i}=\lfloor\frac{\sum_{i=1}^{n}t_{i}}{2}\rfloor}$ 满足 $\forall 1\le i\le n, 0\le x_{i}\le t_{i}$ 的整数解的个数。
**证明**：将该问题用整除来描述：设有整数 $n$，考虑其所有约数组成的集合 $S$，定义 $x\preceq y$ 当且仅当 $x\mid y$。定义 $\deg x$ 为其（可重）质因子数。设 $\deg n=m$。定义 $C=\{x|\deg x=\lfloor\frac{m}{2}\rfloor\}$。我们证明，$S$ 的最大反链大小为 $|C|$，其中 $C$ 显然是一个满足要求的解。
定义对称链为一个序列 $d_{1},d_{2},\cdots,d_{h}$，其中 $\deg d_{1}+\deg d_{h}=m$，$\forall 1\le i