P11314 [RMI 2021] 礼物 / Present 题解

· · 题解

P11314 [RMI 2021] 礼物 / Present 题解

一个正整数集合 S 是好的当且仅当 \forall a,b \in S，\gcd(a,b) \in S。定义 S 的权值为 \sum\limits_{a \in S} 2^{a-1}。求出权值第 k 小的好的集合。k \le 1.5 \times 10^9。

在这个数据范围下，我们可以感觉到答案集合的最大值并不会太大。因此，我们可以尝试直接把答案搜出来。具体地，假设答案集合的最大值为 m，可以从 m 到 1 依次考虑不选 / 选的情况，找出其中权值第 k 小的集合。

不过，显然 O(ans) 的搜索算法是行不通的。

我们考虑在选完较大的数之后，这些已经确定选的数对那些还没确定要不要选的数产生的限制。这时候，我们就会发现，不同的大数选择情况对小数的限制可能是相同的。例如，假设大于 2 的数都已经确定选不选，那么大数集合是 \{7,3\} 和 \{5,3\} 对 1 和 2 的限制是一样的：2 可选可不选，1 必须要选。这就给了我们降低复杂度的机会。

具体地，可以发现，我们在考虑 x 要不要选的时候，如果大于 x 的选的数中 x 的倍数的最大公因数等于 x，那么 x 就必须要选（这是显然的）；否则，x 可选可不选，因为就算没选 x，用集合里其它的数取最大公因数也不会得到 x，因此不违反题目要求。

因此，搜索的时候就只需要记录：所有还没有确定选不选的数中，已经确定要选的数中它们的倍数的最大公因数是多少。对于一个还没有确定选不选的数 x，这个值只有 \lfloor\frac{m}{x}\rfloor+1 种不同的取值（因为可以为 0）。同时可以发现，如果 \lfloor\frac{m}{x}\rfloor \le 2，记录这个值是没有意义的，因为无论如何都不会违反题目规定。

我们在记忆化搜素的时候，记录 (x,msk) 表示当前正在考虑选不选 x，并且上文所述的状态为 msk（可以用变进制数压成一个整数）时，剩下 x 到 1 这些数有多少种选法。此时总状态数大概是 \sum\limits_{x=1}^{m} \prod \limits_{i=1}^{\min(x-1,\lfloor\frac{m}{3}\rfloor)} (\lfloor\frac{m}{i}\rfloor+1) 的。转移也很简单，枚举 x 选不选，如果选就用 x 更新一下 msk 再递归到 x-1。

预处理结束后，对于一个给定的 k 求答案也很简单。还是从大往小考虑选不选，优先不选，如果不选的方案数小于等于 k，答案集合就没有这个数；否则就有这个数。这样求一次答案是 O(m^2) 的（因为更新 msk 要 O(m) 时间）。

如果你写完代码去跑一遍极限数据，就会发现答案集合的最大值不超过 m=37。虽然将其带入上面的公式，算出来状态数是 1.3 \times 10^{12}，但是有非常多的状态是不能同时取到的，例如在 1 的倍数的最大公因数为 4 时 2 的倍数的最大公因数为 2。具体测试后发现状态数只有 594228 种，可以轻松通过。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n=37,m=n/3,k;
int gcd[45][45];
int bas[20];
unordered_map<int,int> mp[45];
//msk[i] : 目前选的数中 i 的倍数的所有数的 gcd 是 i 的几倍
int dfs1(int x,int msk)
{
    if(!x) return mp[x][msk]=1;
    if(mp[x].count(msk)) return mp[x][msk];
    int ret=0,_=msk;
    if(x>m || msk/bas[x-1]%(n/x+1)!=1) ret+=dfs1(x-1,msk);
    for(int i=1;i<=m;i++)
    {
        if(x%i) continue;
        int k=msk/bas[i-1]%(n/i+1);
        msk-=k*bas[i-1];
        k=gcd[k][x/i];
        msk+=k*bas[i-1];
    }
    ret+=dfs1(x-1,msk);
    mp[x][_]=ret;
    return mp[x][_]=ret;
}
vector<int> dfs2(int x,int msk,int rem)
{
    if(!x) return vector<int>();
    if(x>m || msk/bas[x-1]%(n/x+1)!=1)
    {
        int tmp=mp[x-1][msk];
        if(tmp>rem) return dfs2(x-1,msk,rem);
        rem-=tmp;
    }
    for(int i=1;i<=m;i++)
    {
        if(x%i) continue;
        int tmp=msk/bas[i-1]%(n/i+1);
        msk-=tmp*bas[i-1];
        tmp=gcd[tmp][x/i];
        msk+=tmp*bas[i-1];
    }
    vector<int> ret=dfs2(x-1,msk,rem);
    ret.push_back(x);
    return ret;
}
void solve()
{
    scanf("%lld",&k);
    vector<int> ans=dfs2(n,0,k);
    printf("%lld ",(int)ans.size());
    for(int x:ans) printf("%lld ",x);
    printf("\n");
}
signed main()
{
    for(int i=0;i<=40;i++) for(int j=0;j<=40;j++) if(i|j) gcd[i][j]=__gcd(i,j);
    for(int i=bas[0]=1;i<=m;i++) bas[i]=bas[i-1]*(n/i+1);
    dfs1(n,0);
    int t;cin>>t;
    while(t--) solve();
}