题意相当于计数满足如下条件的长度为 的排列 ：

把条件转换一下，就是对于每个 ，要么 （自己匹配自己），要么存在 满足 （即找一个别的位置匹配）；考虑 比较小的时候暴力怎么做，因为 特别小，所以考虑状压 DP：由于 ，所以运用 NOI2023 桂花树 的方法，假设当前考虑到了第 位，用一个集合 表示第 位的状态（ 表示该位已经匹配， 表示待匹配）， 表示这种状态下的答案，最终答案即为 。

有如下几种转移（下文中 表示二进制下的按位左移，其他符号类似）：

  • ： 自己匹配自己；
  • ：将 设为未匹配；
  • ：需要满足 的第 位为 ，用 匹配前面的一个未匹配的 ；

特判一下 的情况，即必须把最早的那一位匹配掉，否则不满足第二个条件。

这个 DP 的过程可以矩阵快速幂优化；对于每个 预处理出转移矩阵的二的非负整数次方，查询时直接暴力做。

参考实现代码（C++17）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef vector<vector<int> > matrix;
const int p=998244353;
inline void chadd(int &x,int y){
  if((x+=y)>=p)x-=p;
}
inline matrix operator *(matrix a,matrix b){
  matrix c(a.size(),vector<int>(b[0].size()));
  for(int i=0;i<a.size();i++)
    for(int j=0;j<b[0].size();j++)
      for(int k=0;k<a[0].size();k++)
        chadd(c[i][j],1ll*a[i][k]*b[k][j]%p);
  return c;
} // 矩阵乘法
signed main(){
  ios::sync_with_stdio(false);
  vector f(8,vector<matrix>(63));
  for(int k=0;k<8;k++){
    f[k][0].resize(1<<k,vector<int>(1<<k));
    for(int S=0;S<1<<k;S++)
      if(S>>k-1&1)f[k][0][S][S<<1&(1<<k)-1]=1;
      else{
        f[k][0][S][S<<1]=f[k][0][S][S<<1|1]=1;
        for(int j=0;j<k-1;j++)
          if(S>>j&1)f[k][0][S][(S^1<<j)<<1]=1;
      } // 处理若干种转移
    for(int i=1;i<63;i++)
      f[k][i]=f[k][i-1]*f[k][i-1];
  } // 预处理转移矩阵
  int t; cin>>t;
  while(t--){
    int n,k; cin>>n>>k;
    matrix s(1,vector<int>(1<<k)); s[0][0]=1;
    for(int i=0;i<63;i++)
      if(n>>i&1)s=s*f[k][i];
    cout<<s[0][0]<<'\n';
  } // 回答询问
  return 0;
}