专栏文章

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

CCarroT1212菜萝卜
P11314题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mina9pgf
此快照首次捕获于
2025/12/01 23:07
3 个月前
此快照最后确认于
2025/12/01 23:07
3 个月前
查看原文
题意即，根据每个集合 SiS_i 的降序排序取字典序第 kk 小的。
容易感受到值域似乎就几十的样子。
考虑一个这样的过程：从小到大枚举最大值 a1a_1，再从小到大枚举次大值 a2<a1a_2<a_1，尝试加入 gcd⁡(a1,a2)\gcd(a_1,a_2)，再从小到大枚举还没被加入的 a3<a2a_3<a_2，把当前已被加入的数与 a3a_3 的 gcd⁡\gcd 尝试加入，再枚举 a4<a3a_4<a_3……这样就可以精准地按我们想要的顺序依次得到每个 SiS_i。
关于其正确性：
  • 枚举的 aia_i 可以理解为，集合中无法当作其它数的 gcd⁡\gcd 的东西。两个数的 gcd⁡\gcd 肯定不大于它们自身，所以从大到小枚举这些 aia_i 不会出问题。
  • 实际加入数时只须考虑每次枚举的 aia_i 和已加入的数的 gcd⁡\gcd，而这些新被加入的 gcd⁡\gcd 没有办法和别的数一起导致更多的 gcd⁡\gcd 被加入，所以就不用处理了。
  • 显然也符合字典序。
根据这个可以实现出一个跑起来类似 O(klog⁡)O(k\log) 的暴力。叠一个块长大概 B=2×106B=2\times 10^6 的分段打表即可通过，表里存第 BiBi 个状态的 aa。
打表程序：
CPP
#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;
}
要跑几分钟。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...