自动搬运

查看原文

来自洛谷，原作者为

	oMin0 oahzgnim| 悲欢离合总无情，一任阶前点滴到天明

搬运于2025-08-24 23:00:48，当前版本为作者最后更新于2024-07-11 15:57:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分析

小清新神秘构造题。

数据范围给得相当精准，感觉就是要大胆猜出做法。

首先观察一些基本结构，一个三元环方案数是 $6$，一条链染色方案数是 $3\times 2^{len-1}$，这时你已经能发现最终图里只有一个连通块，否则方案数是 $3^2$ 的倍数。

然后不妨想到先给 $1,2,3$ 连一个三元环并钦定它们的颜色分别就是 $1,2,3$，这样只需让其它点的方案数恰好是 $k$ 即可。然后根据数据范围必然想到二进制拆分，这时关键问题是我们需要让方案数加起来而不是乘起来，再进行一些尝试后能得到下面这种结构：

• 对一条链进行改造，我们额外对链上的第 $i$ 个点与 $(i-1)\bmod 3+1$ 连边，这样一来方案数变成了 $len+1$，因为每种方案都是对一个前缀（可以为空）染成 $(i\bmod 3)+1$，对其余点染成 $(i+1)\bmod 3+1$。

这种结构的好处是把总方案数变成了若干部分的和，回到题目要求中来，我们把 $4\sim 11$ 造成这种结构，然后把 $12\sim 19$ 挂到上面即可完成二进制拆分，因为可以控制使得后缀方案数总是 $1$，前缀方案数是 $2$ 的若干次幂。

还有一些细节：比如我们有时要给空前缀挂点，这可以通过直接与 $1$ 连边实现；比如我们其实希望总方案数是 $\text{popcount}(k)$ 个部分的和，因此有时需要对 $4\sim 11$ 额外连一条边，以强制一段后缀染成 $(i+1)\bmod 3+1$。

具体实现见代码。

代码

/*
  author: honglan0301
  Sexy_goodier _ xiaoqing
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cmath>
#include <random>
#include <set>
#include <bitset>
#include <assert.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl "\n"

int n=19;
vector <pair<int,int>> cs;
#define lowbit(x) (x&(-x))

signed main()
{
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
	cs.pb(mp(0,1)); cs.pb(mp(1,2)); cs.pb(mp(2,0));
	for(int i=3;i<=10;i++) cs.pb(mp(i%3,i));
	for(int i=3;i<10;i++) cs.pb(mp(i,i+1));
	cout<<n<<" "<<cs.size()<<endl;
	for(auto i:cs) cout<<i.fi+1<<" "<<i.se+1<<endl;
	for(int i=1;i<=500;i++)
	{
		vector <pair<int,int>> nb;
		int ni=i,nx=3,ny=11; 
		if(1)
		{
			int dd=__lg(lowbit(ni));
			for(int j=1;j<=dd;j++) nb.pb(mp(0,ny)),ny++; ni>>=(dd+1);
		}
		while(ni)
		{
			int dd=__lg(lowbit(ni)); 
			for(int j=1;j<=dd+1;j++) nb.pb(mp(nx,ny)),nb.pb(mp((nx+1)%3,ny)),ny++; ni>>=(dd+1); nx++;
		}
		if(nx<=10) nb.pb(mp((nx+1)%3,nx));
		for(int j=ny;j<=18;j++) nb.pb(mp(0,j)),nb.pb(mp(1,j));
		cout<<nb.size()<<endl;
		for(auto i:nb) cout<<i.fi+1<<" "<<i.se+1<<endl;
	}
}