施工中

A. 简单计数

普通做法

考虑矩阵二项式：

则有：

降智严重的做法

构造矩阵 ，那么对于矩阵 ，有 就是答案

可以发现它是一个循环矩阵，因此可以只用第一行来表示，设 ，那么它在模 意义下的 次幂的 即为答案

进一步可以发现， 是相同的，因为它们的图论意义下是完全图上的本质相同点

于是可以只用 来表示

那么循环卷积一次相当于：

对于 ，有：

对于 ，有：

整理可得：

那么只需要维护 即可，因为

设 ，则：

其中 ，设 ，由于 ，可以发现它是一个二阶常系数齐次递推

设 ，则：

由于 ，所以 ，因此有两个不同的根

于是有：

由于 ，可以得到：

因此：

因此：

B. 投硬币

显然答案就是：

C. 植树造林

也就是问你有几个中位数，也就是

D. 签到题I

排序后第 个数

E. 等比数列三角形

标程被打爆了……

就是形如 的三角形个数

只需要满足：

也就是：

设 ，其中 ，且

由于 ，且 ，那么预处理 的时间复杂度就是 级别得了

那么这个暴力的时间复杂度就是：

恭喜获得一个常数比 1 小的算法

预处理是瓶颈

稍作优化，可以用 来存储 的数组，那么空间复杂度就降为了

然而这个做法还是挺烦的，既然都有 了，那么肯定能通过 来使得时间复杂度降下去

设 ，显然答案就是：

其中：

那么暴力模拟这个过程，时间复杂度为：

F. 乐色王传奇

算法1

我会！暴力枚举出每一种可能的情况，将最大值加起来，最后除以即可。

复杂度，期望得分分。

算法2

不如我们统计每个数对上面那个总答案的贡献，最后把所有的贡献加起来？

我们发现这个贡献即是以为最大值的情况数。

如果有值相同呢？那我们这样规定即可：值为第一关键字，行数为第二关键字，列数为第三关键字。

比如这个表是这样的：

N=2

1 1
1 1

那么。我们发现这么做不会影响答案，并且可以将每个数字的贡献统计得不重不漏。

所以这个情况数到底是多少呢？

对于来说，我们要求从其他行里选出来的数都严格小于它。

所以情况数是

对于每个数字，一遍统计即可，复杂度。期望得分分。

算法3

有一些奇怪的算法存在。我忘了，但是肯定有。期望得分分。

算法4

首先我们将每行的排序。

我们发现对于每一行我们可以一起算。

具体来说就是对于每个其他的行维护一个指针（共个），然后在维护一个当前行的指针。

每当时，我们扫一遍所有其它行的指针，如果其它行指针所指的元素小于所指的元素，令其它行指针，并且维护那个式子即可。

由于我们一共有个元素，所以我们要扫次。

故复杂度为（瓶颈就在这）。期望得分分。

算法5

那我们为什么不将个值一起算出来呢？

细想一下其实是可以的。

我们先将所有元素放一起排序，然后每个行维护一个指针（共个）。然后跟算法的思路一样。

注意下细节即可，复杂度，期望得分分。

G. many sum

for(int i = 1 ; i <= n ; ++ i) {
    for(int j = i ; j <= n ; j += i) {
        b[j] += a[i];
    }
}

此时已经可以通过此题了，但如果能做 岂不是更爽

考察这个过程，相当于做了一次高维前缀和，那么就模拟一遍即可

H. 图上计数

这题为啥没人做啊

对于操作一，相当于把子树给缩起来

对于操作二，相当于求子树第 大， 序一下就好了，离线后树状数组就可以了

I. 有毒的玻璃球

可以发现 是一个积性函数，那么线性筛出来就行了

J. J.I

重新说一遍题意

给定一个森林，在其中连尽可能多的边使得仍然是一个二分图（显然森林就是一个二分图）

首先对于每一棵树，可以把它看成一个pair，即分成左右两个点集

也就是说有一些，可以对于一个变成，要求最大化

其中是森林中的边的个数

如果你做过poj 1112的话，你会发现这是个背包裸题

直接压位跑一下就行了