矩形匹配,小地图经过位置为1,和大地图匹配不能同时存在一个1的位置,就可以是一个当前位置
1.bitset压位,。。。。O(n^2m^2/64)可过。。
2.NTT字符串匹配
把n*m的大地图拆成长条,小地图放到n*m的左上角,也拆成长条,
两个一维数组匹配,小地图翻转,NTT
统计答案的时候,如果不会出现距离边界的宽度小于小地图宽度的时候,再考虑是否是0
为了避免红色的越界情况
思路就是把矩阵变成一维数组,由于是匹配是mod 2 意义下的乘法,所以NTT
关于一般的NTT匹配字符的问题+通配符:
https://ebola-emperor.blog.luogu.org/solution-p4173
思路就是想方设法得到匹配函数,使得在能够匹配的时候恰好为0,不匹配的时候必须是正数
最小值为0,为0的位置就是匹配位置。
平方就大力拆开,交叉项可以卷积
有点hash感觉
原文:https://www.cnblogs.com/Miracevin/p/10460365.html