核心思路

本题要求计算从 $[1, 2n]$ 中选 $n$ 个数，且集合中包含偶数个偶数的集合数目。关键在于利用组合恒等式和对称性来推导封闭解。

关键观察

1. 数值分布：在 $[1, 2n]$ 中，恰有 $n$ 个奇数和 $n$ 个偶数
2. 奇偶性对称：设选择的偶数个数为 $k$，则选择的奇数个数为 $n-k$
3. 组合总数：所有可能的集合数为 $\binom{2n}{n}$

重要公式推导

问题形式化

设 $E$ 为满足条件的集合数（含偶数个偶数），$O$ 为含奇数个偶数的集合数，则：

$$E + O = \binom{2n}{n}$$

生成函数方法

考虑生成函数：

$$(1+x)^n(1+x)^n = (1+x)^{2n}$$

其中左边第一个 $(1+x)^n$ 对应选择偶数（选或不选），第二个 $(1+x)^n$ 对应选择奇数。

令 $x = -1$ 得：

$$(1-1)^n(1-1)^n = (1-1)^{2n} = 0$$

展开左边：

$$\sum_{k=0}^n \binom{n}{k}(-1)^k \cdot \sum_{j=0}^n \binom{n}{j}(-1)^j = 0 $$

但更精确地，考虑偶数选择的生成函数：

$$E - O = \sum_{\text{偶数}k} \binom{n}{k}\binom{n}{n-k} - \sum_{\text{奇数}k} \binom{n}{k}\binom{n}{n-k} $$

组合恒等式

通过生成函数分析可得：

$$E - O = (-1)^{n/2} \binom{n}{n/2} \quad (\text{当 } n \text{ 为偶数时}) $$$$E - O = 0 \quad (\text{当 } n \text{ 为奇数时})$$

最终解

结合 $E + O = \binom{2n}{n}$，解得：

• 当 $n$ 为奇数时：

  $$E = O = \frac{1}{2}\binom{2n}{n}$$

• 当 $n$ 为偶数时：

  $$E = \frac{1}{2}\left[\binom{2n}{n} + (-1)^{n/2} \binom{n}{n/2}\right] $$$$O = \frac{1}{2}\left[\binom{2n}{n} - (-1)^{n/2} \binom{n}{n/2}\right] $$

算法实现要点

1. 模运算：在模 $1000003$（质数）下计算
2. 卢卡斯定理：处理 $n \leq 10^{18}$ 的大数组合数计算
3. 预处理：预计算阶乘和逆元加速模意义下的组合数计算