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

P6871 [COCI 2013/2014 #6] HASH题目背景Mirko 正在研究一个哈希函数。题目描述此哈希函数如此定义f ( N U L L ) 0 f(\rm{NULL})0f(NULL)0f ( a i s i ) ( ( f ( s i ) × 33 ) xor ⁡ ord ⁡ ( a i ) ) m o d M O D f(a_is_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)1ord(z)26 ⁡ \operatorname{ord(z) 26}ord(z)26。M O D MODMOD是2 m 2^m2m形式的整数。当m 10 m10m10时哈希函数的一些值如下f ( a ) 1 f(\texttt{a})1f(a)1f ( aa ) 32 f(\texttt{aa})32f(aa)32f ( kit ) 438 f(\texttt{kit})438f(kit)438请问有多少个单词的哈希值为k kk且长度为n nn输入格式输入一行包含三个整数n nnk kk和m mm。输出格式输出一行哈希值为k kk且长度为n nn的单词个数。输入输出样例 #1输入 #11 0 10输出 #10输入输出样例 #2输入 #21 2 10输出 #21输入输出样例 #3输入 #33 16 10输出 #34说明/提示【样例解释】样例 1 解释字母表中的所有字符的ord \text{ord}ord值均不为0 00。样例 2 解释单词b。样例 3 解释词语为dxlhphlxd和xpx。【数据规模与约定】1 ≤ n ≤ 10 1\le n\le 101≤n≤100 ≤ k 2 m 0\le k2^m0≤k2m6 ≤ m ≤ 25 6\le m\le 256≤m≤25。【说明】题目译自 COCI2013-2014 CONTEST #6T5 HASH。C实现#includebits/stdc.husingnamespacestd;intn,K,m,inv,cnt[125];longlongans;voiddfs1(intdep,intv){if(!dep){cnt[v];return;}for(inti1;i26;i)dfs1(dep-1,((v*33)^i)%m);}voiddfs2(intdep,intv){if(!dep){anscnt[v];return;}for(inti1;i26;i)dfs2(dep-1,1ll*(v^i)*inv%m);}intmain(){scanf(%d%d%d,n,K,m);m1m;for(inti1;im;i)if(i*33%m1)invi;dfs1(n/2,0);dfs2((n1)/2,K);printf(%lld,ans);}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容