JXOI Round 2 题解

N^N

根据题意，枚举即可。

密码

判断所有的 到 右移的位数是否一致即可。

画图

每个单元格的最终颜色只取决于对其进行的最后一次操作。在这种情况下，按相反的顺序考虑运算往往会使解题变得容易。

如果将操作的顺序倒过来考虑，问题陈述中的过程就相当于下面的过程：

这样，通过处理已操作的行列数、每行每列是否已操作以及每种颜色已确定的单元格数，就可以得到答案。

具体来说，对第 行的操作只有在之前没有对第 行进行操作的情况下才会被认为是有效的，在这种情况下，颜色为 的已确定单元格的数量会随着未触及列的数量而增加；这同样适用于对第 列的操作。

添加与删除

这个问题可以用一种叫做双向链表的数据结构来解决。双链表是一种直观的数据结构，其中每个元素只维护紧随其后的元素。

每当插入或删除一个元素时，都会相应地更新其相邻元素的 "上一个元素 "和 "下一个元素"。

例如，我们用下面的输入来说明这个过程。为清晰起见，值是按 的顺序排列的，但注意这不是必须的。

3
3 1 4
2
1 1 2
2 3

这样，问题就迎刃而解了。

黑白

涂黑的一组方格与棋子前进的方式相对应，因此只需计算后者即可。

现在，让我们忽略计算复杂性，专注于解决问题。它可以归结为 DP（动态编程），用下面的伪代码表示：

dp={1,0,...,0};
for(i=1;i<=N;i++)
    for(j=i+A[i];j<=N;j+=A[i])
        dp[j]+=dp[i];
print(sum(dp));

当 较大时， 上的迭代不会重复很多次，所以这种方法似乎是合理的，但如果以 为例，则需要花费 时间，所以这种算法很难通过。

取而代之的是，让我们考虑如何在 很小的情况下快速更新 DP 数组。

对于 ，当且仅当 是 的倍数（即 除以 的余数等于 除以 的余数）时，才会发生从 到 的转换。

因此，如果我们定义一个数组，如 {除以 的余数是 }，问题似乎又可以迎刃而解了（事实的确如此）。

那么， 是 "小" 还是 "大 "呢？

假设 是 是 "小" 和 "大" 的边界。

• 如果对小 进行操作，该部分的时间复杂度为 。
• 如果对大型 进行操作，则该部分的时间复杂度为 。

为了使 最小化，让 最小化是最优的（简短证明：算术和几何平均数不等式）。
实施时，可以将 固定为 附近的任意常数。根据常数的不同，最佳的 可能与 相差甚远，因此在某些情况下不妨多试几次。

至于如何正确实现，留给读者自己去探索。我们将在社论后展示示例代码。

在 处选择一个边界或分割成 个数据包以快速求解子问题的技术称为根号分治。