C++(g++ 7.5.0) 解法, 执行用时: 587ms, 内存消耗: 688K, 提交时间: 2023-05-02 14:54:34

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;

int M;
int n, num, dig[13], fail[13], nxt[13][13];

struct Mat{
	int a[120][120];
	void clear(){
        memset(a, 0, sizeof a);
    }
	void init()
	{
		memset(a, 0, sizeof a);
		for(int i = 1; i <= M; i++)
			a[i][i] = 1;
	}
};

Mat operator *(const Mat &x, const Mat &y){
	Mat res;
	res.clear();
	for(int i = 1; i <= M; i++){
		for(int j = 1; j <= M; j++){
			for(int k = 1; k <= M; k++){
				res.a[i][j] = (res.a[i][j] +  (ll)x.a[i][k] * y.a[k][j]) % mod;
			}
		}
	}
	return res;
}

Mat mypow(Mat a, int b){
	Mat ans;
	ans.init();
	while(b){
		if(b & 1)
			ans = ans * a;
		a = a * a;
		b >>= 1;
	}
	return ans;
}

void KMP() {
    fail[1] = 0;
	for(int i = 2, j = 0; i <= num; ++i) {
		while(j && dig[j + 1] != dig[i])
			j = fail[j];
		if(dig[j + 1] == dig[i])
			++j;
		fail[i] = j;
	}
	for(int i = 0; i <= num; ++i){
		for(int j = 0; j <= 9; ++j){
			if(i == num)
				nxt[i][j] = num;
			else{
				int k = i;
				while(k && dig[k + 1] != j)
					k = fail[k];
				if(dig[k + 1] == j)
					++k;
				nxt[i][j] = k;
			}
		}
	}
}

void solve() {
	int k;
	cin >> n >> k;
	num = 0;
	while(k) {
		dig[++num] = k % 10;
        k /= 10; 
    }
	reverse(dig + 1, dig + num + 1);
	ll ans = 0;
	if(num <= n + 1){
		ans = 1;
		if(dig[1] != 1)
			ans = 0;
		for(int i = 2; i <= num; i++)
			if(dig[i] != 0)
                ans = 0;
	}
    KMP();
	M = (num + 1) * 11;
	Mat dp;
	dp.clear();
	for(int i = 0; i <= num; ++i)
	{
		for(int j = 0; j <= 10; ++j){
			int row = i * 11 + j + 1;
			for(int c = 0; c <= 9; c++){
				int nxt_mat = nxt[i][c];
				int nxt_rem = (j * 10 + c) % 11;
				int nxt = nxt_mat * 11 + nxt_rem + 1;
				dp.a[row][nxt] = 1;
			}
		}
	}
	dp = mypow(dp, n);
	int r = 1;
	for(int i = 0; i <= num; ++i) {
		for(int j = 0; j <= 10; ++j) {
			int c = i * 11 + j + 1;
			if(i == num || j == 0)
				ans = (ans + dp.a[r][c]) % mod;
		}
	}
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while(T--) {
		solve();
	}
}

C++ 解法, 执行用时: 172ms, 内存消耗: 632K, 提交时间: 2021-06-20 15:02:21

#include<algorithm>
#include<cstring>
#include<cctype>
#include<cstdio>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
const int N=105,mod=998244353;
int n,k,tot,a[N],id[20][20],m,nxt[N],K;
typedef long long LL;
LL f[N],f1[N],mxt[N][N],mxt1[N][N],ans;

bool check()
{
	rep(i,2,tot) if(a[i]) return 0;
	if(tot>n+1) return 0;
	return a[1]==1;
}

void solve()
{
	scanf("%d%d",&n,&k);
	K=k;
	tot=0;
	while(k) a[++tot]=k%10,k/=10;
	rep(i,1,tot/2) swap(a[i],a[tot-i+1]);
	rep(i,2,tot)
	{
		int x=nxt[i-1];
		while(x && a[x+1]!=a[i]) x=nxt[x];
		if(a[x+1]==a[i]) nxt[i]=x+1; else nxt[i]=x;
	}
	m=0;
	rep(i,0,10) rep(j,0,tot) id[i][j]=++m;
	rep(i,1,m) rep(j,1,m) mxt[i][j]=0;
	rep(i,0,10) rep(j,0,tot)
		rep(x,0,9)
		{
			int p=(i*10+x)%11;
			int q=j;
			if(j!=tot)
			{
				while(q && a[q+1]!=x) q=nxt[q];
				if(a[q+1]==x) ++q;
			}
			++mxt[id[p][q]][id[i][j]];
		}
	ans=check();
	rep(i,1,m) f[i]=0;
	f[id[0][0]]=1;
	while(n)
	{
		if(n&1)
		{
			rep(i,1,m) f1[i]=0;
			rep(i,1,m) rep(j,1,m) f1[i]=(f1[i]+f[j]*mxt[i][j])%mod;
			rep(i,1,m) f[i]=f1[i];
		}
		rep(i,1,m) rep(j,1,m) mxt1[i][j]=0;
		rep(i,1,m) rep(j,1,m) rep(k,1,m) mxt1[i][k]=(mxt1[i][k]+mxt[i][j]*mxt[j][k])%mod;
		rep(i,1,m) rep(j,1,m) mxt[i][j]=mxt1[i][j];
		n>>=1;
	}
	rep(i,0,tot) ans=(ans+f[id[0][i]])%mod;
	rep(i,1,10) ans=(ans+f[id[i][tot]])%mod;
	printf("%lld\n",ans);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;
}