$N$ 为满足以下条件的 $1\text{,}2\text{,}3\text{,}\cdots \text{,}30$ 的排列 $\left( {{a}_{1}}\text{,}{{a}_{2}}\text{,}\cdots \text{,}{{a}_{30}} \right)$ 的个数：对于 $m\in \left\{ 2\text{,}3\text{,}5 \right\}\text{,}\left. m \right|{{a}_{m+n}}-{{a}_{n}}\text{,}\forall n\text{,}1\leqslant n<n+m\leqslant 30$ 。求 $N$ 模 $1000$ 的值。
【难度】
【出处】
2011年第29届美国数学邀请赛Ⅱ（AIMEⅡ）
【标注】
【答案】
440
【解析】
对于每个排列，其中的每个位置可对应一个三元有序数组 $\left( i,j,k \right)$ 。第 $n$ 个位置对应的三元数组定义如下：$i\equiv n\left( \bmod 2 \right),j\equiv n\left( \bmod 3 \right),k\equiv n\left( \bmod 5 \right)$ 。故可得到的不同三元数组有 $2\cdot 3\cdot 5=30$ 种可能。我们下面依次考虑 $\text{1}\sim \text{5}$ 可能的位置。 $\text{1}$ 可能在的位置对应的三元数组的 $i$ 有 $\text{2}$ 种选择，$j$ 有 $\text{3}$ 种选择，$k$ 有 $\text{5}$ 种选择，故共有 $\text{30}$ 种选择（即 $\text{1}$ 可在 $\text{30}$ 个位置中的任一位置上）。当 $\text{1}$ 的位置确定后，$\text{2}$ 的位置的三元数组 $i$ 有 $\text{1}$ 种选择，$j$ 有 $\text{2}$ 种选择，$k$ 有 $\text{4}$ 种选择，故共有 $\text{8}$ 种可能。当 $\text{1,2}$ 位置选定后，同理 $\text{3}$ 的位置有 $\text{3}$ 种选择。 $1,2,3$ 位置确定后 $\text{4}$ 有 $\text{2}$ 种位置选择。 $1,2,3,4$ 位置确定后，$\text{5}$ 对应唯一的位置选择。当 $1,2,3,4,5$ 位置确定之后，$i,k,j$ 所有值都有出现过，则 $\text{6}\sim \text{30}$ 的位置被唯一确定。故 $N=30\cdot 8\cdot 3\cdot 2=1440,N\equiv440\left( \bmod 1000 \right)$
答案
解析
备注
