NFLSPC #2 风 题解

2019-11-28 23:02:04 By wzy

我们先考虑另一个相似的问题:如果问的是每行第一个数的和的最大值该如何处理?

这是一个经典做法 考虑枚举平移次数模2^4*3^2*5^2*7的余数 然后要确定每行第一个数只需要知道平移次数模至多一种质数的幂的余数了 于是把数按对应的质数分组 每组是独立的 组内枚举即可 组之间的合并是直接加

回到这道题 这个做法问题出在了哪呢?

合并的时候需要fwt 导致要做很多很多次fwt 严重超时

我们注意到

1 外层枚举的次数不能太大

2 内层枚举的次数只要不比一次fwt慢太多都行

于是我们有了一个改进版的做法

我们先进行一些不影响答案的操作以便于叙述

1 如果n小于50 将n扩大为50 新的位置全部填0

2 我们对前25行依次做如下操作:

对第i行第j列的数x 我们将第2i行第j列和第2i行第i+j列的数异或x 然后把第i行第j列的数变成0

现在我们面对的是恰好50行数 前25行是0不用考虑

考虑第29 31 37 41 43 47行这六行数 发现这行数哪个在第一个不影响其他任何一行 所有我们最后单独考虑再合并即可

我们枚举平移次数模6的余数 然后把剩下的数字分成两组

第一组:27 28 30 32 33 35 36 40 42 44 45 48 49 50

第二组:26 34 38 39 46

注意到第一组的数因子都属于2 3 5 7 11而第二组的数在知道模6余数后只要再知道模某个唯一的质数的余数即可知道模它的余数

而且在知道平移次数模6的余数的情况下 第一二组数的异或和是独立的

对第一组数 我们枚举平移次数模2^5*3^3*5^2*7^2*11的余数(事实上只有2^4*3^2*5^2*7^2*11种) 就可以知道所有第一组数第一个数的异或和的所有可能值

对第二组数 为了减少fwt合并的次数 我们直接一起考虑 枚举平移次数模2*3*13*17*19*23的余数(事实上只有13*17*19*23种) 就可以知道所有第二组数第一个数的异或和的所有可能值

然后我们我们并第一组数和第二组数的所有可能值

我们把枚举的6种大情况的所有可能值再用fwt合并 然后和外面的第29 31 37 41 43 47行这六行数合并(可以fwt或者直接dp)

这道题大体已经做完了 但是还有几个注意点

1 fwt里每个值记录的是每个数作为异或和的方案数 不做处理肯定爆long long 怎么处理呢?

追求正确性的做法:每次fwt合并完都逆fwt 然后把所有非0数变成1 依然不改变每个数是否可能成为异或和 缺点是每次都要逆fwt 比较慢

追求效率的做法:考率模一个数 比如1000000007 这样不用每次逆fwt了 会快得多但是有概率出错(就是某个异或和出现次数是模数若干倍时)在模数是1000000000数量级时出错率在0.001左右

2 如果我们在枚举平移次数模2^5*3^3*5^2*7^2*11的余数的循环内部一一查看这14行第一个数是多少 将会很慢

考虑先枚举模2^5*3^3*5^2*7^2的余数 然后查看已经确定的12行第一个数是多少 然后再枚举模2^5*3^3*5^2*7^2*11的余数(只有11种情况) 再看第33和44行第一个数是多少 这样可以快很多

其实n到60也可以在1s内完成(大循环枚举模12的余数) 但是有点卡常 所有就只放了n=50

$by\ \text{skyline}$

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。