看看这个sb麻烦但是易懂的题解吧
定义
f_{i,j,1}表示i位数中含有偶数个j的数
f_{i,j,0}表示i位数中含有奇数个j的数
一个含有偶数个j的i位数，可以分为以下两种情况产生：
- 一个含有偶数个j的i-1位数 *9（*9是因为除了j这个数字不能放，其他都可以放）
- 一个含有奇数个j的i-1位数的末尾加上j
一个含有奇数个j的i位数，可以分为以下两种情况产生：
- 一个含有奇数个j的i-1位数 *9（*9是因为除了j这个数字不能放，其他都可以放）
- 一个含有偶数个j的i-1位数的末尾加上j
追求效率，预处理一下即可
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
#define mod 998244353
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a[5010],ans,tmp,k,t;
long long f[114514][12][3];
/*
f[i][j][k]表示i位数中含有偶数个j的数 ,k=1
f[i][j][k]表示i位数中含有奇数个j的数 ,k=0
*/
int main() {
f[1][1][1]=8,f[1][2][1]=8,f[1][3][1]=8,f[1][0][1]=8,f[1][4][1]=8,f[1][5][1]=8,f[1][6][1]=8,f[1][7][1]=8,f[1][8][1]=8,f[1][9][1]=8;
f[1][1][0]=1,f[1][2][0]=1,f[1][3][0]=1,f[1][0][0]=1,f[1][4][0]=1,f[1][5][0]=1,f[1][6][0]=1,f[1][7][0]=1,f[1][8][0]=1,f[1][9][0]=1;
for(int i=2;i<=114514;i++){
for(int j=0;j<=9;j++){
f[i][j][1]=f[i-1][j][1]*9+f[i-1][j][0];
f[i][j][0]=f[i-1][j][0]*9+f[i-1][j][1];
f[i][j][1]%=mod;
f[i][j][0]%=mod;
/*
一个含有偶数个j的i位数，可以分为以下两种情况产生：
1. 一个含有偶数个j的i-1位数 *9（*9是因为除了j这个数字不能放，其他都可以放）
2. 一个含有奇数个j的i-1位数的末尾加上j
一个含有奇数个j的i位数，可以分为以下两种情况产生：
1. 一个含有奇数个j的i-1位数 *9（*9是因为除了j这个数字不能放，其他都可以放）
2. 一个含有偶数个j的i-1位数的末尾加上j
*/
}
}
cin>>t;
while(t--){
n=read(),k=read();
if(n==1) cout<<9<<'\n';
else cout<<f[n][k][1]<<'\n';
//注意，endl比'\n'要慢很多倍，是很多！
}
return 0;
}
