把\(p_i>p_{i+1}\)的位置个数称为间隔数
首先想到一个暴力做法。从小到大挨个添加1-n中的每个数，注意到添加数i时，只能添加到当前序列的最后11个位置中，否则逆序对数就会超。令\(dp_{i,j,p,msk}\)表示当前添加到数i，当前逆序对数为j，间隔数为p，msk是一个集合表示当前序列最后11个位置中哪些满足\(p_i>p_{i+1}\)。转移比较简单。但是这个dp的第一维是n，但n很大。矩阵快速幂也是不行的，后面的维度也很大。
我们考虑把一个长度为n的排列分段。令\(mx_i\)表示\(max_{j=1}^i p_j\)。我们找到从左往右第一个满足\(mx_i=i\)的位置，也就是第一个满足\(p_1\cdots p_i\)是一个排列的位置，然后把1-i分为一段，数组剩下的部分统一减i，然后不断进行同样的分段操作直到序列用完。发现分出的每一段都是一个"小的排列"，且左侧的一个小排列中的所有\(p_i\)都小于右侧任意一个小排列中的\(p_i\)。注意到两个段之间不会贡献任何的逆序对数或间隔数，所以排列p的逆序对数和间隔数等于每一小段内部的逆序对数和间隔数之和。
一个小段的长度如果>12，那它的逆序对数就>11，所以此时的p肯定不合法。证明：令小段为一个1-k的排列\(b_1\cdots b_k\)，其前缀max为\(c_1\cdots c_k\)。对于任意\(1\le i<k\)，满足\(b_i<c_i\)。我们从左往右一个个加入\(b_i\)，当加入到i(\(1\le i <k\))时，如果还有满足\(x<b_i\)的x没被加入，那肯定能至少形成一个还没被统计的逆序对；如果不存在这样的x，那肯定存在一个j满足\(j<i,b_j>b_i\)且加入j时有不止一个这样的x，我们现在加入i只是消耗了加入j时产生的一个逆序对而已。综上，总的逆序对个数一定会\(\ge k-1\)。因此我们可以用一个简单的背包算出数组\(f_{i,j,p}\)表示长度为i，逆序对数为j，间隔数为p的小段个数。为了保证对于任意\(1\le i<k\)满足\(b_i<c_i\)，dp的时候需要状压一下。
算出f数组之后为了得到n的答案，可能会想到多项式快速幂什么的，其实根本不需要多项式技巧。注意到小段的长度\(>1\)时，逆序对数和间隔数都不为0；而小段长度为1时这两个值都为0。所以长度>1的小段个数\(\le 11\)，再做一次背包，然后用插板法把其他长度为1的小段插进去即可。
没仔细算时间复杂度，反正不高。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define pdd pair <double,double>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
const LL MOD=998244353;
LL qpow(LL x,LL a)
{
LL res=x,ret=1;
while(a>0)
{
if(a&1) (ret*=res)%=MOD;
a>>=1;
(res*=res)%=MOD;
}
return ret;
}
LL t,n,k,x,dp[4100][20][20][20];//dp[msk][k][x][lst]
LL dp2[20][30][20][20];//dp2[cnt][lensum][k][x]
LL rinv[100];
LL C(LL nn,LL mm)
{
LL ret=1;for(LL i=nn;i>=nn-mm+1;--i) (ret*=i)%=MOD;
repn(i,mm) (ret*=rinv[i])%=MOD;
return ret;
}
int main()
{
fileio();
rep(i,95) rinv[i]=qpow(i,MOD-2);
LL lim=12;
dp[0][0][0][0]=1;
rep(msk,1<<lim) rep(kk,lim) rep(xx,lim) rep(lst,lim) if(dp[msk][kk][xx][lst])
{
LL sz=__builtin_popcount(msk);
if(msk==(1<<sz)-1&&msk>0) continue;
LL val=dp[msk][kk][xx][lst],addk=0;
for(int nxt=lim-1;nxt>=0;--nxt)
{
if(msk&(1<<nxt)) ++addk;
else if(kk+addk<=11) (dp[msk|(1<<nxt)][kk+addk][xx+(int)(lst>nxt)][nxt]+=val)%=MOD;
}
}
rep(i,1<<lim) rep(kk,lim) rep(xx,lim) repn(lst,lim) (dp[i][kk][xx][0]+=dp[i][kk][xx][lst])%=MOD;
dp2[0][0][0][0]=1;
rep(i,lim) rep(j,25) rep(kk,lim) rep(xx,lim) if(dp2[i][j][kk][xx])
{
LL val=dp2[i][j][kk][xx];
for(int nxtlen=2;nxtlen<=lim&&j+nxtlen<=24;++nxtlen) rep(kkk,lim-kk) rep(xxx,lim-xx)
{
LL msk=(1<<nxtlen)-1;
if(dp[msk][kkk][xxx][0]==0) continue;
(dp2[i+1][j+nxtlen][kk+kkk][xx+xxx]+=val*dp[msk][kkk][xxx][0])%=MOD;
}
}
cin>>t;
rep(tn,t)
{
cin>>n>>k>>x;
LL ans=0;
rep(cnt,k+1) for(int sz=cnt+cnt;sz<=24;++sz)
{
LL val=dp2[cnt][sz][k][x];
if(val==0||sz>n) continue;
LL tot=n-sz,spas=cnt+1;
LL mul=C(tot+spas-1,spas-1);
(ans+=val*mul)%=MOD;
}
cout<<ans<<endl;
}
termin();
}