火大

dehsirehC · 2024-09-03 23:23:01 · 题解

下面会介绍两种做法，希望大家不要火大。

首先考虑当 m<n 时显然无解，接下来就不再考虑这种情况了。

由于 m\ge n ，故对于任意 1\le i\le j\le n ，区间 [\frac{m(i-1)}{j},\frac{mi}{j}) 中必定存在整数。

对于所有 0\le i<j\le n ，我们称 \lceil\frac{mi}{j}\rceil 为关键点，特别的，我们认为 m 也是关键点。

我们将所有关键点去重并排序后得到序列 b_0,b_1,\cdots,b_k 。

容易发现 b 中相邻两数组成的区间 [b_i,b_{i+1}) 内的数是没有本质区别的。

换句话说，我们只需要考虑 a_i 为 b_0,b_1,\cdots b_{k-1} 这 k 个数的情况即可。

此时写一个暴搜可以发现， n 从 18 开始就必定无解了，正经证明我哪会。

（我写的搜索在本地只需要跑 2min 左右）

由于 T 比较大，故可以将 n 在 1\sim 17 之间的所有解先搜出来，再每组询问暴力判断。

具体的，把问题看成 m=1 且 a_i 为实数时的情况，关键点与 a_i 用分数表示。

而原问题本质就是让一些关键点区间不能选（没有整数点），故判断就看是否所有区间都能选即可。

不过现在还有一个问题，就是预处理搜出所有合法的解太慢了，而由于解数太多所以也无法打表。

但是容易发现真正会用到的解数可能并不多，故直接把这些解打表即可。

而找会用到的解直接把 m 比较小的全跑一遍即可，可以证明当 m\ge n(n-1) 时 a_i 是整数与实数没有区别，换句话说，只需要考虑 n\le m\le n(n-1) 时会用到的解即可。

（我写的打表程序在本地只需要跑 1min 左右）

标程在没有压代码长度的情况下只有不到 30\text{KB} ，可以说还是很短的。

下面是暴搜所有合法的解并判断的一种实现方式：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int M = 1e8;
int T, m, n, num, a[100], f[100][100];
int l[20][20], r[20][20], p[20], s[20];
pair<int, pair<int, int>> A[100];
vector<vector<pair<pair<int, int>
, pair<int, int>>>> v[20];
void dfs(int now) {
    if (now > n) {
        vector<pair<pair<int, int>
        , pair<int, int>>> V(n);

        for (int i = 1; i <= n; i++) {
            V[i - 1] = {A[p[i]].second,
                        A[p[i] + 1].second
                       };
        }

        v[n].emplace_back(V);
        return;
    }

    unsigned int S = 0;

    for (int i = 1; i < now; i++) {
        S |= 1 << s[i] * now / M;
    }

    int t = __lg((~S) & -(~S));

    for (int i = l[now][t]; i <= r[now][t]; i++) {
        bool flag = 1;

        for (int j = 1; j < now; j++) {
            if (f[i][p[j]] > now) {
                flag = 0;
                break;
            }
        }

        if (flag) {
            s[now] = a[p[now] = i];
            dfs(now + 1);
        }
    }
}
inline void init(int n) {
    if (!v[n].empty()) {
        return;
    }

    num = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (__gcd(i, j) == 1) {
                A[++num] = {(M * j + i - 1) / i, {i, j}};
            }
        }
    }

    sort(A + 1, A + num + 1);

    for (int i = 1; i <= num; i++) {
        a[i] = A[i].first;
    }

    A[num + 1].second = {1, 1};

    for (int i = 1; i <= num; i++) {
        f[i][i] = n + 1;

        for (int j = i + 1; j <= num; j++) {
            f[i][j] = 0;

            for (int k = n; k; k--) {
                if (a[i]*k / M == a[j]*k / M) {
                    f[i][j] = k;
                    break;
                }
            }

            f[j][i] = f[i][j];
        }
    }

    memset(l, 0x3f, sizeof(l));
    memset(r, 0, sizeof(r));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= num; j++) {
            int t = a[j] * i / M;
            l[i][t] = min(l[i][t], j);
            r[i][t] = max(r[i][t], j);
        }
    }

    dfs(1);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;

    while (T--) {
        cin >> n >> m;

        if (n >= 18 || n > m) {
            cout << "fire big\n";
            continue;
        }

        init(n);
        bool flag = 0;

        for (int i = 0; i < v[n].size(); i++) {
            flag = 1;

            for (int j = 0; j < n; j++) {
                int x = v[n][i][j].first.first;
                int y = v[n][i][j].first.second;
                int X = v[n][i][j].second.first;
                int Y = v[n][i][j].second.second;

                if ((m * y + x - 1) / x == (m * Y + X - 1) / X) {
                    flag = 0;
                    break;
                }
            }

            if (flag) {
                for (int j = 0; j < n; j++) {
                    int x = v[n][i][j].first.first;
                    int y = v[n][i][j].first.second;
                    cout << (m * y + x - 1) / x << " ";
                }

                cout << '\n';
                break;
            }
        }

        if (!flag) {
            cout << "fire big\n";
        }
    }

    return 0;
}

接下来介绍另一种做法，考虑增量法。

找出 n=17 时的所有关键点，考虑将 a_i 描述为关键点的区间，而不是某个关键点。

假设现在得到了 n=x-1 时的所有解，考虑拓展得到 n=x 时的所有解，即考虑 a_x 是什么。

枚举 a_x 在 x 段中的哪一段，即枚举整数 1\le j\le x 满足 a_x\in [\frac{m(j-1)}{x},\frac{mj}{x}) 。

而对于 a_{1\sim x-1} ，将它们从小到大排序（区间不交）后即可得到它们在 n=x\to x+1 时的限制。

将之前对应的关键点区间与新限制对应的关键点区间取交即可，若存在交为空则增量失败。

由于 m\ge n(n-1) 时任意解均合法，故只需要考虑 n\le m<n(n-1) 时的情况。

设 f_i 表示 n=i 时上述算法得到的解的数量，则该算法总时间复杂度即为 O(\sum_{i=1}^{17} f_ii^3+17T) 。

实践得到上式约为 1.6\times 10^8 ，若在过程中将解去重，则上式只有约 3\times 10^7 ，都跑得很快。

顺带一提，上述做法如果不对询问记忆化的话时间复杂度是可以达到 O(\sum_{i=1}^{17} f_ii^3+T\max_{i=1}^{17} f_ii) 的，不过由于出题人非常良心，并没有卡不记忆化的做法（即一种询问 (n,m) 不会出现特别多次）。

如果你使用了其它的做法通过了此题，欢迎联系我。