P11314 Sol || 别样的分段打表大战

CarroT1212 · 2025-11-11 14:47:07 · 题解

题意即，根据每个集合 S_i 的降序排序取字典序第 k 小的。

容易感受到值域似乎就几十的样子。

考虑一个这样的过程：从小到大枚举最大值 a_1，再从小到大枚举次大值 a_2<a_1，尝试加入 \gcd(a_1,a_2)，再从小到大枚举还没被加入的 a_3<a_2，把当前已被加入的数与 a_3 的 \gcd 尝试加入，再枚举 a_4<a_3……这样就可以精准地按我们想要的顺序依次得到每个 S_i。

关于其正确性：

• 枚举的 a_i 可以理解为，集合中无法当作其它数的 \gcd 的东西。两个数的 \gcd 肯定不大于它们自身，所以从大到小枚举这些 a_i 不会出问题。
• 实际加入数时只须考虑每次枚举的 a_i 和已加入的数的 \gcd，而这些新被加入的 \gcd 没有办法和别的数一起导致更多的 \gcd 被加入，所以就不用处理了。
• 显然也符合字典序。

根据这个可以实现出一个跑起来类似 O(k\log) 的暴力。叠一个块长大概 B=2\times 10^6 的分段打表即可通过，表里存第 Bi 个状态的 a。

打表程序：

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9,N=107;
const ll J=1e18;
int n,g[N][N];
int st[N],tp,vis[N],now,li[N];
void go(int p,int lim) {
    if (now%2000001==0) {
        cerr<<now<<"\n";
        printf(",{");
        for (int i=0,flg=0;i<p;i++) {
            if (flg) printf(","); flg=1;
            printf("%d",li[i]);
        } printf("}");
    }
    for (int i=1;i<=tp;i++) for (int j=1;j<=tp;j++) if (!vis[g[st[i]][st[j]]]) exit(0);
    now++;
    for (int i=1;i<=lim;i++) if (!vis[i]) {
        li[p]=i;
        int tmp=tp;
        st[++tp]=i,vis[i]=1;
        for (int j=1;j<=tmp;j++) {
            if (!vis[g[i][st[j]]]) st[++tp]=g[i][st[j]];
            vis[g[i][st[j]]]++;
        }
        go(p+1,i-1);
        for (int j=1;j<=tmp;j++) vis[g[i][st[j]]]--;
        vis[i]=0,tp=tmp;
    }
}
bool ORY; int main() {
    freopen("biao.txt","w",stdout);
    for (int i=0;i<N;i++) for (int j=0;j<N;j++) g[i][j]=__gcd(i,j);
    go(0,N-1);
    cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
    return 0;
}

要跑几分钟。