COCI HASH —— 扩展欧几里得

本文主要是介绍COCI HASH —— 扩展欧几里得，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

应该能进

题意：

定义哈希如下：

现在问你长度为n的字符串中，有多少哈希值$\%2^m$是k

题解：

那么这道题就是个水题，
我一眼就看出来是折半暴力，$26^5$只有1e7种情况，然后从前往后dfs一下，之后再从后往前，因为它有点特殊，不能像普通哈希一样乘，可以推出来：
$x\ast 33$^$y=k$
$=>x=k$^$y\ast inv[x]$
然后inv[33]用exgcd求。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=6e7+5;
int num[N],lim,inv,y;
ll mx;
void dfs(int x,ll v){if(x>lim){num[v]++;return ;}for(ll i=1;i<=26;i++)dfs(x+1,((v*33)^i)&mx);
}
ll ans;
void dfs2(int x,ll v){if(x>lim){ans+=num[v];return ;}for(ll i=1;i<=26;i++)dfs2(x+1,((v^i)*(ll)inv)&mx);
}
void Exgcd(int a,int b,int &x,int &y)
{if (b==0){x=1;y=0;}else{Exgcd(b,a%b,y,x);y=y-a/b*x;}
}
int main()
{int n,k,m;scanf("%d%d%d",&n,&k,&m);mx=(1ll<<m)-1;lim=n/2;dfs(1,0);Exgcd(33,mx+1,inv,y);if(inv<0)inv+=mx+1;lim=n-lim;dfs2(1,k);printf("%lld\n",ans);return 0;
}

这篇关于COCI HASH —— 扩展欧几里得的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---