「THUPC2018」赛艇 / Citing

https://loj.ac/problem/6388

矩形匹配,小地图经过位置为1,和大地图匹配不能同时存在一个1的位置,就可以是一个当前位置

1.bitset压位,。。。。O(n^2m^2/64)可过。。

2.NTT字符串匹配

把n*m的大地图拆成长条,小地图放到n*m的左上角,也拆成长条,

两个一维数组匹配,小地图翻转,NTT

统计答案的时候,如果不会出现距离边界的宽度小于小地图宽度的时候,再考虑是否是0

「THUPC2018」赛艇 / Citing

为了避免红色的越界情况

上一篇:CS Academy Round 75 Permutations NTT


下一篇:Codeforces 438E The Child and Binary Tree [DP,生成函数,NTT]