首页 > 代码库 > [COCI 2013/2014 ROUND 6] hash

[COCI 2013/2014 ROUND 6] hash

2024-08-10 09:30:48   217人阅读

分析：

　　很容易想到时间复杂度为O(26n)的暴力枚举算法，但由于n<=10，很明显会超时，这时会有一个比较常用的方法：折半枚举。

　　分别枚举前半段和后半段，把满足条件的结合起来就是答案。

　　对于f[i]=((f[i-1]*33) xor letter[i]) mod 2m

　　前半段很好做，直接带入公式，定义g[i]为hash值为i的个数，进行记录

　　后半段可以这样做：

　　在此题的背景下，因为m>=6，且1<=letter[i]<=26,所以 (a xor b) mod 2m=(a mod 2m) xor b

　　又因为xor的逆运算是他自己本身,所以已知k=((x*33) xor letter[i]) mod 2m要求x mod 2m，可以化为(x*33) mod 2m=k xor letter[i]

　　因为33肯定与2m互质，令a=33模2m的乘法逆元，那么x mod 2m=((k xor letter[i])*a) mod 2m

　　这样就可以倒着推了

小技巧：对2m取余就等于对2m-1进行位运算和操作

下面是代码：

 1 #include<cstdio> 2 #define maxn 1<<25 3 #define LL long long 4  5 int n,k,m,N,x,y,ni,M; 6 int f[maxn]; 7 int Mod; 8 LL ans=0; 9 10 void dfs(int a,int b)11 {12     if (a>N)13     {14         f[b]++;15         return;16     }17     for (int i=1;i<=26;i++)18         dfs(a+1,((b*33)^i)&Mod);19 }20 21 void Exgcd(int a,int b,int &x,int &y)22 {23     if (b==0)24     {25         x=1;y=0;26     }27     else28     {29         Exgcd(b,a%b,y,x);30         y=y-a/b*x;31     }32 }33 34 void back_dfs(int a,int b)35 {36     if (a>M)37     {38         ans+=f[b];39         return;40     }41     for (int i=1;i<=26;i++)42         back_dfs(a+1,((b^i)*ni)&Mod);43 }44 45 int main()46 {47     scanf("%d%d%d",&n,&k,&m);48     N=n>>1;49     Mod=(1<<m)-1;50     dfs(1,0);51     Exgcd(33,1<<m,x,y);52     ni=(x+(1<<m))&Mod;53     M=n-N;54     back_dfs(1,k);55     printf("%I64d\n",ans);56     return 0;57 }

 

[COCI 2013/2014 ROUND 6] hash


联系
我们