自动搬运

查看原文

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 23:07:17，当前版本为作者最后更新于2025-01-10 10:16:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神秘 adhoc。

首先你考虑一下最大多少，然后你会发现每个非 $1$ 点至少选择一条入边，那么最大值就是 $3^{32}\times 4$，刚好略大于 $k$ 的那个限制。由此猜测，不会有 $-1$，他就是让我们构造的。

然后你会发现你搓个 DAG 答案必然是每个点入边数量之积，所以你不能搓 DAG。

这引导我们去搓一个环。对于一个单独的环（$2\sim n$ 组成的环），外向生成树数量是每个点入边之积减去环上两两之间边的积。

但是这样还是不够，我们只能弄出 $3^{32}\times 4-\prod x_i$，其中 $x_1,x_2,\dots,x_{32}\leq 3$，$x_{33}\leq 4$。

考虑搓一个环，然后加一条 $2\to 4$ 的边的后果。此时方案数是总数减去出现 $2,3,4,\dots,n$ 这个环的方案数再减去 $2,4,5,\dots,n$ 这个环的方案数。也就是，减去 $\prod x_i+3\prod_{i\neq 3}x_i$。

我们钦定 $x_i=1$，即可得到 $1+3$。

然后再加上 $2\to 5$ 的边，以及加两条 $2\to 4$ 的边，通过一定计算会发现可以得到 $1+3^2$ 和 $1+3\times 2$。

这启发我们求出要减去的部分，然后对减去的部分三进制分解，依次加入边。也就是，对于第 $i$ 位，$2\to i+2$ 的边数为减去部分第 $i$ 位的值。

构造会有一些 corner case，所以可以找到比 $n$ 大的第一个 $3^x$ 或 $3^x\times 2$ 或 $3^x\times 4$ 然后去构造。具体细节可以看代码。

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
using namespace std;
int a[40],b[40],c[40],cnt;
void solve(){
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	int n; cin>>n;
	if(n==1){
		cout<<1<<" "<<0<<"\n";
		return ;
	}
	int now=1,cnted=0;
	cnt=0;
	while(now<n){
		if(now*2>=n){
			now*=2;
			a[++cnt]=3;
			a[1]=2;
			cnted+=2;
		}
		else{
			now*=3;
			a[++cnt]=3;
			cnted+=3;
		}
	}
	if(now==n){
		cout<<cnt+1<<" "<<cnted<<"\n";
		for(int i=1;i<=cnt;i++){
			for(int j=1;j<=a[i];j++) cout<<1<<" "<<i+1<<"\n";
		}
		return ;
	}
	if(cnted==101){
		cnt--;
		a[1]=3;
		a[cnt]=4;
		cnted=100;
	}
	for(int i=1;i<=cnt;i++) c[i]=1;
	c[2]=0;
	int ex=now-n,it=2;
	while(ex){
		int md=ex%3; ex/=3;
        b[it]=md;
		it++;
	}
	cout<<cnt+1<<" "<<cnted<<"\n";
	for(int i=1;i<=cnt;i++){
		if(i==1){
			if(a[1]==3) cout<<1<<" "<<2<<"\n";
			cout<<1<<" "<<2<<"\n";
			cout<<cnt+1<<" "<<2<<"\n";
			continue;
		}
		for(int j=1;j<=c[i];j++) cout<<i<<" "<<i+1<<"\n";
		for(int j=1;j<=b[i];j++) cout<<2<<" "<<i+1<<"\n";
		for(int j=1;j<=a[i]-c[i]-b[i];j++) cout<<1<<" "<<i+1<<"\n";
	}
}
signed main(){
	int t; cin>>t;
	while(t--) solve();
	return 0;
}