题目描述给定正整数n nn统计所有排列( a 1 , a 2 , … , a n ) (a_1, a_2, \ldots , a_n)(a1​,a2​,…,an​)的个数使得∑ i 1 n ∣ a i − i ∣ ⌊ n 2 2 ⌋ . \sum_{i1}^{n} |a_i - i| \left\lfloor \frac{n^2}{2} \right\rfloor .i1∑n​∣ai​−i∣⌊2n2​⌋.其中排列是( 1 , 2 , … , n ) (1, 2, \ldots , n)(1,2,…,n)的任意重排。输入格式输入包含多组数据不超过1000 10001000组每组数据仅包含一个整数n nn1 ≤ n ≤ 10 6 1 \le n \le 10^61≤n≤106。输入以文件结束符EOF \texttt{EOF}EOF终止。输出格式对于每组输入输出一行一个整数表示满足条件的排列数量对10 9 7 10^9 71097取模后的结果。样例输入1 2 3输出1 1 3题目分析定义目标值T ⌊ n 2 / 2 ⌋ T \lfloor n^2 / 2 \rfloorT⌊n2/2⌋。对于任意排列和式S ∑ ∣ a i − i ∣ S \sum |a_i - i|S∑∣ai​−i∣总是偶数因为S ∑ i 1 n ∣ a i − i ∣ ≡ ∑ i 1 n ( a i − i ) ≡ 0 ( m o d 2 ) . S \sum_{i1}^n |a_i - i| \equiv \sum_{i1}^n (a_i - i) \equiv 0 \pmod{2}.Si1∑n​∣ai​−i∣≡i1∑n​(ai​−i)≡0(mod2).当n nn为偶数时⌊ n 2 / 2 ⌋ n 2 / 2 \lfloor n^2/2 \rfloor n^2/2⌊n2/2⌋n2/2当n nn为奇数时⌊ n 2 / 2 ⌋ ( n 2 − 1 ) / 2 \lfloor n^2/2 \rfloor (n^2 - 1)/2⌊n2/2⌋(n2−1)/2两者均为整数。考虑S SS的上界。对于每个位置i ii最大值∣ a i − i ∣ |a_i - i|∣ai​−i∣在a i a_iai​取1 11或n nn时达到但全排列的限制使得全局最大和有一个已知公式max ⁡ a ∈ S n ∑ i 1 n ∣ a i − i ∣ ⌊ n 2 2 ⌋ . \max_{a \in \mathfrak{S}_n} \sum_{i1}^n |a_i - i| \left\lfloor \frac{n^2}{2} \right\rfloor .a∈Sn​max​i1∑n​∣ai​−i∣⌊2n2​⌋.事实上该最大值仅在特定的“反转”结构中取得。因此本题等价于求所有使S SS达到全局最大值的排列数目。解题思路最大值取等条件令k ⌊ n / 2 ⌋ k \lfloor n/2 \rfloork⌊n/2⌋。为了达到T ⌊ n 2 / 2 ⌋ T \lfloor n^2/2 \rfloorT⌊n2/2⌋排列必须满足所有较小的数1 , 2 , … , k 1,2,\ldots ,k1,2,…,k只能出现在位置k 1 , k 2 , … , n k1, k2, \ldots , nk1,k2,…,n上所有较大的数n − k 1 , n − k 2 , … , n n-k1, n-k2, \ldots , nn−k1,n−k2,…,n只能出现在位置1 , 2 , … , k 1,2,\ldots ,k1,2,…,k上。这样每个贡献∣ a i − i ∣ |a_i - i|∣ai​−i∣都能取到最大可能值。若将数分成“小数集合”L { 1 , … , k } L \{1,\ldots ,k\}L{1,…,k}和“大数集合”H { n − k 1 , … , n } H \{n-k1,\ldots ,n\}H{n−k1,…,n}位置也分为“前k kk个位置”P PP和“后k kk个位置”Q QQ当n nn为奇数时还剩下中间一个位置和一个中间数。计数推导情况一n nn为偶数即n 2 k n 2kn2k。前k kk个位置必须放置大数集合H HH且可以任意排列方案数为k ! k!k!后k kk个位置必须放置小数集合L LL且可以任意排列方案数也为k ! k!k!。因此总方案数为( k ! ) 2 (k!)^2(k!)2。情况二n nn为奇数即n 2 k 1 n 2k 1n2k1。中间位置第k 1 k1k1个位置可以放置任意一个数共有2 k 1 n 2k1 n2k1n种选择放置后剩下的2 k 2k2k个数中有k kk个大于中间数的数大数和k kk个小于中间数的数小数前k kk个位置必须放置这k kk个大数排列数为k ! k!k!后k kk个位置必须放置这k kk个小数排列数也为k ! k!k!。因此总方案数为n ⋅ ( k ! ) 2 n \cdot (k!)^2n⋅(k!)2。综合两种情形统一公式为ans { ( k ! ) 2 , n 为偶数 , n ⋅ ( k ! ) 2 , n 为奇数 , 其中 k ⌊ n 2 ⌋ . \textit{ans} \begin{cases} (k!)^2, n \text{ 为偶数},\\[4pt] n \cdot (k!)^2, n \text{ 为奇数}, \end{cases} \quad \text{其中 } k \left\lfloor \frac{n}{2} \right\rfloor .ans{(k!)2,n⋅(k!)2,​n为偶数,n为奇数,​其中k⌊2n​⌋.模运算由于n nn最大为10 6 10^6106我们预处理0 ! 0!0!到10 6 ! 10^6!106!对10 9 7 10^9 71097取模的值然后每组询问O ( 1 ) O(1)O(1)计算即可。复杂度分析预处理阶乘O ( max ⁡ n ) O(\max n)O(maxn)这里max ⁡ n 10 6 \max n 10^6maxn106。每组询问O ( 1 ) O(1)O(1)。总时间复杂度O ( max ⁡ n Q ) O(\max n Q)O(maxnQ)其中Q QQ为询问组数不超过1000 10001000。空间复杂度O ( max ⁡ n ) O(\max n)O(maxn)用于存储阶乘表。代码实现// Count these Permutations// UVa ID: 13204// Verdict: Accepted// Submission Date: 2026-07-13// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMOD1000000007;constintMAXN1000000;intmain(){// 预计算阶乘 fact[i] i! mod MODstaticlonglongfact[MAXN1];fact[0]1;for(inti1;iMAXN;i)fact[i]fact[i-1]*i%MOD;intn;// 读取所有输入直到 EOFwhile(cinn){intkn/2;// 向下取整longlongansfact[k]*fact[k]%MOD;if(n1)// n 为奇数ansans*n%MOD;coutans\n;}return0;}总结本题的关键在于识别最大值取等时排列的结构特点。通过对偶性的分析将原问题转化为简单的阶乘乘积形式避免了复杂的排列枚举。预处理阶乘使得多组询问能在常数时间内回答符合题目n nn较大但询问量小的约束。核心技巧为利用绝对值求和的上界及其取等条件分奇偶讨论统一公式预计算阶乘并利用模运算处理大数。本题展示了组合计数中“极值结构”的常用分析方法即当目标函数达到最值时变量的位置往往被严格限制从而大大简化计数。