P16351 「Gensokyo OI Round 1」秘神之钥 题解

· · 题解

哪个管理审的，跟我说组合数要使用 \binom 打回，那我问你，我的式子里已经全是括号了，如果用了 \binom 是不是就又要因为括号太乱格式不清晰不便于阅读为由给我打回了？我不改了。

何意味怎么全是没推到底的题解？

我来发一篇模数固定时预处理 O(n)，单次询问 O(1) 的解。

首先先放结论：

\mathrm{ans}_n=\begin{cases}4,&n=3\\(2k)!\left(1-\frac{2}{k^2}\right)+2((k-1)!)^2,&n=2k(k \in \mathbb{Z_{\ge 2}})\\4(k-1)((k-2)!)^2+(2k+1)!\left(1-\frac{2(k^3-k^2-2k+4)}{(k+2)(k+1)k^2(k-1)}\right),&n=2k+1(k \in \mathbb{Z_{\ge 2}})\end{cases}

我们来证明这件事。

首先 n=3 特判没什么好说的。下面设 n \ge 4。

考虑记 T_n 为在 p_1<p_n 的时候的不合法的方案数。

注意到每次交换要么以 p_1 为中心，p_n 被交换，要么以 p_n 为中心，p_1 被交换，于是不合法的所有条件均为 p_x,p_n 同时大于或小于 p_1，或 p_x,p_1 同时大于或小于 p_n。

于是把所有 p_i 同时变为 n+1-p_i，条件不变。

所以 \mathrm{ans}_n=n!-2T_n。下面计算 T_n，也就是设 p_1<p_n 且排列不合法。

下面对 n 的奇偶分类讨论。

1. n=2k(k \in \mathbb{Z_{\ge 2}})

这部分较简单，要满足的条件为：

于是 p_1 \le k,p_{2k} \ge k+1，记 u=p_1,v=p_{2k}(u \le k,v \ge k+1)。

考虑 [p_{2k}+1,2k] 的数都在 p_{2i}(1 \le i \le k-1) 中出现，[1,p_1-1] 的数都在 p_{2i+1}(1 \le i \le k-1) 中出现，其余数随便，通过这个计数。

T_n&=\sum\limits_{u=1}^k\sum\limits_{v=k+1}^{2k}C_{v-u-1}^{v-k-1}((k-1)!)^2\\ &=((k-1)!)^2\sum\limits_{u=1}^k\sum\limits_{v=k+1}^{2k}C_{v-u-1}^{k-u}\\ &=((k-1)!)^2\sum\limits_{u=1}^k\sum\limits_{v=0}^{k-1}C_{v+(k-u)}^{k-u}\\ &=((k-1)!)^2\sum\limits_{u=1}^k C_{(k-1)+(k-u)+1}^{k-u+1}\\ &=((k-1)!)^2\sum\limits_{u=1}^k C_{2k-u}^{k-u+1}\\ &=((k-1)!)^2\sum\limits_{u=1}^k C_{2k-u}^{k-1}\\ &=((k-1)!)^2\sum\limits_{u=1}^k C_{(k-1)+u}^{k-1}\\ &=((k-1)!)^2\left(-1+\sum\limits_{u=0}^k C_{(k-1)+u}^{k-1}\right)\\ &=((k-1)!)^2\left(-1+C_{k+(k-1)+1}^{k-1+1}\right)\\ &=((k-1)!)^2\left(-1+C_{2k}^{k}\right)\\ &=-((k-1)!)^2+\frac{(2k)!}{k^2} \end{aligned}

于是：

\mathrm{ans}_n&=(2k)!-2T_n\\ &=(2k)!\left(1-\frac{2}{k^2}\right)+2((k-1)!)^2 \end{aligned}

2. n=2k+1(k \in \mathbb{Z_{\ge 2}})

这部分略微繁琐一点，要满足的条件为：

于是 p_1<p_2,p_3<p_{2k+1}，其余条件为 p_{2i}>p_1(2 \le i \le k),p_{2i+1}<p_{2k+1}(2 \le i \le k-1)。

于是 p_1 \le k-1,p_{2k+1} \ge k+2，记 u=p_1,v=p_{2k+1}(u \le k-1,v \ge k+2)。

