首页 > 其他分享 >异或哈希

异或哈希

时间:2024-04-23 09:02:26浏览次数:20  
标签:数组 int 最大值 long 异或 哈希 define

问题:https://codeforces.com/contest/1175/problem/F
关键点:随机化+异或
1.为何要异或:忽略顺序
将1~n随机的一一映射到long long值域内,形成新的映射数组b。再根据异或的特点,只需要判断:
b[1]⊕b[2]⊕…………⊕b[n]==b[a[l]]⊕b[a[l+1]]⊕……⊕b[a[r]]
2.为何要随机,因为若不随机,二进制位数有限,会存在一些情况使得异或并不正确.
例如:1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 6 ⊕ 7 = 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ⊕ 4 ⊕ 5
其实上述等式成立实质上就是等式两边每一个二进制位上的1的个数都相等。
那么当二进制位数变多了之后,发生错误的概率也会下降(但不会没有,只是可以近似看作没有)
问题二:如何找到所有合法子数组?
考虑以下这几个 合法子数组 一定满足的条件:
1.序列含有且仅含有一个1.
2.合法子数组的最大值就是它的长度
3.最大值要么出现在1的左边,要么出现在1的右边.
那么我们遍历序列每一个1的位置,先假设最大值出现在1的右边,那么循环遍历它右边的位置,同时统计区间最大值。然后对于每一个位置,我们假设它就是某个合法子数组的右端点。然后确定左端点。再O ( 1 ) O(1)O(1)hash判排列。然后再revese一下再跑一遍该算法即可。

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define x first 
#define y second

using namespace std;
const int N=5e5+10,mod=998244353;

typedef pair<int,int> PII; 

int n;
int bk[N] , a[N] , b[N] , p[N];

//异或哈希 
void slove(){
	int n; 
	cin>>n;
    srand(9904);
    //将n个数映射到一个ll范围下的桶中
    for (int i = 1 ; i <= n ; i++){
        bk[i] = ((long long)rand()<<30) + 1ll * (rand()<<16) + 1ll * rand();//可以 
        p[i] = p[i - 1] ^ bk[i];//p[i]表示1~i的异或和 
    }
    for (int i = 1 ; i <= n ; i++) cin>>a[i]; 
    int ans = 0;//
    for (int t = 0 ; t < 2 ; t++){//正着跑一遍,倒着跑一遍(正着跑是假定最大值在1的右边,倒着跑是假定最大值在1的左边)

        for (int i = 1 ; i <= n ; i++)
            b[i] = bk[a[i]] ^ b[i - 1]; 

        int now = -1 , mx = 0;//mx记录的是最大值,now表示当前的1的位置
        for (int i = 1 ; i <= n ; i++){
            if (a[i] == 1){
                ans += (t == 0);//特殊记录为1的情况 
                now = i;
                mx = 1;
                continue;
            }
            if (now == -1) continue;// 
            mx = max(mx , a[i]);
            if (mx < (i - now + 1)) continue;//如果mx小于区间长度的话 
            int x = now - (mx - (i - now + 1));//如果mx大于等于区间长度的话,找到左端点 
            if (x <= 0) continue;
            ans += ((b[i] ^ b[x - 1]) == p[mx]);//查看异或和是否相等 
        }
        reverse(a + 1 , a + 1 + n);
    }
    cout << ans << endl;
} 

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T=1;
//	cin>>T;
	while(T--) slove(); 
}	

标签:数组,int,最大值,long,异或,哈希,define
From: https://www.cnblogs.com/mendax-Z/p/18152024

相关文章

  • 最大异或对
    实在是看不懂了....下面这个代码是求最大异或对,的值至于那个异或区间....实在看不懂了...还是贴一下吧#include<iostream>#include<algorithm>usingnamespacestd;intconstN=100010,M=31*N;intn;inta[N];intson[M][2],idx;//M代表一个数字串二进制可以到多长vo......
  • 哈希
    哈希入门LeetCode1.两数之和注意添加顺序,先判断再添加...classSolution{publicint[]twoSum(int[]nums,inttarget){//{numsvalue:index}Map<Integer,Integer>map=newHashMap<>();List<Integer>res=newArrayList<>......
  • P9745 「KDOI-06-S」树上异或
    P9745「KDOI-06-S」树上异或位运算trick+树形dp看到题目中贡献的计算,可以想到乘法分配律,也就是一个连通块的乘积可以直接乘在当前所有方案的权值之和上。可以考虑特殊性质:链。那么树的问题就变成了序列问题。容易设\(f_i\)表示\(i\)以前的节点的所有断边方案权值和。转移......
  • MD5哈希长度延展攻击
    MD5哈希长度延展攻击原理已知原始消息(m)和其对应的哈希值(h)。选择额外数据(m’)。计算填充,使得填充后的消息长度满足长度模512等于448,并包含新消息的长度信息。构造新消息(m+\text{填充}+m’)。计算新消息的哈希值(h’)。代码importhas......
  • 哈希
    简介哈希是一种能把字符串(实际上数组也行,不过本文都会以字符串为例)映射成一个数的算法,哈希就是把一个字符串转成一个\(K\)进制数,但由于得到的数可能会非常大,所以其中会用到取模,因此哈希也有些玄学(建议CF有赛后hack的比赛不要使用哈希,或提高哈希的安全度)。普通哈希可以将......
  • C# 异或校验两种方法
    12publicbyteGetXor(byte[]data)3{4byteCheckCode=0;5intlen=data.Length;6for(inti=0;i<len;i++)7{8CheckCode^=data[i];9......
  • MD5哈希长度延展攻击(选做)
    任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行删除文件的命令(删除文件的命令为......
  • MD5哈希长度延展攻击(选做)
    MD5哈希长度延展攻击(选做)任务任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行......
  • MD5哈希长度延展攻击
    任务描述:在一个使用MD5哈希算法的系统中,管理员使用了一个密钥k和命令cmd的组合来生成每个命令的签名:hash(k||cmd)。你已经获得了一个允许查看文件的命令cmd=viewfile和对应的签名h,但你希望通过哈希长度延展攻击,生成一个新的签名,该签名能够让你执行删除文件的命令(删除文件的命令为......
  • MD5哈希长度延展攻击(选做)
    一、理解长度扩展攻击(lengthextensionattack),是指针对某些允许包含额外信息的加密散列函数的攻击手段。对于满足以下条件的散列函数,都可以作为攻击对象:①加密前将待加密的明文按一定规则填充到固定长度(例如512或1024比特)的倍数;②按照该固定长度,将明文分块加密,并用前一个......