题解：P15364 [CTS 2026] 三色花园
题意简述
Alice 拿到一张三色染边的竞赛图。称没有包含全部三种颜色的有向简单环为坏环，题目保证每个顶点至多属于
下面的方案在
| 通信长度 | 满分上限 | |
|---|---|---|
思路
删去一种颜色，把问题转为保存环结构
对每种颜色
对
这样补边有两个作用。首先，
现在考虑原图的一条边
恢复方向后，如果
于是，如果 Bob 的某个环缺少颜色
这里必须证明整个坏环集合的包含关系。仅证明 Bob 的每张删色图中每个顶点至多属于
k=0,1 ：排列与有序环序列
当
当
因此，每张
设
第一项对应孤点。对于一个大小为
编码时依次枚举首个分量大小、顶点集合、环上顺序，再递归处理剩余顶点。若前面选项的总数为
用高精度整数计算得到
k=2 ：环沿着互不相交的路径相接
这一部分需要更仔细地分析结构。强连通分量不一定只有两个环，忽略方向后的一个点双连通分量也不一定只有两个环。例如，六边形
真正成立的结论是：每个非平凡强连通分量可以从一条有向环开始，不断加入新环；每个新环与已有部分恰好共用某条旧环上的一段有向路径，而且这段路径上的顶点此前都只属于一个环。 共享路径可以只有一个顶点；新环在共享路径之外也可能没有新顶点，此时加入的是一条闭合该路径的边。
下面证明这个结论。任意强连通有向图都可以从一条有向环开始，逐渐加入有向耳，直到得到整个图。构造过程中，若尚有未加入的顶点，就利用强连通性找到一条离开当前图又回到当前图的路径，并截取内部顶点都在图外的一段；顶点全部加入后，剩余边分别视作长度为一的耳。
考虑加入一条从
强连通图中，一个只属于一个环的顶点，其入度和出度都等于一：如果有两条出边，分别沿简单路径返回这个顶点，就能得到两个不同的环；入边同理。因此，刚才的返回路径唯一，并且完全位于同一条旧环上。新耳恰好增加一个环，这个新环只与那条旧环沿上述路径相交。
归纳可知，把每条有向简单环看成一个点，把有公共顶点的两条环连边，得到的是一棵树；两条相邻环的交集是一段同向的路径。同一条环上用于连接不同相邻环的共享路径之间没有公共顶点，否则某个顶点会属于三个环。
注意，这个结论不保证分量中存在只属于一个环的顶点。前面的六点例子中，每个顶点都属于两个环。因此，最外层需要保存完整的根环，而不能强行选一个只属于一个环的顶点作根。
用递归描述给 k=2 的结构排名
任选一条环作为环树的根。对于它与子环的共享路径，选择共享路径之间的边界作为切口，将根环展开成一条线性的主路径，最后再将主路径的首尾连接起来。沿主路径依次记录以下两种单元：
- 一个没有连接子环的普通顶点。
- 一段包含
h\ge1 个顶点的共享路径，以及子环中从共享路径末端返回首端的另一条路径。
第二种单元中，共享路径上的点已经属于两个环，不能再连接其他环；另一条路径的内部顶点则仍可递归记录其子环。设另一条路径有
我们将这个递归描述的形状与顶点标号分开保存。按固定的遍历顺序记录各顶点，就得到一个
下面用生成函数计算描述数量，变量
主路径上没有顶点的描述只有空路径；主路径上恰好一个顶点的描述是
最后处理最外层强连通分量。它要么是一个孤点，要么是主路径上至少有三个顶点的描述首尾相接。主路径恰好有两个顶点时，有两种情况：两个各占一个顶点的单元，或者一个共享路径有两个顶点的单元。因此，设
这些式子是在计算递归描述的数量，允许少量冗余描述。冗余只会使上界变大，不影响对实际图进行编码和恢复。
所有系数都可以按顶点数从小到大，用
初始化
下标为负的项视为零，空区间求和也为零；
精确计算得到
位，满足第三个子任务的满分限制。
实现排名时，先枚举第一个分量的总顶点数，再递归处理剩余分量。分量内部的一条路径，则依次枚举第一个单元的总顶点数
如果当前路径要求至少有
为了避免枚举
从输入中取出环树
先求三张删色图的强连通分量。对于一个分量，使用带阻塞集合的 Johnson 搜索枚举其中的所有有向简单环，以环上的最小标号作为搜索起点，保证每条环恰好枚举一次。
这一步不会遇到一般有向图中环数指数增长的问题。每个顶点至多出现在两个环中，所以全部环的长度之和至多为
对每个顶点记录它属于哪些环，就能找到相交的环及其共享路径。选根环后沿环树递归，将共享路径与子环的另一条路径分别写入描述。两条相邻环共享整段路径时，子环的另一条路径可能没有内部顶点；代码也处理了这种情况。
Bob 先反排名得到形状和顶点排列，恢复每个分量内部的边，再按分量顺序补齐向前的边，得到三张
复杂度分析
每张删色图的强连通分量、环枚举及结构提取需要
若将高精度整数最多占用的
两次程序运行各自初始化所需计数表。第二次运行不依赖 init 曾被调用，也不依赖第一次运行留下的任何状态。
参考代码
#include "garden.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <functional>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
namespace {
using namespace std;
// Nonnegative arbitrary-precision integers, stored in base 2^32.
struct Z {
vector<uint32_t> d;
Z(uint64_t x = 0) {
if (x) d.push_back(uint32_t(x));
if (x >> 32) d.push_back(uint32_t(x >> 32));
}
void trim() { while (!d.empty() && d.back() == 0) d.pop_back(); }
template<class T> T convert_to() const { return d.empty() ? 0 : T(d[0]); }
friend bool operator<(const Z &x, const Z &y) {
if (x.d.size() != y.d.size()) return x.d.size() < y.d.size();
for (int i = int(x.d.size()) - 1; i >= 0; --i)
if (x.d[i] != y.d[i]) return x.d[i] < y.d[i];
return false;
}
friend bool operator==(const Z &x, const Z &y) { return x.d == y.d; }
friend bool operator!=(const Z &x, const Z &y) { return !(x == y); }
friend bool operator>=(const Z &x, const Z &y) { return !(x < y); }
friend bool operator>(const Z &x, const Z &y) { return y < x; }
Z &operator+=(const Z &y) {
d.resize(max(d.size(), y.d.size()), 0);
uint64_t carry = 0;
for (size_t i = 0; i < d.size(); ++i) {
uint64_t v = uint64_t(d[i]) + (i < y.d.size() ? y.d[i] : 0) + carry;
d[i] = uint32_t(v);
carry = v >> 32;
}
if (carry) d.push_back(uint32_t(carry));
return *this;
}
Z &operator-=(const Z &y) {
assert(*this >= y);
uint64_t borrow = 0;
for (size_t i = 0; i < d.size(); ++i) {
uint64_t v = uint64_t(i < y.d.size() ? y.d[i] : 0) + borrow;
borrow = uint64_t(d[i]) < v;
d[i] = uint32_t(uint64_t(d[i]) - v);
}
trim();
return *this;
}
friend Z operator+(Z x, const Z &y) { return x += y; }
friend Z operator-(Z x, const Z &y) { return x -= y; }
friend Z operator*(const Z &x, const Z &y) {
if (x.d.empty() || y.d.empty()) return 0;
Z z;
z.d.assign(x.d.size() + y.d.size(), 0);
for (size_t i = 0; i < x.d.size(); ++i) {
uint64_t carry = 0;
for (size_t j = 0; j < y.d.size(); ++j) {
uint64_t v = uint64_t(x.d[i]) * y.d[j] + z.d[i + j] + carry;
z.d[i + j] = uint32_t(v);
carry = v >> 32;
}
z.d[i + y.d.size()] = uint32_t(carry);
}
z.trim();
return z;
}
Z &operator<<=(int shift) {
if (d.empty() || !shift) return *this;
int whole = shift / 32, part = shift % 32;
d.insert(d.begin(), whole, 0);
uint64_t carry = 0;
for (size_t i = whole; i < d.size(); ++i) {
uint64_t v = (uint64_t(d[i]) << part) | carry;
d[i] = uint32_t(v);
carry = v >> 32;
}
if (carry) d.push_back(uint32_t(carry));
return *this;
}
Z &operator>>=(int shift) {
int whole = shift / 32, part = shift % 32;
if (whole >= int(d.size())) { d.clear(); return *this; }
d.erase(d.begin(), d.begin() + whole);
uint32_t carry = 0;
for (int i = int(d.size()) - 1; i >= 0; --i) {
uint32_t v = d[i];
d[i] = (v >> part) | carry;
carry = part ? v << (32 - part) : 0;
}
trim();
return *this;
}
uint32_t operator&(uint32_t x) const { return d.empty() ? 0 : d[0] & x; }
static pair<Z, Z> divmod(Z x, Z y) {
assert(y != 0);
if (x < y) return {0, x};
Z q, r;
q.d.resize(x.d.size());
if (y.d.size() == 1) {
uint64_t rem = 0;
for (int i = int(x.d.size()) - 1; i >= 0; --i) {
uint64_t v = (rem << 32) | x.d[i];
q.d[i] = uint32_t(v / y.d[0]);
rem = v % y.d[0];
}
q.trim();
return {q, Z(rem)};
}
int shift = __builtin_clz(y.d.back());
x <<= shift;
y <<= shift;
q.d.assign(x.d.size(), 0);
int m = y.d.size();
for (int i = int(x.d.size()) - 1; i >= 0; --i) {
r.d.insert(r.d.begin(), x.d[i]);
r.trim();
uint64_t top = r.d.size() > size_t(m) ? r.d[m] : 0;
uint64_t next = r.d.size() >= size_t(m) ? r.d[m - 1] : 0;
uint64_t digit = min<uint64_t>(((top << 32) | next) / y.d.back(), UINT32_MAX);
Z product = y * Z(digit);
while (product > r) --digit, product -= y;
r -= product;
q.d[i] = uint32_t(digit);
}
q.trim();
r >>= shift;
return {q, r};
}
friend Z operator/(const Z &x, const Z &y) { return divmod(x, y).first; }
friend Z operator%(const Z &x, const Z &y) { return divmod(x, y).second; }
Z &operator/=(const Z &y) { return *this = *this / y; }
Z &operator%=(const Z &y) { return *this = *this % y; }
};
using Mat = vector<vector<unsigned char>>;
using Garden = vector<vector<pair<bool, int>>>;
struct Node {
int type = 0, sz = 1;
vector<int> common;
vector<int> child;
};
struct Shape {
vector<Node> a;
vector<vector<int>> comps;
explicit Shape(int n = 0) : a(n) {}
};
int prepared_n = -1, prepared_k = -1, pb, sb, fb;
vector<Z> fac, f, a, unit, comp, seq, pref;
array<vector<Z>, 4> path_count;
vector<vector<Z>> binom;
int bits(Z x) {
return x == 0 ? 0 : 32 * int(x.d.size()) - __builtin_clz(x.d.back());
}
// Each side prepares its own tables; no state is shared between executions.
void prepare(int n, int k) {
if (n == prepared_n && k == prepared_k) return;
prepared_n = n;
prepared_k = k;
fac.assign(n + 1, 1);
for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i;
pb = bits(fac[n] - 1);
if (k == 1) {
binom.assign(n + 1, vector<Z>(n + 1));
for (int i = 0; i <= n; ++i) {
binom[i][0] = binom[i][i] = 1;
for (int j = 1; j < i; ++j)
binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
}
f.assign(n + 1, 0);
f[0] = 1;
for (int i = 1; i <= n; ++i) {
f[i] = i * f[i - 1];
for (int m = 3; m <= i; ++m)
f[i] += binom[i][m] * fac[m - 1] * f[i - m];
}
fb = bits(f[n] - 1);
}
if (k == 2) {
a.assign(n + 1, 0);
unit.assign(n + 1, 0);
comp.assign(n + 1, 0);
seq.assign(n + 1, 0);
pref.assign(n + 1, 0);
for (auto &v : path_count) v.assign(n + 1, 0);
auto &p = path_count[0];
seq[0] = p[0] = pref[0] = 1;
for (int i = 1; i <= n; ++i) {
a[i] = p[i - 1] - a[i - 1];
unit[i] = a[i];
if (i >= 2) unit[i] += path_count[1][i - 2];
if (i >= 3) unit[i] += pref[i - 3];
for (int j = 1; j <= i; ++j) p[i] += unit[j] * p[i - j];
path_count[1][i] = p[i];
path_count[2][i] = p[i] - a[i];
path_count[3][i] = path_count[2][i];
for (int j = 1; j < i; ++j) path_count[3][i] -= a[j] * a[i - j];
if (i >= 2) path_count[3][i] -= path_count[1][i - 2];
comp[i] = path_count[3][i] + Z(i == 1);
for (int j = 1; j <= i; ++j) seq[i] += comp[j] * seq[i - j];
pref[i] = pref[i - 1] + p[i];
}
sb = bits(seq[n] - 1);
}
}
void put(string &s, Z x, int len) {
for (int i = 0; i < len; ++i) {
s += static_cast<bool>(x & 1) ? '1' : '0';
x >>= 1;
}
assert(x == 0);
}
Z get(const string &s, int &pos, int len) {
Z x = 0;
for (int i = len - 1; i >= 0; --i) {
x <<= 1;
x += s[pos + i] - '0';
}
pos += len;
return x;
}
Z rank_perm(const vector<int> &p, vector<int> rem) {
Z r = 0;
for (int v : p) {
int d = find(rem.begin(), rem.end(), v) - rem.begin();
assert(d < (int)rem.size());
r = r * rem.size() + d;
rem.erase(rem.begin() + d);
}
return r;
}
vector<int> unrank_perm(Z r, vector<int> rem) {
int n = rem.size();
vector<int> d(n), p;
for (int i = n - 1; i >= 0; --i) {
d[i] = (r % (n - i)).convert_to<int>();
r /= n - i;
}
assert(r == 0);
for (int x : d) {
p.push_back(rem[x]);
rem.erase(rem.begin() + x);
}
return p;
}
// Tarjan emits SCCs in reverse topological order.
vector<vector<int>> components(const Mat &g) {
int n = g.size(), timer = 0;
vector<int> dfn(n), low(n), st;
vector<bool> in(n);
vector<vector<int>> comps;
function<void(int)> dfs = [&](int u) {
dfn[u] = low[u] = ++timer;
st.push_back(u);
in[u] = true;
for (int v = 0; v < n; ++v) if (g[u][v]) {
if (!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
else if (in[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
vector<int> c;
while (true) {
int v = st.back();
st.pop_back();
in[v] = false;
c.push_back(v);
if (v == u) break;
}
comps.push_back(c);
}
};
for (int u = 0; u < n; ++u) if (!dfn[u]) dfs(u);
reverse(comps.begin(), comps.end());
return comps;
}
vector<vector<int>> cycle_components(const Mat &g) {
auto comps = components(g);
for (auto &c : comps) if (c.size() > 1) {
int root = *min_element(c.begin(), c.end()), u = root;
vector<int> order;
do {
order.push_back(u);
int nxt = -1;
for (int v : c) if (g[u][v]) {
assert(nxt == -1);
nxt = v;
}
assert(nxt != -1);
u = nxt;
} while (u != root);
assert(order.size() == c.size());
c = order;
}
return comps;
}
// Rank an ordered sequence of singletons and directed cycles on labeled vertices.
Z rank_cycles(const vector<vector<int>> &comps, int at, vector<int> rem) {
int n = rem.size();
if (!n) return 0;
const auto &c = comps[at];
int m = c.size();
Z r = 0;
for (int z = 1; z < m; ++z) if (z != 2)
r += binom[n][z] * fac[z - 1] * f[n - z];
vector<int> sub = c;
sort(sub.begin(), sub.end());
Z sr = 0;
int last = -1;
for (int i = 0; i < m; ++i) {
int atv = lower_bound(rem.begin(), rem.end(), sub[i]) - rem.begin();
for (int j = last + 1; j < atv; ++j) sr += binom[n - j - 1][m - i - 1];
last = atv;
}
vector<int> tail(c.begin() + 1, c.end());
vector<int> small(sub.begin() + 1, sub.end());
Z cr = rank_perm(tail, small);
vector<int> rest;
set_difference(rem.begin(), rem.end(), sub.begin(), sub.end(), back_inserter(rest));
return r + (sr * fac[m - 1] + cr) * f[n - m] + rank_cycles(comps, at + 1, rest);
}
vector<vector<int>> unrank_cycles(Z r, vector<int> rem) {
vector<vector<int>> comps;
while (!rem.empty()) {
int n = rem.size(), m;
for (m = 1; m <= n; ++m) if (m != 2) {
Z w = binom[n][m] * fac[m - 1] * f[n - m];
if (r < w) break;
r -= w;
}
assert(m <= n);
Z q = r / f[n - m];
r %= f[n - m];
Z sr = q / fac[m - 1], cr = q % fac[m - 1];
vector<int> sub;
int last = -1;
for (int i = 0; i < m; ++i) {
int j = last + 1;
while (sr >= binom[n - j - 1][m - i - 1]) {
sr -= binom[n - j - 1][m - i - 1];
++j;
}
sub.push_back(rem[j]);
last = j;
}
vector<int> small(sub.begin() + 1, sub.end());
vector<int> c = {sub[0]}, tail = unrank_perm(cr, small), rest;
c.insert(c.end(), tail.begin(), tail.end());
comps.push_back(c);
set_difference(rem.begin(), rem.end(), sub.begin(), sub.end(), back_inserter(rest));
rem = rest;
}
return comps;
}
// Johnson's blocked DFS lists each directed cycle once. Only SCC-internal
// edges are used, so there are at most 2n edges and 2n/3 cycles here.
vector<vector<int>> list_cycles(const Mat &g, const vector<int> &vertices) {
int n = g.size();
vector<vector<int>> adj(n), waiting(n), cycles;
for (int u : vertices) for (int v : vertices) if (g[u][v]) adj[u].push_back(v);
vector<bool> blocked(n);
vector<int> stack;
function<void(int)> unblock = [&](int u) {
blocked[u] = false;
auto pending = move(waiting[u]);
waiting[u].clear();
for (int v : pending) if (blocked[v]) unblock(v);
};
function<bool(int, int)> dfs = [&](int u, int start) {
bool found = false;
stack.push_back(u);
blocked[u] = true;
for (int v : adj[u]) if (v >= start) {
if (v == start) {
cycles.push_back(stack);
found = true;
} else if (!blocked[v] && dfs(v, start)) found = true;
}
if (found) unblock(u);
else for (int v : adj[u]) if (v >= start) {
auto &w = waiting[v];
if (find(w.begin(), w.end(), u) == w.end()) w.push_back(u);
}
stack.pop_back();
return found;
};
for (int s : vertices) {
fill(blocked.begin(), blocked.end(), false);
for (auto &w : waiting) w.clear();
dfs(s, s);
}
return cycles;
}
// Two intersecting cycles share one directed path. Their intersection graph
// is a tree. A unit stores the shared path and recursively stores the other
// path of the child cycle; common vertices cannot have further attachments.
Shape extract_shape(const Mat &g) {
int n = g.size();
Shape sh(n);
for (const auto &vertices : components(g)) {
if (vertices.size() == 1) {
sh.comps.push_back(vertices);
continue;
}
auto cycles = list_cycles(g, vertices);
int m = cycles.size();
vector<vector<int>> belong(n), nxt(m, vector<int>(n, -1));
for (int i = 0; i < m; ++i) {
const auto &c = cycles[i];
for (int j = 0; j < (int)c.size(); ++j) {
belong[c[j]].push_back(i);
nxt[i][c[j]] = c[(j + 1) % c.size()];
}
}
vector<vector<vector<int>>> shared(m, vector<vector<int>>(m));
for (int v : vertices) {
assert(!belong[v].empty() && belong[v].size() <= 2);
if (belong[v].size() == 2) {
int x = belong[v][0], y = belong[v][1];
shared[x][y].push_back(v);
}
}
int edges = 0;
for (int x = 0; x < m; ++x) for (int y = x + 1; y < m; ++y)
if (!shared[x][y].empty()) {
++edges;
vector<int> indeg(n);
for (int v : shared[x][y]) if (nxt[x][v] == nxt[y][v]) ++indeg[nxt[x][v]];
int first = -1;
for (int v : shared[x][y]) if (!indeg[v]) assert(first == -1), first = v;
assert(first != -1);
vector<int> p = {first};
while (nxt[x][p.back()] == nxt[y][p.back()]) p.push_back(nxt[x][p.back()]);
assert(p.size() == shared[x][y].size());
shared[x][y] = shared[y][x] = p;
}
assert(edges == m - 1);
vector<bool> seen(m);
function<vector<int>(int, int)> build = [&](int id, int parent) {
assert(!seen[id]);
seen[id] = true;
vector<int> base;
if (parent == -1) {
int first = -1;
for (int v : cycles[id]) {
if (belong[v].size() == 1) { first = v; break; }
int child = belong[v][0] ^ belong[v][1] ^ id;
if (shared[id][child].front() == v) { first = v; break; }
}
assert(first != -1);
int v = first;
do { base.push_back(v); v = nxt[id][v]; } while (v != first);
} else {
const auto &p = shared[id][parent];
for (int v = nxt[id][p.back()]; v != p.front(); v = nxt[id][v]) base.push_back(v);
}
vector<int> path;
for (int i = 0; i < (int)base.size();) {
int u = base[i], child = -1;
if (belong[u].size() == 2) child = belong[u][0] ^ belong[u][1] ^ id;
Node &nd = sh.a[u];
path.push_back(u);
if (child == -1) { ++i; continue; }
assert(child != parent);
const auto &p = shared[id][child];
assert(p.front() == u && i + p.size() <= base.size());
for (int j = 0; j < (int)p.size(); ++j) assert(base[i + j] == p[j]);
nd.type = 1;
nd.common.assign(p.begin() + 1, p.end());
nd.sz = p.size();
nd.child = build(child, id);
for (int v : nd.child) nd.sz += sh.a[v].sz;
i += p.size();
}
return path;
};
sh.comps.push_back(build(0, -1));
for (bool used : seen) assert(used);
}
return sh;
}
int list_size(const Shape &sh, const vector<int> &p, int at = 0) {
int s = 0;
for (int i = at; i < (int)p.size(); ++i) s += sh.a[p[i]].sz;
return s;
}
Z unit_count(int n, int h) {
if (h == 1) return a[n];
return path_count[max(0, 3 - h)][n - h];
}
Z first_count(int n, int m, int need) {
const auto &p = path_count;
if (need <= 1) return unit[m] * p[0][n - m];
if (need == 2) return a[m] * p[1][n - m] + (unit[m] - a[m]) * p[0][n - m];
Z two = m >= 2 ? p[1][m - 2] : Z(0);
return a[m] * p[2][n - m] + two * p[1][n - m]
+ (unit[m] - a[m] - two) * p[0][n - m];
}
// need is the minimum number of vertices on this path itself (0..3),
// excluding vertices in recursively attached cycles.
Z rank_path(const Shape &sh, const vector<int> &p, int need, int at = 0) {
if (at == (int)p.size()) { assert(need == 0); return 0; }
int n = list_size(sh, p, at), u = p[at], m = sh.a[u].sz;
int h = sh.a[u].common.size() + 1;
Z r = 0;
for (int i = 1; i < m; ++i) r += first_count(n, i, need);
for (int j = 1; j < h; ++j)
r += unit_count(m, j) * path_count[max(0, need - j)][n - m];
Z nr = sh.a[u].type == 0 ? Z(0) : rank_path(sh, sh.a[u].child, max(0, 3 - h));
int next_need = max(0, need - h);
return r + nr * path_count[next_need][n - m] + rank_path(sh, p, next_need, at + 1);
}
Z rank_forest(const Shape &sh, int at = 0) {
if (at == (int)sh.comps.size()) return 0;
int n = 0, m = list_size(sh, sh.comps[at]);
for (int i = at; i < (int)sh.comps.size(); ++i) n += list_size(sh, sh.comps[i]);
Z r = 0;
for (int i = 1; i < m; ++i) r += comp[i] * seq[n - i];
Z nr = m == 1 ? Z(0) : rank_path(sh, sh.comps[at], 3);
return r + nr * seq[n - m] + rank_forest(sh, at + 1);
}
vector<int> unrank_path(Shape &sh, int &next, int n, int need, Z r) {
vector<int> p;
while (n) {
int m, h;
for (m = 1; m <= n; ++m) {
Z w = first_count(n, m, need);
if (r < w) break;
r -= w;
}
assert(m <= n);
for (h = 1; h <= m; ++h) {
Z w = unit_count(m, h) * path_count[max(0, need - h)][n - m];
if (r < w) break;
r -= w;
}
assert(h <= m);
need = max(0, need - h);
Z nr = r / path_count[need][n - m];
r %= path_count[need][n - m];
int u = next++;
sh.a[u].sz = m;
for (int j = 1; j < h; ++j) sh.a[u].common.push_back(next++);
if (m != 1 || h != 1) {
sh.a[u].type = 1;
sh.a[u].child = unrank_path(sh, next, m - h, max(0, 3 - h), nr);
} else assert(nr == 0);
p.push_back(u);
n -= m;
}
assert(need == 0 && r == 0);
return p;
}
Shape unrank_forest(int n, Z r) {
Shape sh(n);
int next = 0;
while (n) {
int m;
for (m = 1; m <= n; ++m) {
Z w = comp[m] * seq[n - m];
if (r < w) break;
r -= w;
}
assert(m <= n);
Z nr = r / seq[n - m];
r %= seq[n - m];
if (m == 1) sh.comps.push_back({next++});
else sh.comps.push_back(unrank_path(sh, next, m, 3, nr));
n -= m;
}
assert(next == (int)sh.a.size());
return sh;
}
void preorder(const Shape &sh, int u, vector<int> &p) {
p.push_back(u);
p.insert(p.end(), sh.a[u].common.begin(), sh.a[u].common.end());
for (int v : sh.a[u].child) preorder(sh, v, p);
}
Mat restore_shape(const Shape &sh, const vector<int> &labels) {
int n = labels.size();
Mat h(n, vector<unsigned char>(n));
auto edge = [&](int u, int v) { assert(u != v); h[labels[u]][labels[v]] = 1; };
function<vector<int>(const vector<int>&)> build_path = [&](const vector<int> &p) {
vector<int> base;
for (int u : p) {
vector<int> common = {u};
common.insert(common.end(), sh.a[u].common.begin(), sh.a[u].common.end());
base.insert(base.end(), common.begin(), common.end());
if (sh.a[u].type) {
auto inside = build_path(sh.a[u].child);
vector<int> cycle = common;
cycle.insert(cycle.end(), inside.begin(), inside.end());
assert(cycle.size() >= 3);
for (int i = 0; i < (int)cycle.size(); ++i) edge(cycle[i], cycle[(i + 1) % cycle.size()]);
}
}
return base;
};
vector<int> previous;
for (const auto &c : sh.comps) {
vector<int> cur;
for (int u : c) preorder(sh, u, cur);
for (int u : previous) for (int v : cur) edge(u, v);
auto base = build_path(c);
if (cur.size() > 1) {
assert(base.size() >= 3);
for (int i = 0; i < (int)base.size(); ++i) edge(base[i], base[(i + 1) % base.size()]);
}
previous.insert(previous.end(), cur.begin(), cur.end());
}
return h;
}
Mat restore_cycles(int n, const vector<vector<int>> &comps) {
Mat h(n, vector<unsigned char>(n));
vector<int> previous;
for (const auto &c : comps) {
for (int u : previous) for (int v : c) h[u][v] = 1;
if (c.size() > 1)
for (int i = 0; i < (int)c.size(); ++i) h[c[i]][c[(i + 1) % c.size()]] = 1;
previous.insert(previous.end(), c.begin(), c.end());
}
return h;
}
} // namespace
int init(int n, int k) {
prepare(n, k);
return 3 * (k == 0 ? pb : k == 1 ? fb : pb + sb);
}
std::string send_message(int n, int k, Garden e) {
prepare(n, k);
vector<int> all(n);
iota(all.begin(), all.end(), 0);
string s;
for (int col = 0; col < 3; ++col) {
Mat g(n, vector<unsigned char>(n));
for (int u = 0; u < n; ++u) for (int v = u + 1; v < n; ++v) {
auto [dir, color] = e[u][v - u - 1];
if (color != col) g[dir ? u : v][dir ? v : u] = 1;
}
if (k == 0) {
auto comps = components(g);
vector<int> p;
for (const auto &c : comps) assert(c.size() == 1), p.push_back(c[0]);
put(s, rank_perm(p, all), pb);
} else if (k == 1) {
put(s, rank_cycles(cycle_components(g), 0, all), fb);
} else {
Shape sh = extract_shape(g);
vector<int> p;
for (const auto &c : sh.comps) for (int u : c) preorder(sh, u, p);
assert((int)p.size() == n);
put(s, rank_perm(p, all), pb);
put(s, rank_forest(sh), sb);
}
}
return s;
}
Garden build_flower_garden(int n, int k, std::string s) {
prepare(n, k);
vector<int> all(n);
iota(all.begin(), all.end(), 0);
array<Mat, 3> h;
int pos = 0;
for (int col = 0; col < 3; ++col) {
if (k == 0) {
auto p = unrank_perm(get(s, pos, pb), all);
vector<vector<int>> comps;
for (int u : p) comps.push_back({u});
h[col] = restore_cycles(n, comps);
} else if (k == 1) {
h[col] = restore_cycles(n, unrank_cycles(get(s, pos, fb), all));
} else {
auto p = unrank_perm(get(s, pos, pb), all);
Shape sh = unrank_forest(n, get(s, pos, sb));
h[col] = restore_shape(sh, p);
}
}
Garden e(n - 1);
for (int u = 0; u < n; ++u) for (int v = u + 1; v < n; ++v) {
int votes = h[0][u][v] + h[1][u][v] + h[2][u][v];
bool dir = votes >= 2;
int x = dir ? u : v, y = dir ? v : u, color = 0;
assert(h[0][x][y] + h[1][x][y] + h[2][x][y] >= 2);
for (int c = 0; c < 3; ++c) if (!h[c][x][y]) color = c;
e[u].emplace_back(dir, color);
}
return e;
}