AtCoder Regular Contest 135

D - Add to Square

考虑寻找不变式。

发现\(r_i=\sum_{i,j}(-1)^{ij}A_{ij}\)与\(c_j=\sum_{i,j}(-1)^{ij}A_{ij}\)是不变的。充分性可以贪心消元构造。

于是把每个数乘上\((-1)^{ij}\)以后，就变成每行/列和不变。

答案就是行/列的绝对值的和中更大的那个。

E - Sequence of Multiples

不妨设\(B_i=A_i/i\). 有递归式\(B_{i+1}=\lfloor \dfrac {iB_{i}}{i+1}\rfloor+1\). 至此通过枚举不同的\(B\)可以做到\(O(\sqrt N)\). 发现可以继续差分， 令\(C_i=B_i-B_{i+1}\)， 枚举\(C_i\)可以做到\(O(\sqrt[3] N)\).

F - Delete 1, 4, 7, ...

考虑通过\(f(x)=\lfloor1.5x\rfloor+1\)来表示保留的数原来的位置.

这样就可以用\(f^{(k)}(x)\)通过复合计算出原来留下了哪些数.

考虑当\(k\)较大时, 最终剩下的数较少, 可以直接暴力.

当\(k\)较小时, 需要考虑研究\(f\)的性质: \(f^{(k)}(x+2^k)=f^{(k)}(x)+3^k\).

然而\(O(k2^k)\)的做法不能通过..., 发现可以重复利用这个性质: \(f^{a+b}(x+2^b)=f^a(f^b(x)+3^b)\)

内层是一堆形如\(a, a + c, a + 2c \dots\)的数的点值. 倍增即可.