- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
异或哈希是个很神奇的算法,利用了异或操作的特殊性和哈希降低冲突的原理,可以用于快速找到一个组合是否出现、序列中的数是否出现了 \(k\) 次 。
算法如其名,异或+哈希.
想起某首歌叫PPAP?
I have a \(\oplus\),I have an \(hash\). (Uhh~) \(\oplus hash\) .
😅 。
最基本的,也很重要的 。
考虑到异或运算满足交换律,即\(a \oplus b=b\oplus a\) 。
因此组合的不同排列的异或值相等 。
这样我们便可以忽略顺序,直接统计组合出现次数.
由于二进制位数有限,会存在一些情况使得异或并不正确,如:\(1\oplus 2=5\oplus 6\),\(1\oplus 2\oplus 3 = 4\oplus 8\oplus 12\) 。
因此需要将原始数据哈希为较大的数降低冲突概率 。
直接来看道例题.
here 。
不会有人看不懂英文还不会拿软件翻译吧 虽然翻译软件翻译的跟构式一样 。
直接沿用异或哈希的思路,不难写出 \(O(n^2)\) 的代码 。
int n,m;
mt19937_64 rnd(time(0));
unsigned long long code[N],chk[N],Xor[N],a[N];
signed main(){
n=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
}
for(int i=1;i<=n;i++){
code[i]=rnd();
chk[i]=chk[i-1]^code[i];
}
for(int i=1;i<=n;i++){
Xor[i]=Xor[i-1]^code[a[i]];
}
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if((Xor[i-1]^Xor[j])==chk[j-i+1]){
++cnt;
}
}
}
printf("%lld",cnt);
return Elaina;
}
兴高采烈地交上去...乂~T了.
一看数据范围:\(3*10^5\) 。
好家伙 \(O(n^2)\) 肯定 水 过不去了.
进一步考虑到:
分别向右/左做两次扩展:
设 \(pos\) 记录上一个 \(1\) 的位置,当前扩展到 \(x\) 。
当 \(x=1\) 时,就更新指针 \(pos\),并重置 \(mx\) 。
否则往回捯饬 \(mx=max(mx,x)\) 个数,异或哈希判断是否合法即可.
int n,m;
int max(int a,int b){
return a>b?a:b;
}
mt19937_64 rnd(time(0));
unsigned long long code[N],chk[N],Xor[N],a[N];
signed main(){
n=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
}
for(int i=1;i<=n;i++){
code[i]=rnd();
chk[i]=chk[i-1]^code[i];
}
for(int i=1;i<=n;i++){
Xor[i]=Xor[i-1]^code[a[i]];
}
int cnt=0,pos=-1,cnt1=0,mx=0;
for(int i=1;i<=n;i++){
if(a[i]==1){
pos=i,++cnt1,mx=1;
}else if(pos!=-1){
mx=max(mx,a[i]);
if(i-mx+1<=pos)
if((Xor[i]^Xor[i-mx])==chk[mx])
++cnt;
}
}
pos=-1;
for(int i=n;i>=1;i--){
if(a[i]==1){
pos=i,++cnt1,mx=1;
}else if(pos!=-1){
mx=max(mx,a[i]);
if(i+mx>=pos)
if((Xor[i+mx-1]^Xor[i-1])==chk[mx])
++cnt;
}
}
printf("%lld",cnt+cnt1/2);
return Elaina;
}
实际上反过来的时候可以直接reverse一下数组,然后再跑一遍,就不用复制粘贴打两遍了。。.
然后就 AC 了喵~ 。
二进制的异或的本质是对每一位进行不进位的加法,也就是每一位相加对2取模,即:
假设有一种运算 \(③\),使得 \(a\ ③\ a\ ③\ a=0\),即 。
其实也就是 \(3\) 进制的运算 。
扩展到 \(k\) 进制即可解决是否出现 \(k\) 次的问题 。
ull xork(ull a,ull b,int k){
vector<int> vec;
while(a||b){
vec.push_back((a+b)%k);
a/=k;
b/=k;
}
ull res=0;
ull p=1;
for(auto x:vec){
res+=p*x;
p*=k;
}
return res;
}
ull xork(ull x,ull y,int k){
int sum=0,p=1;
// if(y%2==0) swap(x,y);
while(x||y){
sum+=(x%k+y%k)%k*p;
p*=k;
x/=k;
y/=k;
}
return sum;
}
我们还是来看道例题 。
here 。
洛谷 。
其实上一道题也可以在洛谷找到对应的翻译版本 (逃 。
首先我们知道一个思想,证明充要条件就要证明它既充分又必要;同样,要证明一个数等于某个值,必须让它既小于等于又大于等于这个值。 迁移到本题,我们让所有数的出现个数 \(cnt = 3\) ,便是要去满足 \(cnt \geq 3 \land cnt \leq 3\) 这俩约束 。
第一个约束随便糊一个异或哈希即可.
关键在于第二个约束.
我们考虑使用类似于双指针的算法:
考虑对于一个满足约束二的 \([l, r]\) 区间,右指针每次往右移动一次,都可能会破坏原本“满足约束二”的性质。那么为了让其重新满足,我们需要让左指针一直向右移动,即:从左到右删去数字使得区间再次满足约束二.
让新加入的右指针的值 \(a_r\) 出现的次数小于等于三即可;因为这样删除必然不会导致“因为其他数字出现次数减少而导致不能满足约束二”这种情况,理由显然.
令 \(pre_r\) 为 \([1, r]\) 的前缀异或和.
当删除完毕之后,我们统计满足 \(pre_r = pre_{pos}\) 且 \(pos \in [l, r]\) 的 \(pos\) 数量,这一点可以使用 map 或者哈希表完成.
那么这道题就完成了,复杂度 \(\mathcal{O}(N \log_2 N)\) 或者纯线性.
然后关于...算了,自己看吧.
discuss 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
#define rd read()
#define mkp make_pair
#define psb push_back
#define Elaina 0
inline ll read(){
ll f=1,x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f=(ch=='-'?-1:1);
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return f*x;
}
const int mod=1e9+7;
const int N=1e6+100;
const int inf=0x7fffffff;
int n,k;
mt19937_64 rnd(time(0));
ull code[N],pre[N],a[N],num[N];
map<ull,ull> mp;
ull xork(ull x,ull y,int k){
ull sum=0,p=1;
while(x||y){
sum+=(x%k+y%k)%k*p;
p*=k;
x/=k;
y/=k;
}
return sum;
}
signed main(){
srand(time(0));
n=rd,k=3;
for(int i=1;i<=n;i++){
a[i]=rd;
}
for(int i=1;i<=N;i++){
code[i]=rnd()%(1ll<<63);
}
for(int i=1;i<=n;i++){
pre[i]=xork(pre[i-1],code[a[i]],k);
}
int cnt=0;
mp[0]=1;
for(int l=0,r=1;r<=n;++r){
++num[a[r]];
while(num[a[r]]>3){
--num[a[l]];
if(l>0) --mp[pre[l-1]];
++l;
}
cnt+=mp[pre[r]];
++mp[pre[r]];
}
printf("%lld",cnt);
return Elaina;
}
判断一个序列的乘积是否是 \(x^2\) ( $ x$ 为某个整数) 。
这个就比较好说了,根据唯一分解定理 。
其中,\(\alpha_1 \leq \alpha_2 \leq \alpha_3 \leq \dots \leq \alpha_k\)皆素数.
则 。
那么当这个序列质因子出现的次数都是偶数次即可.
题目 | 类型 |
---|---|
Prefix Equality AtCoder - abc250_e | 组合问题 |
The Number of Subpermutations CodeForces - 1175F | 组合问题 |
The Untended Antiquity CodeForces - 869E | 组合问题 |
由乃与大母神原型和偶像崇拜 洛谷 - P3792 | 组合问题 |
Number Game on a Tree HackerRank | 出现次数问题 |
Quadratic Set CodeForces - 1622F | \(x^2\)问题 |
蒂蒂~❤ 嘿嘿嘿 我的蒂蒂❤ 。
最后此篇关于关于异或哈希的文章就讲到这里了,如果你想了解更多关于关于异或哈希的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我正在尝试 grep conf 文件中所有不以 开头的有效行 哈希(或) 任意数量的空格(0 个或多个)和一个散列 下面的正则表达式似乎不起作用。 grep ^[^[[:blank:]]*#] /op
我正在使用哈希通过 URL 发送 protected 电子邮件以激活帐户 Hash::make($data["email"]); 但是哈希结果是 %242y%2410%24xaiB/eO6knk8sL
我是 Perl 的新手,正在尝试从文本文件创建散列。我有一个代码外部的文本文件,旨在供其他人编辑。前提是他们应该熟悉 Perl 并且知道在哪里编辑。文本文件本质上包含几个散列的散列,具有正确的语法、缩
我一直在阅读 perl 文档,但我不太了解哈希。我正在尝试查找哈希键是否存在,如果存在,则比较其值。让我感到困惑的是,我的搜索结果表明您可以通过 if (exists $files{$key}) 找到
我遇到了数字对映射到其他数字对的问题。例如,(1,2)->(12,97)。有些对可能映射到多个其他对,所以我真正需要的是将一对映射到列表列表的能力,例如 (1,2)->((12,97),(4,1))。
我见过的所有 Mustache 文档和示例都展示了如何使用散列来填充模板。我有兴趣去另一个方向。 EG,如果我有这个: Hello {{name}} mustache 能否生成这个(伪代码): tag
我正在尝试使用此公式创建密码摘要以获取以下变量,但我的代码不匹配。不确定我做错了什么,但当我需要帮助时我会承认。希望有人在那里可以提供帮助。 文档中的公式:Base64(SHA1(NONCE + TI
我希望遍历我传递给定路径的这些数据结构(基本上是目录结构)。 目标是列出根/基本路径,然后列出所有子 path s 如果它们存在并且对于每个子 path存在,列出 file从那个子路径。 我知道这可能
我希望有一个包含对子函数的引用的散列,我可以在其中根据用户定义的变量调用这些函数,我将尝试给出我正在尝试做的事情的简化示例。 my %colors = ( vim => setup_vim()
我注意到,在使用 vim 将它们复制粘贴到文件中后尝试生成一些散列时,散列不是它应该的样子。打开和写出文件时相同。与 nano 的行为相同,所以一定有我遗漏的地方。 $ echo -n "foo"
数组和散列作为状态变量存在限制。从 Perl 5.10 开始,我们无法在列表上下文中初始化它们: 所以 state @array = qw(a b c); #Error! 为什么会这样?为什么这是不允
在端口 80 上使用 varnish 5.1 的多网站设置中,我不想缓存所有域。 这在 vcl_recv 中很容易完成。 if ( req.http.Host == "cache.this.domai
基本上,缓存破坏文件上的哈希不会更新。 class S3PipelineStorage(PipelineMixin, CachedFilesMixin, S3BotoStorage): pa
eclipse dart插件在“变量” View 中显示如下内容: 在“值”列中可见的“id”是什么意思? “id”是唯一的吗?在调试期间,如何确定两个实例是否相同?我是否需要在所有类中重写toStr
如何将Powershell中的命令行参数读入数组?就像是 myprogram -file file1 -file file2 -file file3 然后我有一个数组 [file1,file2,fil
我正尝试在 coldfusion 中为我们的安全支付网关创建哈希密码以接受交易。 很遗憾,支付网关拒绝接受我生成的哈希值。 表单发送交易的所有元素,并发送基于五个不同字段生成的哈希值。 在 PHP 中
例如,我有一个包含 5 个元素的哈希: my_hash = {a: 'qwe', b: 'zcx', c: 'dss', d: 'ccc', e: 'www' } 我的目标是每次循环哈希时都返回,但没
我在这里看到了令人作呕的类似问题,但没有一个能具体回答我自己的问题。 我正在尝试以编程方式创建哈希的哈希。我的问题代码如下: my %this_hash = (); if ($user_hash{$u
我正尝试在 coldfusion 中为我们的安全支付网关创建哈希密码以接受交易。 很遗憾,支付网关拒绝接受我生成的哈希值。 表单发送交易的所有元素,并发送基于五个不同字段生成的哈希值。 在 PHP 中
这个问题已经有答案了: Java - how to convert letters in a string to a number? (9 个回答) 已关闭 7 年前。 我需要一种简短的方法将字符串转
我是一名优秀的程序员,十分优秀!