E 时间复杂度计算 + 暴力

题意

设 $f(n) $ 为满足 $ px + q(x + 1) + r(x + 2) = n$ 的方案数，其中要求：

  1. $p, q, r, x 为整数$
  2. $1 \le p, q, r, x \le N$

有 $T$ 次询问 $(1\le T \le 10^4)$，每次询问给出一个 $L, R$, 保证 $(1\le L \le R \le N \le 10^5)$，请求出：$ans = \sum \limits_{i=L}^{R} f(i)$

思路

先枚举出 $f(n)$:

for (int i = M; i < N; ++i) {
    // p > r 的情况
    for (int p = 1; p * i < N; ++p)
        for (int q = 3; q * (i + 1) + p * i < N; ++q)
            sum[q * (i + 1) + p * i] += (q - 1) / 2;
    // p <= r 的情况
    for (int r = 0; r * (i + 2) < N; ++r)
        for (int q = 3; q * (i + 1) + r * (i + 2) < N; ++q)
            sum[q * (i + 1) + r * (i + 2)] += (q - 1) / 2;
}

然而当 $M = 1$ 时，上面的代码要跑很久, 需要一定的优化。我们先计算以上代码的时间复杂度：

$T(n) = O(\int_{M}^{N}\int_{0}^{N/y}\int_{0}^{(N-xy/x)}dxdydz) = O(\frac{N^2}{M})$

$N^2$ 约为 $10^{10}$，若 $M = 500$ ，那么时间复杂度大概就在 $O(2e7)$ 的量级内，可以跑过。

因为 $i$ 被下截断了，那么这个时候我们思考怎么处理比较小的 $i$。我们可以使用多重背包计算方案数，时间复杂度为 $O(MN)$，大约在 $5e7$ 这个量级。

总时间复杂度为 $O(\frac{N^2}{M}+NM)$

再优化

可以看到，时间复杂度和均值不等式的形式很像。只要取 $\frac{N^2}{M}=NM$，就可以取到最小值，最小值为 $\sqrt{N}$。此时,时间复杂度为 $O(N^{1.5})$

代码

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

const int N = 1e5 + 5, M = sqrt(N);
ll sum[N], dp[N];

void init() {
    // 较小情况，多重背包计算方案数
    for (int i = 1; i < M; ++i) {
        // 选中 i, i + 1, i + 2 这种方案
        dp[3 * i + 3] = 1;
        for (int u = i; u <= i + 2; ++u)
            for (int j = 3 * i + 3; j < N; ++j)
                dp[j] += dp[j - u];

        for (int j = 3 * i + 3; j < N; ++j) {
            sum[j] += dp[j];
            dp[j] = 0;
        }
    }
    
    // 较大情况，直接枚举
    for (int i = M; i < N; ++i) {
        // p > r 的情况
        for (int p = 1; p * i < N; ++p)
            for (int q = 3; q * (i + 1) + p * i < N; ++q)
                sum[q * (i + 1) + p * i] += (q - 1) / 2;
        // p <= r 的情况
        for (int r = 0; r * (i + 2) < N; ++r)
            for (int q = 3; q * (i + 1) + r * (i + 2) < N; ++q)
                sum[q * (i + 1) + r * (i + 2)] += (q - 1) / 2;
    }

    for (int i = 1; i < N; ++i)
        sum[i] += sum[i - 1];
}

int main() {
    init();
    int t;
    scanf("%d", &t);
    for (int _ = 1; _ <= t; ++_) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("Case #%d: %lld\n", _, sum[r] - sum[l - 1]);
    }
    return 0;
}