当前位置：首页 > news >正文

打卡信奥刷题（3064）用C++实现信奥题 P6871 [COCI 2013/2014 #6] HASH

news 2026/8/8 5:04:11

P6871 [COCI 2013/2014 #6] HASH

题目背景

Mirko 正在研究一个哈希函数。

题目描述

此哈希函数如此定义：

f ( N U L L ) = 0 f(\rm{NULL})=0f(NULL)=0
f ( a i + s i ) = ( ( f ( s i ) × 33 ) xor ⁡ ord ⁡ ( a i ) ) m o d M O D f(a_i+s_i)=((f(s_i)\times33)\operatorname{xor}\ \operatorname{ord}(a_i))\bmod MODf(ai+si)=((f(si)×33)xorord(ai))modMOD

其中a i a_iai代表一个字符，s i s_isi代表一个字符串，均由小写字母组成。

xor ⁡ \operatorname{xor}xor代表按位异或算符。
ord(letter) ⁡ \operatorname{ord(letter)}ord(letter)代表字母中字母的序数（如：ord(a)=1 ⁡ \operatorname{ord(a)=1}ord(a)=1，ord(z)=26 ⁡ \operatorname{ord(z)= 26}ord(z)=26）。

M O D MODMOD是2 m 2^m2m形式的整数。

当m = 10 m=10m=10时，哈希函数的一些值如下：

f ( a ) = 1 f(\texttt{a})=1f(a)=1
f ( aa ) = 32 f(\texttt{aa})=32f(aa)=32
f ( kit ) = 438 f(\texttt{kit})=438f(kit)=438

请问有多少个单词的哈希值为k kk且长度为n nn？

输入格式

输入一行，包含三个整数n nn，k kk和m mm。

输出格式

输出一行，哈希值为k kk且长度为n nn的单词个数。

输入输出样例 #1

输入 #1

1 0 10

输出 #1

输入输出样例 #2

输入 #2

1 2 10

输出 #2

输入输出样例 #3

输入 #3

3 16 10

输出 #3

说明/提示

【样例解释】

样例 1 解释

字母表中的所有字符的ord \text{ord}ord值均不为0 00。

样例 2 解释

单词b。

样例 3 解释

词语为dxl，hph，lxd和xpx。

【数据规模与约定】

1 ≤ n ≤ 10 1\le n\le 101≤n≤10，0 ≤ k < 2 m 0\le k<2^m0≤k<2m，6 ≤ m ≤ 25 6\le m\le 256≤m≤25。

【说明】

题目译自 COCI2013-2014 CONTEST #6T5 HASH。

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,K,m,inv,cnt[1<<25];longlongans;voiddfs1(intdep,intv){if(!dep){++cnt[v];return;}for(inti=1;i<=26;++i)dfs1(dep-1,((v*33)^i)%m);}voiddfs2(intdep,intv){if(!dep){ans+=cnt[v];return;}for(inti=1;i<=26;++i)dfs2(dep-1,1ll*(v^i)*inv%m);}intmain(){scanf("%d%d%d",&n,&K,&m);m=1<<m;for(inti=1;i<m;++i)if(i*33%m==1)inv=i;dfs1(n/2,0);dfs2((n+1)/2,K);printf("%lld",ans);}