File size: 6,076 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 | #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int L, R;
cin >> L >> R;
// Build ADFA recognizing binary representations of [L,R]
// Then minimize by merging nodes with identical subtrees (right languages)
struct Edge { int to, w; };
// Phase 1: Build all nodes
vector<vector<Edge>> adj;
int n = 0;
auto nn = [&]() -> int { adj.emplace_back(); return n++; };
int END = nn(); // 0
int START = nn(); // 1
// Free chain: free[k] accepts any k-bit suffix
map<int,int> fc;
fc[0] = END;
function<int(int)> getF = [&](int k) -> int {
if (fc.count(k)) return fc[k];
int ch = getF(k-1), u = nn();
adj[u].push_back({ch, 0});
adj[u].push_back({ch, 1});
return fc[k] = u;
};
// Range nodes: gr(k, lo, hi) accepts k-bit suffixes in [lo, hi]
map<tuple<int,int,int>,int> rc;
function<int(int,int,int)> gr = [&](int k, int lo, int hi) -> int {
if (lo > hi) return -1;
if (k == 0) return (lo == 0 && hi == 0) ? END : -1;
if (lo == 0 && hi == (1<<k)-1) return getF(k);
auto key = make_tuple(k, lo, hi);
auto it = rc.find(key);
if (it != rc.end()) return it->second;
int mid = 1 << (k-1);
int left = -1, right = -1;
if (lo <= min(hi, mid-1))
left = gr(k-1, lo, min(hi, mid-1));
if (max(lo, mid) <= hi)
right = gr(k-1, max(lo, mid) - mid, hi - mid);
if (left == -1 && right == -1) return rc[key] = -1;
int u = nn();
if (left != -1) adj[u].push_back({left, 0});
if (right != -1) adj[u].push_back({right, 1});
return rc[key] = u;
};
int lenL = 32 - __builtin_clz(L), lenR = 32 - __builtin_clz(R);
for (int len = lenL; len <= lenR; len++) {
int rs = 1 << (len-1), re = (1<<len)-1;
int cL = max(L, rs), cR = min(R, re);
if (cL > cR) continue;
int target;
if (len == 1) target = END;
else target = gr(len-1, cL - rs, cR - rs);
if (target != -1)
adj[START].push_back({target, 1});
}
// Phase 2: Compute reachability from START
vector<bool> reach(n, false);
{
queue<int> q;
q.push(START);
reach[START] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (auto& e : adj[u]) {
if (!reach[e.to]) {
reach[e.to] = true;
q.push(e.to);
}
}
}
}
// Phase 3: ADFA minimization - merge nodes with identical subtrees
// Compute signature for each node bottom-up (topological order)
// Signature = sorted list of (child_signature, weight) pairs
// Compute topological order (reverse BFS from END, or compute in-degrees)
// Actually, let's use the fact that this is a layered DAG.
// We'll compute signatures bottom-up.
// First, compute depth of each node (longest path from node to END)
vector<int> depth(n, -1);
depth[END] = 0;
// BFS in reverse topological order
// Let's compute topological order first
vector<int> indeg(n, 0);
for (int u = 0; u < n; u++) {
if (!reach[u]) continue;
for (auto& e : adj[u]) {
indeg[e.to]++;
}
}
vector<int> topo;
queue<int> q;
for (int u = 0; u < n; u++) {
if (reach[u] && indeg[u] == 0) q.push(u);
}
while (!q.empty()) {
int u = q.front(); q.pop();
topo.push_back(u);
for (auto& e : adj[u]) {
if (--indeg[e.to] == 0) q.push(e.to);
}
}
// Reverse topological order for bottom-up processing
reverse(topo.begin(), topo.end());
// Compute canonical signature for each node
// Map signature -> representative node
map<vector<pair<int,int>>, int> sig_to_rep; // signature -> representative
vector<int> node_rep(n, -1); // node -> its representative
for (int u : topo) {
if (!reach[u]) continue;
// Build signature using representative IDs of children
vector<pair<int,int>> sig;
for (auto& e : adj[u]) {
sig.push_back({node_rep[e.to], e.w});
}
sort(sig.begin(), sig.end());
auto it = sig_to_rep.find(sig);
if (it != sig_to_rep.end()) {
node_rep[u] = it->second;
} else {
node_rep[u] = u;
sig_to_rep[sig] = u;
}
}
// But wait - START must remain START (can't merge with anything else due to its role)
// And END must remain END.
// Actually, the merging is fine as long as we track which nodes survive.
// However, there's a subtlety: we can't merge START with anything because it's the
// unique in-degree-0 node. Similarly END is the unique out-degree-0 node.
// The signature-based merging handles this naturally if signatures are truly identical.
// Collect unique representative nodes
set<int> reps;
for (int u : topo) {
if (reach[u]) reps.insert(node_rep[u]);
}
// Assign new IDs. START must be first.
map<int, int> new_id;
int cnt = 0;
new_id[node_rep[START]] = ++cnt;
for (int r : reps) {
if (r != node_rep[START]) {
new_id[r] = ++cnt;
}
}
// Build output adjacency
vector<vector<pair<int,int>>> out_adj(cnt + 1);
for (int r : reps) {
int id = new_id[r];
for (auto& e : adj[r]) {
int child_rep = node_rep[e.to];
out_adj[id].push_back({new_id[child_rep], e.w});
}
// Deduplicate edges
sort(out_adj[id].begin(), out_adj[id].end());
out_adj[id].erase(unique(out_adj[id].begin(), out_adj[id].end()), out_adj[id].end());
}
cout << cnt << "\n";
for (int i = 1; i <= cnt; i++) {
cout << out_adj[i].size();
for (auto& [to, w] : out_adj[i]) {
cout << " " << to << " " << w;
}
cout << "\n";
}
return 0;
}
|