官方题解｜方格染色

题目解析

涂黑的一组方格与棋子移动的方法相关，因此只需计算到达每个方格的方案数即可。

若我们忽略解法的复杂度我们可以使用以下这种动态规划的方法来解决这个问题：

vector<int> dp(n);
for (int i = 0; i < n; ++i)
    for (int j = i + A[i]; j < n; j += A[i])
        dp[j] += dp[i];

当 $A_i$ 较大时，对 $j$ 的迭代不会重复很多次，所以这种方法似乎是合理的，但如果以 $A_i=[1,1,\dots,1]$ 为例，则需要花费 $O(N^2)$ 的时间，所以这种算法无法通过本题。

考虑在 $A_i$ 相同的情况下集体更新。具体来说，在从 $i$ 开始的转换过程中，如果存在 $j$ 使得 $A_i=A_j$，那么之后在 $j$ 的循环过程中将它们全部相加。

时间复杂度

上述方法可以在 $O(N\sqrt N)$ 的时间复杂度内完成。

如果每个 $A_i$ 在更新的过程中全部重复掉，那么对于每个 $A_i$ 只需要将其移动一次，之后让 $A_j$ 代替 $A_i$ 更新。

最坏的情况是没有 "一起更新"，并且 $A_i$ 的值尽可能的小。

在这种情况下，$A$ 就像这个样子 $[1, 2, 2, 3, 3, 3, 4, \cdots]$，而那么 $j$ 的调用次数为：

$$\frac{N}{1} + \frac{N}{2} + \frac{N}{2} + \frac{N}{3} + \frac{N}{3} + \frac{N}{3} + \frac{N}{4} + \cdots$$

即：

$$N \times \big(1 + 2 \times \frac{1}{2} + 3 \times \frac{1}{3} + 4 \times \frac{1}{4} + \cdots + M \times \frac{1}{M} + \cdots\big)$$

上式中 $1 + 2 + 3 + 4 + \cdots + M = \frac{M \times (M + 1)}{2} = N$ 所以 $O(M) = O(\sqrt{N})$

那么我们可以由上式得到：

$$O \big(N \times \big( \overbrace{1 + 1 + 1 + \cdots + 1}^{M} + \cdots\big)\big) = O(N\sqrt{N})$$

故整体算法时间复杂度为 $O(N\sqrt{N})$。

AC代码

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 998244353;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        vector<int> arr(n);
        for (auto &x : arr) cin >> x;
        vector<int> dp(n), f(n);
        dp[0] = 1;
        for (int i = 0; i < n; ++i)
            for (int j = i + arr[i]; j < n; j += arr[i]) {
                dp[j] = (dp[j] + (dp[i] + f[i]) % MOD) % MOD;
                if (arr[j] == arr[i]) {
                    f[j] = (dp[i] + f[i]) % MOD;
                    break;
                }
            }
        int res = 0;
        for (int i = 0; i < n; ++i)
            res = (res + dp[i]) % MOD;
        cout << res << '\n';
    }
    return 0;
}