虽然平时做过但是考场上肯定还是不会，不过没事干还是写一下吧
Myhill-Nerode
\text{Myhill-Nerode}
Myhill-Nerode
定理：给定一个语言
L
L
L
，定义在字符串上一个关系为，若对于所有的
z
z
z
，
x
z
xz
x
z
在
L
L
L
中当且仅当
y
z
yz
yz
在
L
L
L
中，则称
x
,
y
x,y
x
,
y
在同一个等价类中。因此它把所有有限字符串的集合划分成一个或多个等价类。
Myhill-Nerode
\text{Myhill-Nerode}
Myhill-Nerode
定理声称在
L
L
L
的最小自动机中状态的数目等价于在
L
L
L
中诱导出的等价类的数目。
容易发现，语言
L
L
L
可以被有限状态机接受，当且仅当等价类的数目是有限的。
Gym 102586J
考虑用等价类构造
D
F
A
DFA
D
F
A
，还要为每一类找一个代表元。这里必须指出的是，
L
L
L
中的字符串一定在同一个等价类中，这个等价类也是接收点。
这里假定有限字符串集合长度不超过
L
L
L
，然后暴搜求出每个字符串的等价类即可。
如何证明取
L
=
10
L=10
L
=
10
的正确性？
思维小实验
假设存在一个
D
F
A
DFA
D
F
A
d
(
k
)
d(k)
d
(
k
)
能正确识别长度不超过
k
k
k
的好串，据此可以构造出一个
N
F
A
NFA
NF
A
能正确识别长度不超过
k
+
2
k+2
k
+
2
的好串（其构造方法是，在原
D
F
A
DFA
D
F
A
的基础上建立
ϵ
\epsilon
ϵ
，然后建一个子
D
F
A
DFA
D
F
A
表示操作的长度为
3
3
3
的段，再用
ϵ
\epsilon
ϵ
连回在原
D
F
A
DFA
D
F
A
中所对应的字符边即可），再将其转化为
D
F
A
DFA
D
F
A
d
(
k
+
2
)
d(k+2)
d
(
k
+
2
)
（最常用的方法是幂极构造），并最小化。
如果
d
(
k
)
d(k)
d
(
k
)
等价于
d
(
k
+
2
)
d(k+2)
d
(
k
+
2
)
，我们就能得到
d
(
k
)
=
d
(
k
+
2
)
=
d
(
k
+
4
)
=
⋯
d(k)=d(k+2)=d(k+4)=\cdots
d
(
k
)
=
d
(
k
+
2
)
=
d
(
k
+
4
)
=
⋯
，这也就是我们所要求的
D
F
A
DFA
D
F
A
。验证即可。
CF956F
考虑构造一个
F
A
FA
F
A
来识别不超过
n
n
n
位的
f
(
m
)
≤
k
f(m)\le k
f
(
m
)
≤
k
的数字串
F
A
FA
F
A
的状态是背包容量，字母表是
0
∼
9
0\sim 9
0
∼
9
，原来状态是
c
c
c
，读入一个数字
d
d
d
，可以转移到
c
+
d
c+d
c
+
d
和
∣
c
−
d
∣
|c-d|
∣
c
−
d
∣
，显然这是一个
N
F
A
NFA
NF
A
，可以设置状态数为
100
100
100
，然后大力幂集转移。
可以用长度为
100
100
100
的
bitset
\text{bitset}
bitset
实现幂集，用一个哈希表记录某个
bitset
\text{bitset}
bitset
出现过没有。
理论复杂度
O
(
2
100
)
O(2^{100})
O
(
2
100
)
。这非常不科学。这种方法还是比较大胆的。
我完全没这个魄力好吧
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=1e5+5;
int n,K,tot,to[N][10],c[100],len;
ll l,r,dp[N][20][10];
map<__int128,int>id;
__int128 has(bitset<100>&b){
__int128 x=0;
for(int i=99;i>=0;i--){
x*=2;if(b[i])x++;
}return x;
}
int dfs(bitset<100>&b){
int x;if(id[has(b)])return id[has(b)];
x=id[has(b)]=++tot;
for(int i=0;i<10;i++){
if(b._Find_first()<=i)dp[tot][0][i]=1;
}
for(int i=0;i<10;i++){
bitset<100>b2=(b<<i)|(b>>i);
for(int j=0;j<i;j++)if(b[j])b2[i-j]=1;
to[x][i]=dfs(b2);
}return x;
}
ll dfs2(int x,int y,int z){
if(!z)return dp[y][x][K];
if(x==0)return dp[y][0][K];
ll res=0;
for(int i=0;i<=c[x];i++){
res+=dfs2(x-1,to[y][i],i==c[x]);
}return res;
}
ll solve(ll x){
len=0;while(x)c[++len]=x%10,x/=10;
return dfs2(len,1,1);
}
int main(){
bitset<100>e;e[0]=1;
int T;cin>>T,dfs(e);
for(int l=0;l<10;l++){
for(int i=1;i<=18;i++){
for(int j=1;j<=tot;j++){
for(int k=0;k<10;k++){
dp[j][i][l]+=dp[to[j][k]][i-1][l];
}
}
}
}
while(T--){
cin>>l>>r>>K;
cout<<solve(r)-solve(l-1)<<"\n";
}
}