「codevs1998」终极武器 - 数位trie树

题目大意

经过一番周折，精英队伍的队员们终于来到了关押applepi的牢狱面前。心中神一般的领袖applepi就在眼前，队员们都不由自主地跪烂膝盖……不过令他们沮丧的是，牢狱的大锁没有钥匙孔，黑魔法师Vani根本就没有指望它再被打开。幸好队员们携带了新研制的终极武器——k型氙激光器（Xenon Laser - k，代号XLk），可以用来破拆这把锁。不过作为一道终极武器，它的启用规则异常严格。
Xenon Laser - k上共有$N$个波段能够发射激光，每个波段可以用一个闭区间$[a_i,b_i]$来表示，其中$a_i,b_i$为正整数，$b_i-1<a_i<=b_i$。对于两个数字$p$和$q$，如果对于这$N$个波段内的任意一个整数$num$，把它在十进制表示下的后$K$位中某一位上$p$的换成$q$（或者$q$换成$p$），都满足得到的整数仍然在这$N$个波段内，那么称在该激光器中，数字$p$和$q$是等价的。我们称两两之间$k$等价的数字组成一个等价类。
激光器附带了$9$个发射匣，代表$1\rightarrow 9$这$9$个数字。只有把同一个等价类的数字对应的发射匣安置在一排上，Xenon Laser - k才能够启动。给定$N$个波段，现在就请你求出$1\rightarrow 9$这$9$个数字分成了哪些等价类，并且每行输出一个等价类。
本题描述比较抽象，请参考样例解释。

---

题目分析

本题可以用一个非常麻烦的模拟解决。
然而我们（我、achen、KEKE_046）都不会写模拟，因此我们选择使用$trie$树。

根据题目给出的上下界将各个位拆分建成$trie$树，因为建立$trie$树的过程类似数位动规，因此称为数位$trie$树。

判断两个数字是否是在同一个等价类中的方法是：它们的后$K$位构成的树完全相同。
我们可以在$trie$树上递归到后$K$位然后判断其子树是否完全相同，具体可以使用$Hash$实现。

最后输出答案用并查集维护一下即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const LL mod=1e9+7;
const int maxn=5000005;
int n,k;
struct Trie {
	int root,cnt;
	int child[maxn][10];
	int f[maxn],tmp1[21],tmp2[21];
	LL Hash[maxn];
	Trie() {
		cnt=0;
		root=++cnt;
	}
	int Get_Hash(int depth) {
		if(!depth)return 0;
		if(f[depth])return f[depth];
		for(int i=0; i<=9; i++)f[depth]=((LL)f[depth]*131+i+Get_Hash(depth-1))%mod;
		return f[depth];
	}
	void build(int Now,bool Up,bool Down,int pos) {
		if(pos==0)return;
		if(!Up&&!Down) {
			Hash[Now]=Get_Hash(pos);
			return;
		}
		int up=Up?tmp2[pos]:9,down=Down?tmp1[pos]:0;
		for(int i=down; i<=up; i++) {
			if(!child[Now][i])child[Now][i]=++cnt;
			build(child[Now][i],Up&&i==up,Down&&i==down,pos-1);
		}
	}
	void insert(LL Left,LL Right) {
		for(int i=1; i<=19; i++)tmp1[i]=Left%10,Left/=10;
		for(int i=1; i<=19; i++)tmp2[i]=Right%10,Right/=10;
		build(root,1,1,19);
	}
	void dfs(int Now) {
		for(int i=0; i<=9; i++) {
			int Next=child[Now][i];
			if(!Next)continue;
			dfs(Next);
			Hash[Now]=((LL)Hash[Now]*131+Hash[Next]+i)%mod;
		}
	}
	bool check(int Now,int x,int y,int pos) {
		if(pos<=k&&((!child[Now][x])^(!child[Now][y])))return false;
		if(pos<=k&&child[Now][x]&&child[Now][y]&&Hash[child[Now][x]]!=Hash[child[Now][y]])return false;
		for(int i=0; i<=9; i++)
			if(child[Now][i]&&!check(child[Now][i],x,y,pos-1))return false;
		return true;
	}
} trie;
vector<int>ans[10];
int father[15];
int Get_Father(int x) {
	if(father[x]==x)return x;
	return father[x]=Get_Father(father[x]);
}
int main() {
	n=Get_Int();
	k=Get_Int();
	for(int i=1; i<=n; i++) {
		LL x=Get_Int(),y=Get_Int();
		trie.insert(x,y);
	}
	trie.dfs(1);
	for(int i=1; i<=9; i++)father[i]=i;
	for(int i=1; i<=9; i++)
		for(int j=i+1; j<=9; j++)
			if(trie.check(1,i,j,19))father[Get_Father(j)]=Get_Father(i);
	for(int i=1; i<=9; i++)ans[Get_Father(i)].push_back(i);
	for(int i=1; i<=9; i++) {
		if(!ans[i].size())continue;
		for(int x:ans[i])printf("%d",x);
		putchar('\n');
	}
	return 0;
}