来广营网站建设,南昌易动力网站建设公司,WordPress Core 5.0,有孩子做的网站虽然平时做过但是考场上肯定还是不会#xff0c;不过没事干还是写一下吧 Myhill-Nerode\text{Myhill-Nerode}Myhill-Nerode 定理#xff1a;给定一个语言LLL#xff0c;定义在字符串上一个关系为#xff0c;若对于所有的zzz#xff0c;xzxzxz在LLL中当且仅当yzyzyz在LLL中…虽然平时做过但是考场上肯定还是不会不过没事干还是写一下吧
Myhill-Nerode\text{Myhill-Nerode}Myhill-Nerode 定理给定一个语言LLL定义在字符串上一个关系为若对于所有的zzzxzxzxz在LLL中当且仅当yzyzyz在LLL中则称x,yx,yx,y在同一个等价类中。因此它把所有有限字符串的集合划分成一个或多个等价类。
Myhill-Nerode\text{Myhill-Nerode}Myhill-Nerode 定理声称在LLL的最小自动机中状态的数目等价于在LLL中诱导出的等价类的数目。
容易发现语言LLL可以被有限状态机接受当且仅当等价类的数目是有限的。
Gym 102586J
考虑用等价类构造DFADFADFA还要为每一类找一个代表元。这里必须指出的是LLL中的字符串一定在同一个等价类中这个等价类也是接收点。
这里假定有限字符串集合长度不超过LLL然后暴搜求出每个字符串的等价类即可。
如何证明取L10L10L10的正确性思维小实验
假设存在一个DFADFADFA d(k)d(k)d(k)能正确识别长度不超过kkk的好串据此可以构造出一个NFANFANFA能正确识别长度不超过k2k2k2的好串其构造方法是在原DFADFADFA的基础上建立ϵ\epsilonϵ然后建一个子DFADFADFA表示操作的长度为333的段再用ϵ\epsilonϵ连回在原DFADFADFA中所对应的字符边即可再将其转化为DFADFADFA d(k2)d(k2)d(k2)最常用的方法是幂极构造并最小化。
如果d(k)d(k)d(k)等价于d(k2)d(k2)d(k2)我们就能得到d(k)d(k2)d(k4)⋯d(k)d(k2)d(k4)\cdotsd(k)d(k2)d(k4)⋯ 这也就是我们所要求的DFADFADFA。验证即可。
CF956F
考虑构造一个FAFAFA来识别不超过nnn位的f(m)≤kf(m)\le kf(m)≤k的数字串
FAFAFA的状态是背包容量字母表是0∼90\sim 90∼9原来状态是ccc读入一个数字ddd可以转移到cdcdcd和∣c−d∣|c-d|∣c−d∣显然这是一个NFANFANFA可以设置状态数为100100100然后大力幂集转移。
可以用长度为100100100的bitset\text{bitset}bitset实现幂集用一个哈希表记录某个bitset\text{bitset}bitset出现过没有。
理论复杂度O(2100)O(2^{100})O(2100)。这非常不科学。这种方法还是比较大胆的。
我完全没这个魄力好吧
#includebits/stdc.h
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N1e55;
int n,K,tot,to[N][10],c[100],len;
ll l,r,dp[N][20][10];
map__int128,intid;
__int128 has(bitset100b){__int128 x0;for(int i99;i0;i--){x*2;if(b[i])x;}return x;
}
int dfs(bitset100b){int x;if(id[has(b)])return id[has(b)];xid[has(b)]tot;for(int i0;i10;i){if(b._Find_first()i)dp[tot][0][i]1;}for(int i0;i10;i){bitset100b2(bi)|(bi);for(int j0;ji;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(x0)return dp[y][0][K];ll res0;for(int i0;ic[x];i){resdfs2(x-1,to[y][i],ic[x]);}return res;
}
ll solve(ll x){len0;while(x)c[len]x%10,x/10;return dfs2(len,1,1);
}
int main(){bitset100e;e[0]1;int T;cinT,dfs(e);for(int l0;l10;l){for(int i1;i18;i){for(int j1;jtot;j){for(int k0;k10;k){dp[j][i][l]dp[to[j][k]][i-1][l];}}} }while(T--){cinlrK;coutsolve(r)-solve(l-1)\n;}
}
