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 \leq i, j \leq n)$ 总共会造成的贡献为多少，由于所有数对是等价的（还是沿用那句话，我们并不关心哪个数大哪个数小，只关心它们在不在自己的位置上）。

我们进行分类讨论：

$p_{j} \neq i, p_{i} \neq j$ 的情况。容易发现这种情况可以两两配对形成双射（只要交换 $i, j$ 就可以了），并且配对的其中一个必定造成一点贡献，另一个必定不会（显然 $j$ 在 $i$ 左边会造成贡献，反过来就不会）。另外值得一提的是，此时我们统计的是 $i, j$ 两个值产生的贡献，因为 $p_{i}, p_{j}$ 两个位置上的贡献会在计算其他数对的时候被统计。为方便叙述，我们称满足这种情况的错排构成的集合为 $A$ 。
$p_{j} \neq i, p_{i} = j$ 或 $p_{i} \neq j, p_{j} = i$ 的情况，此时我们令不等的那个为1 $k$ ，此时统计的是 $p_{i}, p_{j}$ 两个位置上产生的贡献。
- 若 $kj $，我们也可以类似地构成双射，$ p_i=k,p_j=i $和$ p_i=j,p_j=k $其中一种情况会贡献，另一个则不会（另外我们并不在意另一个数的具体位置，它会在$ i'=k,j'=i $（或者其他类似的，这里我说的比较不严谨，但是你能懂这个意思）时被统计到），为方便叙述，我们称满足这种情况的错排构成的集合为$ B$。
- 若 $i < k < j$ ，我们仍可以像上面一样构成双射，但需要注意，此时两边都会有贡献，这个我们后面再讲，我们称这种情况的集合为 $B^{'}$ 。
$p_{i} = j, p_{j} = i$ 的情况，这种情况并不能构成双射，但是这样显然会构成逆序对，并且它十分好统计，我们参考之前算错排个数的思想，容易推出这种情况的个数为 $f_{n - 2}$ ，我们称这种情况的构成的集合为 $C$ 。

容易发现， $A \cup B \cup B^{'} \cup C$ 恰好就等于所有错排构成的集合，我们可以_~很快地~ $O (1)$ 地算出 $\frac{| A | + | B | + | B^{'} | + 2 | C |}{2} = \frac{f_{n} + f_{n - 2}}{2}$ 。对于所有数对，我们再乘以 $\frac{n \cdot (n - 1)}{2}$ 就可以得到答案。

但是这并不正确，我们之前提到了 $B^{'}$ 中所有元素都会产生贡献，而我们只计算了 $\frac{| B^{'} |}{2}$ 个情况，本着多退少补的原则，我们需要加上这一部分。

考虑有多少种数对会组成 $B^{'}$ ，容易想到，每一个三元组 $(i, j, k) (i < k < j, 1 \leq i, j, k \leq n)$ 都会构成一组 $B^{'}$ （感性理解一下， $B^{'}$ 需要左右夹着中间一个）。

接下来我们考虑 $| B^{'} |$ 的大小，由于所有数是等价的所以对于固定的 $n$ ，所有的 $| B^{'} |$ 应该也是相等的。

先考虑 $p_{i} = j, p_{j} = k$ 的情况，另一种直接乘以二即可，类似于算错排个数的思路，我们分 $p_{k} = i$ 和 $p_{k} \neq i$ 的情况讨论，这里请读者自行思考不展开讲，得到的式子就是 $| B^{'} | = 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

#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);
    }
}

T3

题解

10pts

20pts

40~80pts

100pts

code

Comments