T3
题解
10pts
暴力 dfs。
20pts
状压 dp。状态为当前选了的数，保存这样的方案数和逆序对总数枚举下一个数推到下一个状态，转移方程不难推，反正是部分分不展开讲，可能需要打表防止 $T$ 过大。
40~80pts
这几个点意义不明 我不知道有什么方法卡过这几个点。
100pts
首先我们需要学会求长度为 $n$ 的错排的个数。
设 $f_i$ 表示长度为 $i$ 的错排个数。
首先，很显然 $f_1=0,f_2=1$。
另外特别注意一下 $f_0=1$。
对于 $f_n$，我们考虑将 $n$ 放在位置 $p_x$ 上。
假如将 $x$ 放在 $p_n$ 上，容易发现这样的方案有 $f_{n-2}$ 种，因为我们并不关心每个数的具体大小，只关心它在不在自己的位置上，既然已经确定了两个数不动，那其他数便有 $f_{n-2}$ 种放法。
假如 $x$ 不在 $p_n$ 上，沿用刚才的思路，我们只关心每个数在不在自己的位置上，由于我们规定 $x$ 不在 $p_n$ 上，所以我们就可以把 $x$ 视作 $n$，故此时 $f_n=f_{n-1}$。
由于除了当前数外每个数都可能成为 $x$，状态转移方程为 $f_i=f_{i-1}\cdot(i-1)+f_{i-2}\cdot(i-1)$。
下面我们进行逆序对的计算。
考虑在长度为 $n$ 的错排中每一个数对 $(i,j)(i<j,1 \le i,j \le n)$ 总共会造成的贡献为多少，由于所有数对是等价的（还是沿用那句话，我们并不关心哪个数大哪个数小，只关心它们在不在自己的位置上）。
我们进行分类讨论：
-
$p_j\ne i,p_i \ne j$ 的情况。容易发现这种情况可以两两配对形成双射（只要交换 $i,j$ 就可以了），并且配对的其中一个必定造成一点贡献，另一个必定不会（显然 $j$ 在 $i$ 左边会造成贡献，反过来就不会）。另外值得一提的是，此时我们统计的是 $i,j$ 两个值产生的贡献，因为 $p_i,p_j$ 两个位置上的贡献会在计算其他数对的时候被统计。为方便叙述，我们称满足这种情况的错排构成的集合为 $A$。
-
$p_j \ne i,p_i = j$ 或 $p_i \ne j,p_j = i$ 的情况，此时我们令不等的那个为1 $k$，此时统计的是 $p_i,p_j$ 两个位置上产生的贡献。
- 若 $k
- 若 $i < k < j$，我们仍可以像上面一样构成双射，但需要注意，此时两边都会有贡献，这个我们后面再讲，我们称这种情况的集合为 $B'$。
- 若 $k
- $p_i=j,p_j=i$ 的情况，这种情况并不能构成双射，但是这样显然会构成逆序对，并且它十分好统计，我们参考之前算错排个数的思想，容易推出这种情况的个数为 $f_{n-2}$，我们称这种情况的构成的集合为 $C$。
容易发现，$A \cup B \cup B' \cup C$ 恰好就等于所有错排构成的集合，我们可以~很快地~ $O(1)$ 地算出 $\frac{\left| A \right|+\left| B \right|+\left| B' \right|+2\left| C \right|}{2}=\frac{f_n+f_{n-2}}{2}$。对于所有数对，我们再乘以 $\frac{n\cdot(n-1)}{2}$ 就可以得到答案。
但是这并不正确，我们之前提到了 $B'$ 中所有元素都会产生贡献，而我们只计算了 $\frac{\left| B' \right|}{2}$ 个情况，本着多退少补的原则，我们需要加上这一部分。
考虑有多少种数对会组成 $B'$，容易想到，每一个三元组 $(i,j,k)(i < k < j ,1 \le i,j,k \le n)$ 都会构成一组 $B'$（感性理解一下，$B'$ 需要左右夹着中间一个）。
接下来我们考虑 $\left| B' \right|$ 的大小，由于所有数是等价的所以对于固定的 $n$，所有的 $\left| B' \right|$ 应该也是相等的。
先考虑 $p_i=j,p_j=k$ 的情况，另一种直接乘以二即可，类似于算错排个数的思路，我们分 $p_k=i$ 和 $p_k \ne i$ 的情况讨论，这里请读者自行思考不展开讲，得到的式子就是 $\left| B' \right| = 2 \cdot(f_{n-2}+f_{n-3})$。
综上所述，预处理 $f$ 后，长度为 $n$ 的错排中逆序对数为 $\frac{f_{n}+f_{n-2}}{2}\times\frac{n\cdot(n-1)}{2}+\frac{2\cdot(f_{n-2}+f_{n-3})}{2}\times\frac{n\cdot(n-1)\cdot(n-2)}{6}$（$\frac{n\cdot(n-1)\cdot(n-2)}{6}$ 为三元组的个数）。
我们可以进行一些简单的化简，容易发现 $f_{n-2}+f_{n-3}=\frac{f_{n-1}}{n-2}$，故最终式子为：
$$\frac{f_{n}+f_{n-2}}{2}\times\frac{n\cdot(n-1)}{2}+\frac{f_{n-1}\cdot n\cdot(n-1)}{6}$$
code
code
#include<iostream>
#include<algorithm>
#include<string.h>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#include<vector>
#define pbk(a) emplace_back(a)
#define forup(i,s,e) for(register ll i=(s);i<=(e);i++)
#define fordown(i,s,e) for(register ll i=(s);i>=(e);i--)
#define abs(x) (((x)^((x)>>63))-((x)>>63))
using namespace std;
#define gc getchar()
inline ll read(){
ll x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
const ll N=1e7+5,inf=0x3f3f3f3f,mod=998244353;
ll t,n;
ll f[N];
ll inv2,inv6;
ll ksm(ll a,ll b){
ll c=1;
while(b){
if(b&1) c=c*a%mod;
a=a*a%mod;
b>>=1;
}
return c;
}
signed main(){
inv2=ksm(2,mod-2);inv6=ksm(6,mod-2);//预处理 2 和 6 的逆元
f[2]=1;f[3]=2;f[0]=1;
forup(i,4,1e7){
f[i]=(f[i-2]*(i-1)%mod+f[i-1]*(i-1)%mod)%mod;
}
t=read();
while(t--){
n=read();
if(n==1){puts("0");continue;}
ll shuangshe=(f[n]+f[n-2])*inv2%mod*n%mod*(n-1)%mod*inv2%mod;
ll trible=n*(n-1)%mod*inv6%mod;
ll add=(trible*f[n-1]%mod)%mod;
printf("%lld\n",(shuangshe+add)%mod);
}
}