首先通过手玩，发现对于小的 \(n\) 都有 \(m_{\max}\le n\)，于是直接猜测这个结论并尝试证明。
首先对于 \(n\le 4\) 的情况，首先可以直接通过手玩知道 \(m_{\max}\le n\)。
对于 \(n > 4\) 的情况，考虑 \(n\) 从小到大证明。
若 \(m > n\)，则 \(\sum\limits_{i = 1}^n \operatorname{deg}_i > 2n\)，那么一定存在 \(\operatorname{deg}_i > 2\)，且此时与 \(i\) 有连边的点一定不能与其他点有连边了。
此时只连了 \(\operatorname{deg}_i\) 条边，却独立出了 \(\operatorname{deg}_i + 1\) 个点，于是会递归到 \(m' = m - \operatorname{deg}_i, n' = n - \operatorname{deg}_i - 1\) 的情况，此时一定有 \(m' > n'\) 且对于 \(n'\) 一定满足 \(m'_{\max}\le n'\)，于是不存在合法的构造。
所以可以证得 \(m_{\max}\le n\)。
接下来考虑什么情况下能取到 \(m_{\max} = n\)。
首先类似上面的证明，可以知道一定不能存在 \(\operatorname{deg}_i > 2\)，即此时一定满足 \(\forall 1\le i\le n, \operatorname{deg}_i = 2\)。
考虑对于 \(i\)，令连边为 \((i, j), (i, k)\)，能够知道此时要满足条件只能连上 \((j, k)\) 这条边，然后递归到 \(n' = n - 3, m' = m - 3\) 的情况。
于是可以知道，只有当 \(n\bmod 3 = 0\) 时有 \(m_{\max} = n\)，此时对应的构造为 \(\frac{n}{3}\) 个三元环。
对于 \(n\bmod 3 \not = 0\)，直接构造一个菊花就可以构造出 \(m_{\max} = n - 1\)，但是注意最终形态不一定只有菊花，也可以是一些三元环加上一个菊花（但是菊花一定只有 \(1\) 个，因为如果多一个 \(m\) 最大就只能是 \(n - 2\) 了）。
然后来考虑计数。
首先因为 \(n\bmod 3 \not = 0\) 也可能有三元环出现，所以先考虑计数三元环。
此时可以考虑 dp，令 \(g_n\) 为点数为 \(3n\)，分出 \(n\) 个三元换的个数。
那么考虑 \(3n\) 所在的三元环，另外 \(2\) 个数就应该是 \(1\sim 3n - 1\) 中的任意 \(2\) 个，于是有 \(g_n = \binom{3n - 1}{2}g_{n - 1}\)。
那么 \(n\bmod 3 = 0\) 就处理完了。
接下来考虑处理 \(n\bmod 3 \not = 0\) 的情况，那么就可以，枚举三元环的个数，然后对于菊花的点定根（注意 \(n = 2\) 时的特殊情况）就有：
\(\operatorname{ans} = \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor} g_{i} \dbinom{n}{3i}(n - 3i - [n - 3i = 2])\)。
但这样肯定是做不了线性的，于是观察 \(g_{n} = \binom{3n - 1}{2}g_{n - 1} = \frac{(3n - 1)(3n - 2)}{2}g_i = \frac{3n(3n - 1)(3n - 2)}{6n} g_{i - 1}\)。
所以有 \(g_n = \dfrac{(3n)!}{n!6^n}\)。
代入 \(\operatorname{ans}\) 有 \(\operatorname{ans} = - [n \bmod 3 = 2]\dbinom{n}{2}g_{\lfloor\frac{n}{3}\rfloor} + \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor} g_{i} \dbinom{n}{3i}(n - 3i) = - [n \bmod 3 = 2]\dbinom{n}{2}g_{\lfloor\frac{n}{3}\rfloor} + \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor} \dfrac{(3i)!n!(n - 3i)}{i!6^i(3i)!(n - 3i)!} = - [n \bmod 3 = 2]\dbinom{n}{2}g_{\lfloor\frac{n}{3}\rfloor} + n! \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor} \dfrac{(n - 3i)}{i!6^i(n - 3i)!}\)。
那么接下来的问题就是线性预处理 \(f'_n = \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor} \dfrac{n - 3i}{(n - 3i)!i!6^i} = \sum\limits_{i = 0}^{\lfloor\frac{n - 1}{3}\rfloor} \dfrac{n - 3i}{(n - 3i)!i!6^i} = \sum\limits_{i = 0}^{\lfloor\frac{n - 1}{3}\rfloor} \dfrac{1}{(n - 3i - 1)!i!6^i}\)。
所以令 \(f_n = \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor} \dfrac{1}{(n - 3i)!i!6!}\)，那么有 \(f'_n = f_{n - 1}\)。
然后考虑找 \(f_n\) 的递推关系。
考虑分母的 \(n - 3i\)，于是代入 \(f_{n - 3} = \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor - 1} \dfrac{1}{(n - 3i - 3)!i!6!} = \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor - 1} \dfrac{1}{(n - 3(i + 1))!i!6!} = \sum\limits_{i = 1}^{\lfloor\frac{n}{3}\rfloor} \dfrac{1}{(n - 3i)!(i - 1)6^{i - 1}} = \sum\limits_{i = 1}^{\lfloor\frac{n}{3}\rfloor} \dfrac{6i}{(n - 3i)!i!6^i} = \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor} \dfrac{6i}{(n - 3i)!i!6^i}\)。
那么肯定是想把 \(6i\) 消成常数的，那么从上面通分启发，代入 \(f_{n - 1} = \sum\limits_{i = 0}^{\lfloor\frac{n - 1}{3}\rfloor} \dfrac{1}{(n - 3i - 1)!i!6^i} = \sum\limits_{i = 0}^{\lfloor\frac{n - 1}{3}\rfloor} \dfrac{n - 3i}{(n - 3i)!i!6^i} = \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor} \dfrac{n - 3i}{(n - 3i)!i!6^i}\)。
所以发现有 \(\dfrac{f_{n - 3}}{2} + f_{n - 1} = \sum\limits_{i = 0}^{\lfloor\frac{n}{3}\rfloor} \dfrac{n}{(n - 3i)!i!6^i} = n f_n\)，所以有 \(f_n = \dfrac{f_{n - 1} + \frac{f_{n - 3}}{2}}{n}\)。
特殊处理一下 \(f_{0\sim 2}\) 的边界情况即可。
那么对于 \(n\bmod 3\not = 0\) 的情况，就有 \(\operatorname{ans} = - [n \bmod 3 = 2]\dbinom{n}{2}g_{\lfloor\frac{n}{3}\rfloor} + n!f_{n - 1}\)。
时间复杂度 \(\mathcal{O}(n + q)\)。
代码中的 \(f, g\) 含义是反过来的。
#include<bits/stdc++.h>
using ll = long long;
constexpr int maxn = 3e7 + 10, N = 3e7, M = 1e7;
ll mod;
inline ll qpow(ll a, ll b, ll v = 1) {
while (b) {
if (b & 1) (v *= a) %= mod;
(a *= a) %= mod, b >>= 1;
}
return v;
}
ll fac[maxn], ifac[maxn], inv[maxn];
inline ll binom(int n, int m) {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
ll f[maxn], g[maxn];
int main() {
int q;
scanf("%d%lld", &q, &mod);
for (int i = fac[0] = 1; i <= N; i++) fac[i] = fac[i - 1] * i % mod;
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N; i; i--) ifac[i - 1] = ifac[i] * i % mod;
for (int i = inv[0] = 1; i <= N; i++) inv[i] = ifac[i] * fac[i - 1] % mod;
const ll inv2 = inv[2], inv6 = inv[6];
ll pw = 1ll;
for (int i = 0; i <= M; i++) {
f[i] = fac[3 * i] * ifac[i] % mod * pw % mod;
(pw *= inv6) %= mod;
}
g[0] = g[1] = 1, g[2] = inv[2];
for (int i = 3; i <= N; i++) {
g[i] = (g[i - 1] + g[i - 3] * inv2 % mod) * inv[i] % mod;
}
for (int n; q--; ) {
scanf("%d", &n);
if (n % 3 == 0) {
printf("%lld\n", f[n / 3] % mod);
continue;
}
ll ans = g[n - 1] * fac[n] % mod;
if (n % 3 == 2) {
(ans += mod - binom(n, 2) * f[n / 3] % mod) %= mod;
}
printf("%lld\n", ans);
}
return 0;
}