首页 > 其他 > 详细

「THUPC2018」赛艇 / Citing

时间:2019-03-02 12:25:49      阅读:151      评论:0      收藏:0      [点我收藏+]

https://loj.ac/problem/6388

矩形匹配,小地图经过位置为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感觉

「THUPC2018」赛艇 / Citing

原文:https://www.cnblogs.com/Miracevin/p/10460365.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!