xjoi noip模拟赛 50

T1:

首先观察到题目有一个奇妙的性质(当然我是不会的)

他的矩形的边长都是奇数

所以相邻的矩形的(x,y) 的奇偶性肯定不同

于是我们就可以把整个矩形转换成2*2的simple的方块染色

于是就可以在O(1) 的时间内解决这个问题

T2:

弃疗了 还没有补

T3:

F等于f的前缀和

f = g * h * 1

* 为狄利克雷卷积

f = g * 1 * h

我们观察g * 1

我们设n = \sum_{i=1}^{n}(pi^{ai})

对于每一个pi 我们都有如下的展开式

\sum_{i=0}^{ai}(-1)^{i}

于是g(x)就是判断x是不是完全平方数

我们对F分块求解即可

复杂度


O(\sqrt[3]{n})


发表评论

电子邮件地址不会被公开。 必填项已用*标注