题解 P5629 【【AFOI-19】区间与除法】

这题我们可以想到将每个数字变成 \(d\) 进制的数，消灭数可以看成是 \(d\) 进制下原数是这个数 \(d\) 进制下的一段前缀。

于是可以使用 \(Trie\) 来实现这个过程，于是可以先将这 \(m\) 个原数 insert，然后再去查询。

一个数有多个前缀，我们可以选择其中最短的一个，因为这样是最优秀的，可以理解为越短的串延伸出来的串就越多，而越长的串则通用性就越差。

于是我们就可以求出是每个数会选择哪个原数进行消灭，我们可以将状态存在一个 long long 里面，需要做到的就是区间或。

无修改，只有区间或，可以想到使用倍增（ST表）来求，因为或有着跟 \(\min\) 和 \(\max\) 一样好的性质。

code（目前的最优解）:

#include
#define fi first
#define se second
#define LL long long
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define DF(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(b,a) cerr<<"D:";F(i,1,b-1)cerr<<"   ";cerr<<" "<<#a<<" => "<<(a)<<"  <="<<__LINE__<<"L"<>1]+1;
	F(i,1,n)a[i]=read();
	F(i,1,m)b[i]=read();
	sort(b+1,b+m+1);
	F(i,1,m)
		insert(b[i],i);
	F(i,1,n){
		int c=query(a[i]);
		if(~c)f[0][i]=(1ll<