题解：P16351 「Gensokyo OI Round 1」秘神之钥
Cx114514
·
·
题解
题目链接：「Gensokyo OI Round 1」秘神之钥
神秘计数题。
先考虑什么样的排列是不满足条件的。
手玩或者打表一下不难发现，第 i 次操作时的 p_i 一定是初始状态下的 a_1 或 a_n，且 p_1 和 p_n 永远相邻。
可以分类讨论一下：n 为奇数或偶数。
这个时候只要观察一下另外一个相邻数会是什么。当 n 为偶数时，可以发现和 p_1 相邻的会是所有的偶数位，而和 p_n 相邻的是所有的奇数位。接下来我们考虑怎么计算答案：
考虑 p_1<p_n 的情况，首先枚举一下 p_1 的值，设其为 i，则所有偶数位都需要 >i，但是因为 p_n 比较特殊，所以我们先钦定另外 \left(\frac{n}{2}-1\right) 个数 >i，这样的方案数为 A_{n-i}^{\frac{n}{2}-1}。剩下的数可以随便排列，但要注意 p_n 一定要是其中最大的，所以方案数为 \left(\frac{n}{2}-1\right)!
得到结果为：
\sum\limits_{i=1}^{n}A_{n-i}^{\frac{n}{2}-1}\left(\frac{n}{2}-1\right)!
但是这样会多算，要考虑最终 p_n<p_1 的情况，这种情况当且仅当 p_n=\frac{n}{2}，p_{1}=\frac{n}{2}+1。剩下的奇数位都小于 p_{n}，偶数位都大于 p_1，这部分方案数为 \left[\left(\frac{n}{2}-1\right)!\right]^2。
最终方案数为：
\sum\limits_{i=1}^{n}A_{n-i}^{\frac{n}{2}-1}\left(\frac{n}{2}-1\right)!-\left[\left(\frac{n}{2}-1\right)!\right]^2
接下来考虑 $n$ 为奇数的情况。依旧手玩或打表不难发现，$p_1$ 会和所有的偶数位以及 $p_2$ 相邻，$p_n$ 回合所有的奇数位以及 $p_3$ 相邻。
考虑 $p_1<p_n$ 的情况，$p_1<p_2,p_3<p_n$，首先 $p_2$ 和 $p_3$ 的位置可以分出先后，方案数为 $2$。接下来可以看作剩余的偶数位不能 $<a_1$，剩余的奇数位不能 $>a_n$ 的方案数。这个可以枚举一下有多少个偶数位 $<a_n$，设其有 $i$ 个。选择数字的方式有 $\binom{\frac{n-1}{2}-1}{i}$，接下来可以看作每次往空位中插入一个数字，方案数为 $3^{\overline{i}}$，剩下的 $\left(\frac{n-1}{2}-1-i\right)$ 个数可以随便排，方案数为 $\left(\frac{n-1}{2}-1-i\right)!$。接下来奇数位上的数也可以理解为插空位，方案数为 $\left(4+i\right)^{\overline{\frac{n-1}{2}-2}}$。
因此最终答案为：
$$2\sum\limits_{i=0}^{\frac{n-1}{2}-1}3^{\overline{i}}\binom{\frac{n-1}{2}-1}{i}\left(\frac{n-1}{2}-1-i\right)!\left(4+i\right)^{\overline{\frac{n-1}{2}-2}}$$
对于 $p_1>p_n$ 的情况，答案是一样的，乘 $2$ 即可。
代码：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int T, n, mod, ans, fac[1000005], inv[1000005], facinv[1000005];
int A(int x, int y)
{
if (y > x) return 0;
return fac[x] * facinv[x - y] % mod;
}
int C(int x, int y)
{
return (fac[x] * facinv[x - y] % mod) * facinv[y] % mod;
}
signed main()
{
fac[0] = 1;
cin >> T;
while (T--)
{
ans = 0;
cin >> n >> mod;
for (int i = 1; i <= n; i++)
fac[i] = fac[i - 1] * i % mod;
inv[0] = 0;
inv[1] = 1;
for(int i = 2; i <= n; ++ i)
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
facinv[0] = 1;
for (int i = 1; i <= n; i++)
facinv[i] = facinv[i - 1] * inv[i] % mod;
if (n == 3)
{
cout << 4 << endl;
continue;
}
if (n % 2 == 0)
{
for (int i = 1; i <= n; i++)
{
ans = (ans + A(n - i, n / 2 - 1) * fac[n / 2 - 1]) % mod;
}
cout << (fac[n] - (ans - fac[n / 2 - 1] * fac[n / 2 - 1] % mod) * 2 % mod + mod) % mod << endl;
}
else
{
for (int i = 0; i <= n / 2 - 1; i++)
{
ans = (ans + ((A(3 + i - 1, i) * C(n / 2 - 1, i) % mod) * fac[n / 2 - 1 - i] % mod) * A(4 + i + n / 2 - 3, n / 2 - 2) % mod) % mod;
}
cout << (fac[n] - 4 * ans % mod + mod) % mod << endl;
}
}
return 0;
}
```