题目
题解
一眼看出是kmp+数位dp，然后就掉坑里了。。。
数位dp显然时间会爆。观察数据范围，发现k长度最多为5，加上mod11的11个余数，最多有55个状态，可以使用矩阵快速幂。
假设\(f_{i,j}\)代表余数为i，当前匹配位置为j的结果。任意写出递推式，直接套矩阵快速幂。初始只有\(f_{0,1}=1\)(匹配状态从1开始)，最终n次幂后将\(f_{i,len+1}\)和\(f_{0,i}\)全部加起来就是答案了。
#include<bits/stdc++.h>
using namespace std;
const int N = 500 + 10;
const int M = 998244353;
typedef long long ll;
#define endl ‘\n‘
typedef long long ll;
struct mat {
ll arr[N][N];
int n;
mat(const ll mx[N][N], int n) : n(n) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
arr[i][j] = mx[i][j];
}
}
}
mat(int n) : n(n){
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
arr[i][j] = 0;
}
}
}
mat(const mat& m) : mat(m.arr, m.n){}
mat operator * (const mat &rhs) const {
ll res[N][N];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
ll sum = 0;
for(int k = 1; k <= n; k++) {
sum += arr[i][k] * rhs.arr[k][j] % M;
sum %= M;
}
res[i][j] = sum;
}
}
return mat(res, n);
}
};
int di[20];
int nt[20];
ll ans[N];
int len;
void getnext() {
int i = 1, j = 0;
nt[i] = j;
while(i <= len) {
if(j == 0 || di[i] == di[j]) {
i++;
j++;
nt[i] = j;
} else {
j = nt[j];
}
}
}
int id(int st, int mod) {
return mod * 7 + st;
}
mat qpow(mat A, int b) {
mat res(100);
for(int i = 1; i <= res.n; i++) res.arr[i][i] = 1;
while(b) {
if(b & 1) {
res = res * A;
}
A = A * A;
b = (b >> 1);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
len = 0;
bool flag = true;
do{
if(k > 10 && (k % 10)) flag = false;
else if(k < 10 && k != 1) flag = false;
di[++len] = k % 10;
k /= 10;
} while(k);
if(n + 1 < len) flag = false;
getnext();
mat A(100);
auto &arr = A.arr;
for(int i = 1; i <= len + 1; i++) {
for(int j = 0; j < 11; j++) {
int id2 = id(i, j);
for(int k = 0; k <= 9; k++) {
int st = i, mod = j;
if(st < len + 1) {
while(st && k != di[st]) {
st = nt[st];
}
st++;
}
mod = (mod * 10 + k) % 11;
int id1 = id(st, mod);
arr[id1][id2]++;
}
}
}
mat res(qpow(A, n));
int tar = id(1, 0);
for(int i = 1; i <= 100; i++) {
ans[i] = res.arr[i][tar];
}
ll tans = 0;
for(int i = 0; i < 11; i++) {
tans += ans[id(len + 1, i)];
tans %= M;
}
for(int i = 1; i <= len; i++ ) {
tans += ans[id(i, 0)];
tans %= M;
}
cout << (tans + flag) % M << endl;
}
}