P10474 [ICPC 2011 Beijing R] Matrix 矩阵哈希题目描述给定一个MMM行NNN列的010101矩阵以及QQQ个AAA行BBB列的010101矩阵你需要求出这QQQ个矩阵哪些在原矩阵中出现过。所谓010101矩阵就是矩阵中所有元素不是000就是111。输入格式输入文件的第一行为M,N,A,BM,N,A,BM,N,A,B参见题目描述。接下来MMM行每行NNN个字符非000即111描述原矩阵。接下来一行为你要处理的询问数QQQ。接下来QQQ个矩阵一共Q×AQ\times AQ×A行每行BBB个字符描述QQQ个010101矩阵。输出格式你需要输出QQQ行每行为000或者111表示这个矩阵是否出现过000表示没有出现过111表示出现过。输入输出样例 #1输入 #13 3 2 2 111 000 111 3 11 00 11 11 00 11输出 #11 0 1说明/提示对于100%100\%100%的实际测试数据1≤M,N≤10001\leq M,N \leq 10001≤M,N≤1000Q1000Q 1000Q1000。对于40%40\%40%的数据A1A 1A1。对于80%80\%80%的数据A≤10A \leq 10A≤10。对于100%100\%100%的数据A≤100A \leq 100A≤100B≤500B \leq 500B≤500。C实现#includebits/stdc.husingnamespacestd;typedefunsignedlonglongULL;constintP110003,P211117,mod1000007,N1005;intn,m,T,A,B;chars[N];ULL p1[N],p2[N],h[N][N],num[N*N];intcnt,last[mod],nxt[N*N];intfind(ULL x){intidx%mod;for(intilast[id];i;inxt[i])if(num[i]x)returni;return0;}intinsert(ULL x){intidx%mod;for(intilast[id];i;inxt[i])if(num[i]x)returni;num[cnt]x;nxt[cnt]last[id];last[id]cnt;returncnt;}intmain(){cinnmAB;p1[0]p2[0]1;for(inti1;in;i)p1[i]p1[i-1]*P1;for(inti1;im;i)p2[i]p2[i-1]*P2;for(inti1;in;i){ULL c0;scanf(%s,s1);for(intj1;jm;j){cc*P2s[j];h[i][j]h[i-1][j]*P1c;}}for(intiA;in;i)for(intjB;jm;j)insert(h[i][j]-h[i-A][j]*p1[A]-h[i][j-B]*p2[B]h[i-A][j-B]*p1[A]*p2[B]);cinT;while(T--){ULL res0;for(inti1;iA;i){scanf(%s,s1);for(intj1;jB;j)ress[j]*p1[A-i]*p2[B-j];}if(find(res))cout1endl;elsecout0endl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容