[CF1270I]Xor on Figures

这个题比较神仙,我做了三天左右的时间,说明我太菜了。
设$n=2^k$
首先可以找规律发现,每个位置需要异或上的值是唯一的,那么答案就是需要异或上大于0的数的位置个数。
这个其实很好证,我们可以把每一位拆开来,然后相当于解一个异或的方程(也就是模2意义下的方程),我们设这个转移的矩阵为B。
我们只需要证明B是满秩的即可。如果B不满秩,那么一定能在高斯消元的时候消出一列0,然而每一列的1的个数一定是奇数,这不可能。所以B是满秩的。
然后我又找了找规律,发现了一个性质:$B^n=I$(B的n次方是单位矩阵)。
??!
我一脸懵逼,那就先假装这个是对的吧,那么$B^{-1}=B^{n-1}$,我们要对于每一位求答案,设第i位的矩阵为$A_i$,那么我们要求$AB^{-1}=AB^{n-1}$,我们发现A去乘的时候相当于是一个二维循环卷积,我们可以先用快速幂+FFT预处理$B^{n-1}$,然后对于每一位求答案,再合起来。
时间复杂度$O(n^2\lg n(\lg n+\lg x))$
随手写了发代码:

然后TLE了。。。
我不死心,想卡卡常,发现用分治做多项式乘法可以直接用位运算,不需要每一位拆开来做,然后又写了一个$O((n^2)^{\lg 3})$的分治乘法,的确快了不少,但是它还是TLE了。

然后我开始自闭了。然后我突然意识到异或只需要考虑操作的奇偶性,不需要知道具体操作了几次,然后还有一个性质叫做:$\binom{n}{m} \% 2=\lbrack n=m \oplus (n-m) \rbrack $(\oplus表示异或)
我突然意识到为什么$B^n=I$了!因为n是2的幂次,考虑所有n次操作每种出现了几次,可以发现一种操作的贡献要是奇数必须是出现0次或者n次,然而任意一种操作执行n次都会回到原点。
那么对于$AB^{n-1}$,我们可以将n-1每一位拆开,一位必须由一种操作全部包下,由于t比较小,所以直接暴力即可。
时间复杂度$O(tn^2k)$或者用FFT$O(n^2k\lg n)$。
然后AC了,跑得飞快,代码超短。

Tagged with:

发表评论