如何做网站海报,大同格泰网站建设,深圳专门做网站的公司,直接做海报的网站有点难#x1f605;
真的是 A B C ABC ABC的难度吗#x1f605;
非常精妙的哈希题目。
定义矩阵乘法#xff1a; c i , j ⊕ ( a i , k b k , j ) c_{i,j}\oplus (a_{i,k}\ b_{k,j}) ci,j⊕(ai,kbk,j)
之所以可以矩阵乘法是因为满足 ( a ⊕ b )…有点难
真的是 A B C ABC ABC的难度吗
非常精妙的哈希题目。
定义矩阵乘法 c i , j ⊕ ( a i , k b k , j ) c_{i,j}\oplus (a_{i,k}\ b_{k,j}) ci,j⊕(ai,kbk,j)
之所以可以矩阵乘法是因为满足 ( a ⊕ b ) c ( a c ) ⊕ ( b c ) (a\oplus b)\ c(a\ c)\oplus (b\ c) (a⊕b)c(ac)⊕(bc)
其实非常好验证就把两个运算符按顺序写下来然后把括号拆开看等式两边是否恒等即可。
定义对于序列 { a i } \{a_i\} {ai}的哈希规则为将每个 a k a_k ak与上 k − 1 k-1 k−1个 p p p后的结果全部异或起来
因为 ( a ⊕ b ) p ( a p ) ⊕ ( b p ) (a\oplus b)\p(a\ p)\oplus (b\ p) (a⊕b)p(ap)⊕(bp)所以如果 c i a i ⊕ b i c_ia_i\oplus b_i ciai⊕bi那么 { c i } \{c_i\} {ci}的哈希值就是把 { a i } \{a_i\} {ai}和 { b i } \{b_i\} {bi}对应的哈希值异或起来
但是发现与上的 p p p都是相同的所以这个方案冲突的概率很大
仔细观察正解的代码发现他是把 p p p设计成了一个 M × M M\times M M×M的 01 01 01矩阵 其中 M M M表示二进制位数也就是 64 64 64 a i a_i ai看成一个长度为 M M M的 01 01 01向量 这个向量的第 i i i位就是 a i a_i ai在二进制下的第 i i i位
不妨形式化的写一下首先我们随机一个矩阵 p p p哈希值就是 ⊕ i 1 n v i p i − 1 \oplus_{i1}^nv_ip^{i-1} ⊕i1nvipi−1。发现 c i a i ⊕ b i c_{i}a_{i}\oplus b_{i} ciai⊕bi那不就是把两个向量做按位异或吗。
直接倍增的复杂度是 O ( n M 3 log n ) O(nM^3\log n) O(nM3logn)考虑优化。
注意到是 01 01 01矩阵所以可以把同一行压成一个 64 64 64位整数这样转移优化到了 O ( M 2 ) O(M^2) O(M2)。
最终复杂度 O ( n M 2 log n ) O(nM^2\log n) O(nM2logn)。瓶颈在于倍增预处理不知道可不可以做的更好。
#includebits/stdc.h
#define ll long long
#define fi first
#define ull unsigned long long
using namespace std;
const int N5e55;
const int M64;
mt19937_64 t(time(0));
struct Matrix{ull c[M];Matrix(){memset(c,0,sizeof c);}Matrix operator *(const Matrix a)const{Matrix r;for(int i0;iM;i){for(int j0;jM;j){if(c[i]j1){r.c[i]^a.c[j];}}}return r;}
}pw[20];
int n,m;
ll a[N];
ull st[N][20];
ull get(ull x,Matrix y){ull res(0);for(int i0;iM;i){if(xi1)res^y.c[i];}return res;
}
void write(ull x){if(x10){cout(char)(0x);return;}write(x/10),cout(char)(0x%10);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm;srand(time(0));for(int i1;in;i)cina[i],st[i][0]a[i];for(int i0;iM;i){pw[0].c[i]t();}for(int i1;i20;i)pw[i]pw[i-1]*pw[i-1];for(int j1;j20;j){for(int i1;in-(1j)1;i){st[i][j]st[i][j-1]^get(st[i(1j-1)][j-1],pw[j-1]);}}for(int i1;im;i){int b,c,d,e,f,g;cinbcdefg;for(int j19;j0;j--){if(b(1j)-1cf(1j)-1g(st[b][j]^st[d][j])st[f][j]){b(1j),d(1j),f(1j);}}if(bc){if(fg)coutNo\n;else coutYes\n;}else{if(fg)coutNo\n;else if((a[b]^a[d])a[f])coutYes\n;else coutNo\n;}}
}
