日记 - 伊埃斯的博客站

山重水复疑无路，柳暗花明又一村。

也许马上就柳暗花明了呢？

La Vaca Saturno Saturnita↗

鉴定为 CF 评测机神力，时间复杂度 $O(n \sqrt{n} \log^2 n)$ 。

设当前位置为 $l$ ，我们枚举当前 $k$ 的每个因子，然后二分找到下一个最近因子出现的位置 $nxt$ ，那么 $ans$ 就要加上 $(nxt - l) \times k$ ，然后 $k$ 除以 $a_{nxt}$ ，将 $l$ 赋值成 $nxt$ 后，开启新一轮的轮回。

时间复杂度里一个 $n$ 来自 $n$ 个查询，一个 $\sqrt{n}$ 来自 $\sqrt{n}$ 个因数，剩下的两个 $\log$ 来自二分查找和需要跳 $\log k$ 次。因为因数个数远远没有 $\sqrt{n}$ 个，他也不会实打实的跳 $\log_2 n$ 次，所以应该算是非常小的常数了，能卡着时限过。

Easy Demon Problem↗

确实是 Easy。

发现 $x = (suma - a_r)(sumb - b_c)$ 。直接枚举 $x = u \times v$ ，看看 $a$ 里有没有 $suma - u$ 或者 $suma - v$ ， $b$ 也是同理，如果都有就是 YES，如果对于所有的 $u \times v = x$ 都没有，那就是 NO。

Zapina↗

简单计数 dp，鉴定为涨信心题。

设 $dp_{i,j,0 / 1}$ 表示已经分了 $i$ 个人，一共用了 $j$ 本书，有没有人高兴。

转移方程也是十分的简单。枚举下一个人分配的书数量，有 $dp_{i + 1,j + x,k \lor [x = i + 1]} \gets dp_{i,j,k} \times \binom{n - j}{x}$ 。然后这个组合数是因为这 $n$ 本书是互相区分的。

制杖题↗

我是制杖。

一眼容斥，但是需要注意的是：对于前三个点，它的 $n$ 能开到 $10^7$ ，所以记得数组开大点。

Modulo Permutations↗

不是所有的计数题都用容斥

我们经过一番手玩，发现这个序列旋转后一定能变成两个单调递减的子串拼起来。一个子串的结尾是 $1$ ，另一个是 $2$ 。我们钦定 $1$ 结尾的子串在前，那么这个序列就形如 $\{a_1,a_2,\dots,a_x,1,a_{x + 1},a_{x + 2},\dots,a_{n - 2},2\}$ 。

观察到题意里说的这是一个排列，那么我们设 $b_i \in [1,2]$ 表示 $i$ 在以 $b_i$ 结尾的子串里，那么这个 $b$ 一定是由一堆极长的，只由 $1$ 或 $2$ 组成的子串构成。设 $dp_{i,1/2}$ 表示考虑 $1 \sim i$ ， $b_i = 1/2$ 的方案数，初始有 $dp_{1,1} = dp_{2,2} = 1$ 。

考虑如何转移。我们发现这个极长子串内一定是合法的，因为 $i \mod (i - 1) = 1 \le 2$ 。转移时枚举 $j$ 作为下一段开头，我们只用考虑 $j \mod (i - 1)$ 是否 $\le 2$ 就是了。

我们枚举 $i - 1$ 的倍数并加上余数进行转移，最终的答案就是 $ans = n(\sum_{i = 1}^{n}(dp_{i,1} + dp_{i,2}) - 1)$ 。减一是因为 $1,2$ 都存在， $dp_{1,1}$ 和 $dp_{2,2}$ 必然有一个不能延续到末尾。乘 $n$ 是因为 $n$ 个点都可以作为环的起点。

时间复杂度 $O(n)$ 。

众数 II↗

今天的重量级选手来了。

设展开后的数组叫 $b$ 。我们发现 $x$ 能成为众数当且仅当 $b_l = x$ 且每个区间的结尾都 $\ge x$ 。所以我们可以写出 $O(n^2V)$ 暴力：

1
for (int x = 2; x <= V; x++)
2
    for (int i = 1; i <= n; i++)
3
        for (int j = i; j <= n && a[j] >= x; j++)
4
            ans = (ans + a[j] - x + 1) % mod;

对于贡献为 $1$ 的，我们记录所有贡献不为 $1$ 的区间数，剩下的就是贡献为 $1$ 的区间数了。

考虑优化。我们发现在 $x,j$ 固定的情况下， $a_j - x + 1$ 也固定，所以我们可以这样：

1
for (int x = 2; x <= V; x++)
2
{
3
    for (int i = 1; i <= n; i++)
4
    {
5
        if (a[i] < x)
6
            continue;
7
        int p = i;
8
        while (a[p + 1] >= x)
9
            p++;
10
        for (int j = i; j <= p; j++)
11
            ans = (ans + (a[p] - x + 1) * (p - i + 1)) % mod;
12
    }
13
}

复杂度 $O(nV)$ 。

然后就是一大堆乱七八糟的推式子，建议直接阅读原文↗。

后日谈

我能等到柳暗花明的那一天吗？

Thanks for reading!

日记

周四 10月 16 2025

1054 字 · 5 分钟

life 日记