题解：P10738 [SEERC2020] 3-colorings

· · 题解

分析

小清新神秘构造题。

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

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

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

这种结构的好处是把总方案数变成了若干部分的和，回到题目要求中来，我们把 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;
    }
}