和上面那部分类似，不过要先选出 p_2,p_3 再用上面的步骤选其余的 p_x。

T_n&=\sum\limits_{u=1}^{k-1}\sum\limits_{v=k+2}^{2k+1}(v-u-1)(v-u-2)C_{v-u-3}^{v-k-2}(k-1)!(k-2)!\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}\sum\limits_{v=k+2}^{2k+1}(v-u-1)(v-u-2)C_{v-u-3}^{k-1-u}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}\sum\limits_{v=0}^{k-1}(v+k+1-u)(v+k-u)C_{v+k-1-u}^{k-1-u}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}\sum\limits_{v=0}^{k-1}(v+k+1-u)(v+k-u)\frac{(v+k-1-u)!}{(k-1-u)!v!}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}\sum\limits_{v=0}^{k-1}\frac{(v+k+1-u)!}{(k-1-u)!v!}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}(k+1-u)(k-u)\sum\limits_{v=0}^{k-1}\frac{(v+k+1-u)!}{(k+1-u)!v!}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}(k+1-u)(k-u)\sum\limits_{v=0}^{k-1}C_{v+(k+1-u)}^{k+1-u}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}(k+1-u)(k-u)C_{(k-1)+(k+1-u)+1}^{k+1-u+1}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}(k+1-u)(k-u)C_{2k+1-u}^{k+2-u}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}(k+1-u)(k-u)\frac{(2k+1-u)!}{(k+2-u)!(k-1)!}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}((k^2+k)-(2k+1)u+u^2)\frac{(2k+1-u)!}{(k+2-u)!(k-1)!}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}((2k+3-u)(2k+2-u)-(2k+4)(2k+2-u)\\&\ \ \ \ +(k^2+3k+2))\frac{(2k+1-u)!}{(k+2-u)!(k-1)!}\\ &=(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}\frac{(2k+3-u)!}{(k+2-u)!(k-1)!}\\&\ \ \ \ -(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}(2k+4)\frac{(2k+2-u)!}{(k+2-u)!(k-1)!}\\&\ \ \ \ +(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}(k^2+3k+2)\frac{(2k+1-u)!}{(k+2-u)!(k-1)!}\\ &=(k+1)k(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}\frac{(2k+3-u)!}{(k+2-u)!(k+1)!}\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}\frac{(2k+2-u)!}{(k+2-u)!k!}\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}\frac{(2k+1-u)!}{(k+2-u)!(k-1)!}\\ &=(k+1)k(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}C_{2k+3-u}^{k+1}\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}C_{2k+2-u}^{k}\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!\sum\limits_{u=1}^{k-1}C_{2k+1-u}^{k-1}\\ &=(k+1)k(k-1)!(k-2)!\sum\limits_{u=3}^{k+1}C_{u+(k+1)}^{k+1}\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!\sum\limits_{u=3}^{k+1}C_{u+k}^{k}\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!\sum\limits_{u=3}^{k+1}C_{u+(k-1)}^{k-1}\\ &=(k+1)k(k-1)!(k-2)!\left(-1-(k+2)-\frac{(k+3)(k+2)}{2}+\sum\limits_{u=0}^{k+1}C_{u+(k+1)}^{k+1}\right)\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!\left(-1-(k+1)-\frac{(k+2)(k+1)}{2}+\sum\limits_{u=0}^{k+1}C_{u+k}^{k}\right)\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!\left(-1-k-\frac{(k+1)k}{2}+\sum\limits_{u=0}^{k+1}C_{u+(k-1)}^{k-1}\right)\\ &=(k+1)k(k-1)!(k-2)!\left(-\frac{(k+3)(k+4)}{2}+\sum\limits_{u=0}^{k+1}C_{u+(k+1)}^{k+1}\right)\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!\left(-\frac{(k+2)(k+3)}{2}+\sum\limits_{u=0}^{k+1}C_{u+k}^{k}\right)\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!\left(-\frac{(k+1)(k+2)}{2}+\sum\limits_{u=0}^{k+1}C_{u+(k-1)}^{k-1}\right)\\ &=(k+1)k(k-1)!(k-2)!\left(-\frac{(k+3)(k+4)}{2}+C_{(k+1)+(k+1)+1}^{k+1+1}\right)\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!\left(-\frac{(k+2)(k+3)}{2}+C_{(k+1)+k+1}^{k+1}\right)\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!\left(-\frac{(k+1)(k+2)}{2}+C_{(k+1)+(k-1)+1}^{k-1+1}\right)\\ &=(k+1)k(k-1)!(k-2)!\left(-\frac{(k+3)(k+4)}{2}+C_{2k+3}^{k+2}\right)\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!\left(-\frac{(k+2)(k+3)}{2}+C_{2k+2}^{k+1}\right)\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!\left(-\frac{(k+1)(k+2)}{2}+C_{2k+1}^{k}\right)\\ &=-\frac{1}{2}(k-1)!(k-2)!((k+1)k(k+3)(k+4)-(2k+4)k(k+2)(k+3)\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +(k^2+3k+2)(k+1)(k+2))\\&\ \ \ \ +(k+1)k(k-1)!(k-2)!C_{2k+3}^{k+2}\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!C_{2k+2}^{k+1}\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!C_{2k+1}^{k}\\ &=-\frac{1}{2}(k-1)!(k-2)!\times 4\\&\ \ \ \ +(k+1)k(k-1)!(k-2)!C_{2k+3}^{k+2}\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!C_{2k+2}^{k+1}\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!C_{2k+1}^{k}\\ &=-2(k-1)!(k-2)!\\&\ \ \ \ +(k+1)k(k-1)!(k-2)!\frac{(2k+3)!}{(k+2)!(k+1)!}\\&\ \ \ \ -(2k+4)k(k-1)!(k-2)!\frac{(2k+2)!}{((k+1)!)^2}\\&\ \ \ \ +(k^2+3k+2)(k-1)!(k-2)!\frac{(2k+1)!}{k!(k+1)!}\\ &=-2(k-1)!(k-2)!\\&\ \ \ \ +\frac{(2k+3)!}{(k+2)(k+1)k(k-1)}\\&\ \ \ \ -(2k+4)\frac{(2k+2)!}{(k+1)^2 k(k-1)}\\&\ \ \ \ +(k^2+3k+2)\frac{(2k+1)!}{(k+1)k^2(k-1)}\\ &=-2(k-1)!(k-2)!\\&\ \ \ \ +(2k+3)(2k+2)\frac{(2k+1)!}{(k+2)(k+1)k(k-1)}\\&\ \ \ \ -(4k+8)\frac{(2k+1)!}{(k+1)k(k-1)}\\&\ \ \ \ +(k^2+3k+2)\frac{(2k+1)!}{(k+1)k^2(k-1)}\\ &=-2(k-1)!(k-2)!\\&\ \ \ \ +\frac{(2k+1)!}{(k+2)(k+1)k^2(k-1)}((2k+3)(2k+2)k-(4k+8)(k+2)k\\&\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +(k^2-3k+2)(k+2))\\ &=-2(k-1)!(k-2)!+\frac{(2k+1)!}{(k+2)(k+1)k^2(k-1)}(k^3-k^2-2k+4) \end{aligned}

