https://www.lydsy.com/JudgeOnline/problem.php?id=1009

阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为0

在构造好的next图上跑矩阵快速幂即可

/**************************************************************    Problem: 1009    User: walfy    Language: C++    Result: Accepted    Time:120 ms    Memory:1384 kb****************************************************************/ //#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")//#pragma GCC optimize("unroll-loops")#include
      
       #define fi first#define se second#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define vi vector
       
        //#define mod 1000000007#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pil pair
        
         #define pli pair
         
          #define pii pair
          
           #define cd complex
           
            #define ull unsigned long long#define base 1000000000000000000#define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12;const int N=200+10,maxn=200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; ll n,m,k;struct Node{ ll row,col; ll a[30][30];};Node mul(Node x,Node y,ll mod){ Node ans; ans.row=x.row,ans.col=y.col; memset(ans.a,0,sizeof ans.a); for(int i=0;i
            

q; fail[root]=root; for(int i=0;i<10;i++) { if(Next[root][i]==-1)Next[root][i]=root; else { fail[Next[root][i]]=root; q.push(Next[root][i]); } } while(!q.empty()) { int now=q.front(); q.pop(); if(End[fail[now]])End[now]=1; for(int i=0;i<10;i++) { if(Next[now][i]==-1)Next[now][i]=Next[fail[now]][i]; else { fail[Next[now][i]]=Next[fail[now]][i]; q.push(Next[now][i]); } } } } void solve() { Node A; A.row=A.col=tot; for(int i=0;i