集宁建设局网站,网站手机模板的特点,wordpress文章图片缩放,高端网站建设哪里好传送门 题目条件两个子串\(S[l_1,r_1],S[l_2,r_2]\)完全相同等价于\(\forall i \in[0,r_1-l_11],S_{l1i}S_{l_2i}\),然后所有相同位置的都要选一种数字,把所有相同的放在一个集合,然后记集合个数为\(cn\)那么答案就是\(9*10^{cn-1}\),因为第一位不为0,然后就可以暴…传送门 题目条件两个子串\(S[l_1,r_1],S[l_2,r_2]\)完全相同等价于\(\forall i \in[0,r_1-l_11],S_{l1i}S_{l_2i}\),然后所有相同位置的都要选一种数字,把所有相同的放在一个集合,然后记集合个数为\(cn\)那么答案就是\(9*10^{cn-1}\),因为第一位不为0,然后就可以暴力并查集做到\(O(n^2)\)了 发现这样的连边是一个区间对应向另一个区间连边,可以考虑优化.因为连边要一一对应,所以可以ST表优化连边.就是每个点拆出\(log\)个点,代表以这个点为左端点的长度为\(2^k\)的区间,然后每次两个区间二进制拆分一下,在对应的点连边就好了个鬼.不过这样还是不对的,最后还要把这些连的边的作用发挥出来,就从上往下遍历ST表的每一层,某个点如果在当前层的根不是自己,那么就把自己的左儿子,右儿子分别向根的两个儿子连边,然后做下去 #includebits/stdc.h
#define LL long long
#define db long double
#define il inline
#define re registerusing namespace std;
const int N1e510,mod1e97;
il LL rd()
{LL x0,w1;char ch0;while(ch0||ch9) {if(ch-) w-1;chgetchar();}while(ch0ch9) {x(x3)(x1)(ch^48);chgetchar();}return x*w;
}
int n,m,lz,ff[N][17],l2[N];
int findf(int x,int i){return ff[x][i]x?x:ff[x][i]findf(ff[x][i],i);}
int fpow(int a,int b){int an1;while(b){if(b1) an1ll*an*a%mod;a1ll*a*a%mod,b1;}return an;}int main()
{nrd(),mrd();lzlog2(n);for(int j0;jlz;j) l2[1j]j;for(int j0;jlz;j)for(int i1;i(1j)-1n;i)ff[i][j]i;while(m--){int lrd(),rrd(),llrd(),rrrd();if(lll) continue;rrrr-ll1;while(rr){int xrr(-rr),yl2[x];ff[findf(l,y)][y]findf(ll,y);lx,llx;rr-x;}}for(int jlz;j;--j){for(int i1;i(1j)-1n;i)if(i!findf(i,j))ff[findf(i,j-1)][j-1]findf(findf(i,j),j-1),ff[findf(i(1(j-1)),j-1)][j-1]findf(findf(i,j)(1(j-1)),j-1);}int cn0;for(int i1;in;i) cnifindf(i,0);printf(%lld\n,9ll*fpow(10,cn-1)%mod);return 0;
} 转载于:https://www.cnblogs.com/smyjr/p/10537890.html