于是：

\mathrm{ans}_n&=n!-2T_n\\ &=(2k+1)!+4(k-1)!(k-2)!-\frac{2(2k+1)!(k^3-k^2-2k+4)}{(k+2)(k+1)k^2(k-1)}\\ &=4(k-1)((k-2)!)^2+(2k+1)!\left(1-\frac{2(k^3-k^2-2k+4)}{(k+2)(k+1)k^2(k-1)}\right) \end{aligned}

总结

经过简单的推导，我们得到了 \mathrm{ans}_n 的非常简单的式子，如果固定模数，只需要预处理出 i! \bmod M(0 \le i \le n) 与 i^{-1} \bmod M(1 \le i \le n)，即可单次询问 O(1) 得到答案。

以上过程我计算总共花费 1.1h，由于推导过程十分基础，建议评绿。

:::info[AC 记录] AC Code:

/*
统计不合法的情况数 S 然后用 n! 来减。
记 T 为 p[1]<p[n] 不合法的数量，则 S=2T。（因为所有 p[i] 变为 n+1-p[i] 时限制不变）
n=3 特判（ans=4）
1. n=2k
所有限制为 [2i,2k;1](1<=i<=k-1),[1,2i+1;2k](1<=i<=k-1)
于是 p[2i]>p[1](1<=i<=k-1)；p[2i+1]<p[2k](1<=i<=k-1)
则 p[1]<=k,p[2k]>=k+1，记 p[1]=u,p[2k]=v(u<=k,v>=k+1)
T=sum u=1~k(sum v=k+1~2k(C(v-u-1,v-k-1)*((k-1)!)^2))
=((k-1)!)^2*sum u=1~k(sum v=k+1~2k(C(v-u-1,v-k-1)))
=((k-1)!)^2*sum u=1~k(sum v=0~k-1(C(v+(k-u),k-u)))
=((k-1)!)^2*sum u=1~k(C((k-1)+(k-u)+1,k-u+1))
=((k-1)!)^2*sum u=1~k(C(2k-u,k-u+1))
=((k-1)!)^2*sum u=1~k(C(2k-u,k-1))
=((k-1)!)^2*sum u=1~k(C(k-1+u,k-1))
=((k-1)!)^2*(-1+sum u=0~k(C(k-1+u,k-1)))
=((k-1)!)^2*(-1+C(k+(k-1)+1,k-1+1))
=((k-1)!)^2*(-1+C(2k,k))
=-((k-1)!)^2+(2k)!/k^2
ans=(2k)!-2T=(2k)!(1-2/k^2)+2((k-1)!)^2
2. n=2k+1
所有限制为 [2i,2k+1;1](1<=i<=k),[1,2i+1;2k+1](1<=i<=k-1),[1,2;2k+1],[3,2k+1;1]
于是 p[1]<p[2],p[3]<p[2k+1]；p[2i]>p[1](2<=i<=k)；p[2i+1]<p[2k+1](2<=i<=k-1)
则 p[1]<=k-1,p[2k+1]>=k+2，记 p[1]=u,p[2k+1]=v(u<=k-1,v>=k+2)
T=sum u=1~k-1(sum v=k+2~2k+1((v-u-1)*(v-u-2)*C(v-u-3,v-k-2)*(k-1)!*(k-2)!))
=(k-1)!*(k-2)!*sum u=1~k-1(sum v=k+2~2k+1((v-u-1)*(v-u-2)*C(v-u-3,v-k-2)))
=(k-1)!*(k-2)!*sum u=1~k-1(sum v=k+2~2k+1((v-u-1)*(v-u-2)*C(v-u-3,k-1-u)))
=(k-1)!*(k-2)!*sum u=1~k-1(sum v=0~k-1((v+k+1-u)*(v+k-u)*C(v+k-1-u,k-1-u)))
=(k-1)!*(k-2)!*sum u=1~k-1(sum v=0~k-1((v+k+1-u)!/(k-1-u)!/v!))
=(k-1)!*(k-2)!*sum u=1~k-1((k+1-u)*(k-u)*sum v=0~k-1((v+k+1-u)!/(k+1-u)!/v!))
=(k-1)!*(k-2)!*sum u=1~k-1((k+1-u)*(k-u)*sum v=0~k-1(C(v+k+1-u,k+1-u)))
=(k-1)!*(k-2)!*sum u=1~k-1((k+1-u)*(k-u)*C((k-1)+(k+1-u)+1,k+1-u+1))
=(k-1)!*(k-2)!*sum u=1~k-1((k+1-u)*(k-u)*C(2k+1-u,k+2-u))
=(k-1)!*(k-2)!*sum u=1~k-1((k+1-u)*(k-u)*(2k+1-u)!/(k+2-u)!/(k-1)!)
=(k-1)!*(k-2)!*sum u=1~k-1(((k^2+k)-(2k+1)u+u^2)*(2k+1-u)!/(k+2-u)!/(k-1)!)
=(k-1)!*(k-2)!*sum u=1~k-1((((4k^2+10k+6)-(4k+5)u+u^2)-(3k^2+9k+6)+(2k+4)u)*(2k+1-u)!/(k+2-u)!/(k-1)!)
=(k-1)!*(k-2)!*sum u=1~k-1(((2k+3-u)*(2k+2-u)-(2k+4)*(2k+2-u)+(k^2+3k+2))*(2k+1-u)!/(k+2-u)!/(k-1)!)
=(k-1)!*(k-2)!*sum u=1~k-1((2k+3-u)*(2k+2-u)*(2k+1-u)!/(k+2-u)!/(k-1)!-(2k+4)*(2k+2-u)*(2k+1-u)!/(k+2-u)!/(k-1)!+(k^2+3k+2)*(2k+1-u)!/(k+2-u)!/(k-1)!)
=(k-1)!*(k-2)!*sum u=1~k-1((2k+3-u)!/(k+2-u)!/(k-1)!-(2k+4)*(2k+2-u)!/(k+2-u)!/(k-1)!+(k^2+3k+2)*(2k+1-u)!/(k+2-u)!/(k-1)!)
=(k-1)!*(k-2)!*sum u=1~k-1((k+1)*k*C(2k+3-u,k+1)-(2k+4)*k*C(2k+2-u,k)+(k^2+3k+2)*C(2k+1-u,k-1))
=(k+1)*k*(k-1)!*(k-2)!*sum u=1~k-1(C(2k+3-u,k+1))
 -(2k+4)*k*(k-1)!*(k-2)!*sum u=1~k-1(C(2k+2-u,k))
 +(k^2+3k+2)*(k-1)!*(k-2)!*sum u=1~k-1(C(2k+1-u,k-1))
=(k+1)*k*(k-1)!*(k-2)!*sum u=3~k+1(C(u+(k+1),k+1))
 -(2k+4)*k*(k-1)!*(k-2)!*sum u=3~k+1(C(u+k,k))
 +(k^2+3k+2)*(k-1)!*(k-2)!*sum u=3~k+1(C(u+(k-1),k-1))
=(k+1)*k*(k-1)!*(k-2)!*(-1-(k+2)-(k+3)*(k+2)/2+sum u=0~k+1(C(u+(k+1),k+1)))
 -(2k+4)*k*(k-1)!*(k-2)!*(-1-(k+1)-(k+2)*(k+1)/2+sum u=0~k+1(C(u+k,k)))
 +(k^2+3k+2)*(k-1)!*(k-2)!*(-1-k-(k+1)*k/2+sum u=0~k+1(C(u+(k-1),k-1)))
=(k+1)*k*(k-1)!*(k-2)!*(-1-(k+2)-(k+3)*(k+2)/2+C((k+1)+(k+1)+1,k+1+1))
 -(2k+4)*k*(k-1)!*(k-2)!*(-1-(k+1)-(k+2)*(k+1)/2+C((k+1)+k+1,k+1))
 +(k^2+3k+2)*(k-1)!*(k-2)!*(-1-k-(k+1)*k/2+C((k+1)+(k-1)+1,k-1+1))
=(k+1)*k*(k-1)!*(k-2)!*(-1-(k+2)-(k+3)*(k+2)/2+C(2k+3,k+2))
 -(2k+4)*k*(k-1)!*(k-2)!*(-1-(k+1)-(k+2)*(k+1)/2+C(2k+2,k+1))
 +(k^2+3k+2)*(k-1)!*(k-2)!*(-1-k-(k+1)*k/2+C(2k+1,k))
=-(k-1)!*(k-2)!*((k+1)*k*(1+(k+2)+(k+3)*(k+2)/2)-(2k+4)*k*(1+(k+1)+(k+2)*(k+1)/2)+(k^2+3k+2)*(1+k+(k+1)*k/2))
 +(k+1)*k*(k-1)!*(k-2)!*C(2k+3,k+2)
 -(2k+4)*k*(k-1)!*(k-2)!*C(2k+2,k+1)
 +(k^2+3k+2)*(k-1)!*(k-2)!*C(2k+1,k)
=-(k-1)!*(k-2)!*(1/2)*((k+1)*k*(k+3)*(k+4)-2*(k+2)*k*(k+2)*(k+3)+(k+1)*(k+2)*(k+1)*(k+2))
 +(k+1)*k*(k-1)!*(k-2)!*C(2k+3,k+2)
 -(2k+4)*k*(k-1)!*(k-2)!*C(2k+2,k+1)
 +(k^2+3k+2)*(k-1)!*(k-2)!*C(2k+1,k)
=-(k-1)!*(k-2)!*(1/2)*4
 +(k+1)*k*(k-1)!*(k-2)!*C(2k+3,k+2)
 -(2k+4)*k*(k-1)!*(k-2)!*C(2k+2,k+1)
 +(k^2+3k+2)*(k-1)!*(k-2)!*C(2k+1,k)
=-2*(k-1)!*(k-2)!
 +(k+1)*k*(k-1)!*(k-2)!*(2k+3)!/(k+2)!/(k+1)!
 -(2k+4)*k*(k-1)!*(k-2)!*(2k+2)!/(k+1)!/(k+1)!
 +(k^2+3k+2)*(k-1)!*(k-2)!*(2k+1)!/k!/(k+1)!
=-2*(k-1)!*(k-2)!
 +(2k+3)!/((k+2)*(k+1)*k*(k-1))
 -(2k+4)*(2k+2)!/((k+1)*(k+1)*k*(k-1))
 +(k^2+3k+2)*(2k+1)!/(k*(k+1)*k*(k-1))
=-2*(k-1)!*(k-2)!
 +(2k+3)!/((k+2)*(k+1)*k*(k-1))
 -(4k+8)*(2k+1)!/((k+1)*k*(k-1))
 +(k^2+3k+2)*(2k+1)!/(k*(k+1)*k*(k-1))
=-2*(k-1)!*(k-2)!+(2k+1)!/((k+2)*k*(k+1)*k*(k-1))*((2k+3)*(2k+2)*k-(4k+8)*(k+2)*k+(k^2+3k+2)*(k+2))
=-2*(k-1)!*(k-2)!+(2k+1)!/((k+2)*(k+1)*k^2*(k-1))*(k^3-k^2-2k+4)
ans=n!-2T
=(2k+1)!-2*(-2*(k-1)!*(k-2)!+(2k+1)!/((k+2)*(k+1)*k^2*(k-1))*(k^3-k^2-2k+4))
=(2k+1)!+4*(k-1)!*(k-2)!-2*(2k+1)!/((k+2)*(k+1)*k^2*(k-1))*(k^3-k^2-2k+4)
=4*(k-1)!*(k-2)!+(2k+1)!*(1-2*(k^3-k^2-2k+4)/((k+2)*(k+1)*k^2*(k-1)))
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,m,k;
ll e,ans,u[1000009],v[1000009];
inline ll w(ll a,ll b){return !b?1:b==1?a:b&1?w(a*a%m,b>>1)*a%m:w(a*a%m,b>>1);}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m,k=n>>1,ans=0;
        if(n==3){cout<<"4\n";continue;}
        if(!(n&1)){
            e=1;
            for(int i=2;i<k;++i) e=e*i%m;
            ans=2*e*e%m;
            for(int i=k+1;i<n;++i) e=e*i%m;
            ans+=(2*k*(ll)k-4)%m*e%m;
            cout<<ans%m<<"\n";
        }
        else{
            u[0]=1;
            for(int i=1;i<=n;++i) u[i]=u[i-1]*i%m;
            v[n]=w(u[n],m-2);
            for(int i=n;i;--i) v[i-1]=v[i]*i%m;
            ans=(4*u[k-1]*u[k-2]%m+(1-2*(k*(ll)k%m*(k-1)%m-2*k+4)%m*v[k+2]%m*u[k-2]%m*v[k]%m*u[k-1])%m*u[n]%m+m)%m;
            cout<<ans<<"\n";
        }
    }
    return 0;
}
/*
#include<bits/stdc++.h>
using namespace std;
int n=20,a[109];
int main(){
    iota(a+1,a+n+1,1);
    for(int i=1;i<=n;++i){
        int l=(i==1?n:i-1),r=(i==n?1:i+1);
        cout<<min(a[l],a[r])<<","<<max(a[l],a[r])<<";"<<a[i]<<"\n";
        swap(a[l],a[r]);
    }
    return 0;
}
*/

:::

闲话

我在赛时一开始忘记特判 n=3 导致挂到了 10pts，瞪了 4min 才瞪出来。我太菜了/ll