E 时间复杂度计算 + 暴力

题意

设 为满足 的方案数，其中要求：

有 次询问 ，每次询问给出一个 , 保证 ，请求出：

思路

先枚举出 :

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;
}

然而当 时，上面的代码根本跑不动, 需要一定的优化。我们先计算以上代码的时间复杂度：

约为 ，若 ，那么时间复杂度大概就在 的量级内，可以跑过。

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

总时间复杂度为

再优化

可以看到，时间复杂度和均值不等式的形式很像。只要取 ，就可以取到最小值，最小值为 。此时,时间复杂度为

代码

#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;
}