Problem 673: Beds and Desks
View on Project EulerProject Euler Problem 673 Solution
EulerSolve provides an optimized solution for Project Euler Problem 673, Beds and Desks, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary We are given \(n\) people together with two pairing rules: one for beds and one for desks. Each rule is an involution, so every person is either paired with exactly one other person or left fixed by that rule. The task is to count, modulo $$P=999{,}999{,}937,$$ how many relabelings of the people preserve both structures simultaneously. Mathematical Approach The solution treats the data as a finite colored graph built from two involutions, then counts its structure-preserving permutations by decomposing the graph into connected components and grouping isomorphic components together. Step 1: Model the Two Pairings as Involutions Let \(V=\{1,2,\dots,n\}\). Write the bed relation as \(\beta:V\to V\) and the desk relation as \(\delta:V\to V\). Because each relation is an involution, we have $$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i \qquad \text{for every } i\in V.$$ A relabeling is a permutation \(\pi\) of \(V\). It is valid exactly when it preserves both relations, which means $$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)) \qquad \text{for every } i\in V.$$ So the problem is to count all permutations that commute with both involutions. Step 2: Turn the Data into a Two-Colored Graph Connect each vertex \(i\) to \(\beta(i)\) by a bed edge and to \(\delta(i)\) by a desk edge. Fixed points are allowed, so a vertex can carry a loop of one color....
Detailed mathematical approach
Problem Summary
We are given \(n\) people together with two pairing rules: one for beds and one for desks. Each rule is an involution, so every person is either paired with exactly one other person or left fixed by that rule. The task is to count, modulo
$$P=999{,}999{,}937,$$
how many relabelings of the people preserve both structures simultaneously.
Mathematical Approach
The solution treats the data as a finite colored graph built from two involutions, then counts its structure-preserving permutations by decomposing the graph into connected components and grouping isomorphic components together.
Step 1: Model the Two Pairings as Involutions
Let \(V=\{1,2,\dots,n\}\). Write the bed relation as \(\beta:V\to V\) and the desk relation as \(\delta:V\to V\). Because each relation is an involution, we have
$$\beta(\beta(i))=i,\qquad \delta(\delta(i))=i \qquad \text{for every } i\in V.$$
A relabeling is a permutation \(\pi\) of \(V\). It is valid exactly when it preserves both relations, which means
$$\pi(\beta(i))=\beta(\pi(i)),\qquad \pi(\delta(i))=\delta(\pi(i)) \qquad \text{for every } i\in V.$$
So the problem is to count all permutations that commute with both involutions.
Step 2: Turn the Data into a Two-Colored Graph
Connect each vertex \(i\) to \(\beta(i)\) by a bed edge and to \(\delta(i)\) by a desk edge. Fixed points are allowed, so a vertex can carry a loop of one color. Every vertex therefore has exactly one incident bed edge and exactly one incident desk edge, counting loops.
Now split this colored graph into connected components. If a permutation preserves both colored edge relations, it must send each connected component to another connected component with exactly the same colored structure. Therefore the global counting problem breaks into independent pieces indexed by component isomorphism classes.
Step 3: Count Isomorphisms by Choosing One Root Image
Take one component \(C\) of size \(m\) and relabel its vertices locally as \(0,1,\dots,m-1\). Record two local partner tables: one table gives the bed partner of each local index, and the other gives the desk partner. This removes the original labels and keeps only the structure.
If \(f:C\to C'\) is a color-preserving bijection between two components, then it must satisfy
$$f(p_C(x))=p_{C'}(f(x)),\qquad f(q_C(x))=q_{C'}(f(x))$$
for every local vertex \(x\), where \(p_C\) and \(q_C\) denote the local bed and desk partner tables. Because the component is connected and each vertex has exactly one neighbor of each color, once the image of one starting vertex is chosen, these equations force the image of every reachable vertex. Either the propagation stays consistent and yields one isomorphism, or it produces a contradiction and fails.
A necessary first check is that the chosen starting vertices have the same loop pattern:
$$p_C(r)=r \iff p_{C'}(s)=s,\qquad q_C(r)=r \iff q_{C'}(s)=s.$$
Trying all possible starting images \(s\) therefore counts all isomorphisms from \(C\) to \(C'\).
Step 4: Automorphisms Determine All Isomorphism Counts Inside One Class
For a component \(C\), let
$$a(C)=\left|\operatorname{Aut}(C)\right|,$$
the number of color-preserving automorphisms of \(C\). This is exactly the number obtained when the implementation compares a component with itself.
If \(C\) and \(C'\) are isomorphic, then the number of isomorphisms \(C\to C'\) is also \(a(C)\). The reason is simple: choose one fixed isomorphism \(\varphi:C\to C'\). Then every other isomorphism \(C\to C'\) is uniquely of the form \(\varphi\circ \sigma\) with \(\sigma\in \operatorname{Aut}(C)\).
Step 5: Multiply the Contributions of Repeated Component Types
Suppose an isomorphism class appears \(m_j\) times, and let \(a_j\) be the automorphism count of one representative component in that class. A valid global permutation can first permute those \(m_j\) copies among themselves in
$$m_j!$$
ways. After the target copy of each source component is chosen, there are
$$a_j$$
color-preserving bijections for that source-to-target move. Since this choice is made independently for all \(m_j\) copies, the class contributes
$$a_j^{m_j}\cdot m_j!.$$
If the graph has isomorphism classes \(\mathcal{C}_1,\dots,\mathcal{C}_t\), the final formula is
$$\boxed{N=\prod_{j=1}^{t} a_j^{m_j}\cdot m_j! \pmod{P}.}$$
Worked Example
Consider \(n=4\), with bed pairing \(2\leftrightarrow 3\) and desk pairings \(1\leftrightarrow 3\), \(2\leftrightarrow 4\). The bed relation fixes \(1\) and \(4\), so those two vertices carry bed loops. The whole structure is one connected component, and its colored shape is an alternating path
$$1 \overset{\delta}{\leftrightarrow} 3 \overset{\beta}{\leftrightarrow} 2 \overset{\delta}{\leftrightarrow} 4$$
with bed loops at the two ends. There are exactly two automorphisms: the identity, and the reversal that swaps the two ends and the two middle vertices while preserving edge colors. Hence the answer is
$$2,$$
which matches the implementation checkpoint for this small case.
How the Code Works
The C++, Python, and Java implementations begin by storing both involutions as tables on \(1,\dots,n\), with fixed points filled in automatically for any person not listed in a pair. They then traverse the graph with an explicit stack, following both colored relations, to extract every connected component.
Each component is relabeled locally so that it can be compared without referring to the original global labels. To compare two components, the implementation tries every possible image of the first local vertex whose loop pattern matches. For each candidate, it propagates the bed and desk constraints through the entire component. A contradiction rejects that candidate; a complete consistent propagation counts as one isomorphism.
After grouping components into isomorphism classes, the implementation computes the modular product
$$a_j^{m_j}\cdot m_j! \pmod{P}$$
for every class, using fast modular exponentiation for the power term and ordinary modular multiplication for the factorial term. No search over all \(n!\) permutations is ever attempted.
Complexity Analysis
Building the two involution tables and extracting all connected components costs \(O(n)\) time and \(O(n)\) memory. If two components have size \(s\), then testing isomorphism between them tries up to \(s\) starting images, and each successful or failed propagation touches at most \(s\) local vertices, so one comparison is \(O(s^2)\) in the worst case.
If the component sizes are \(s_1,\dots,s_r\), the grouping stage is therefore bounded by the pairwise same-size comparisons performed by the simple implementation; for the actual \(n=500\) instance this is easily fast enough. The overall memory use remains linear in \(n\).
Footnotes and References
- Problem page: Project Euler 673 - Beds and Desks
- Involution: Wikipedia - Involution (mathematics)
- Connected component: Wikipedia - Connected component
- Graph automorphism: Wikipedia - Graph automorphism
- Graph isomorphism: Wikipedia - Graph isomorphism
- Wreath product: Wikipedia - Wreath product
Problem 673 source code
C++
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
namespace {
using i64 = std::int64_t;
constexpr i64 MOD = 999'999'937LL;
struct Comp {
std::vector<int> b;
std::vector<int> d;
};
i64 mod_pow(i64 a, int e) {
i64 r = 1;
i64 x = a % MOD;
int p = e;
while (p > 0) {
if ((p & 1) != 0) {
r = static_cast<i64>((static_cast<__int128>(r) * x) % MOD);
}
p >>= 1;
if (p > 0) {
x = static_cast<i64>((static_cast<__int128>(x) * x) % MOD);
}
}
return r;
}
std::vector<std::pair<int, int>> parse_pairs(const std::string& data) {
std::vector<std::pair<int, int>> out;
std::istringstream in(data);
std::string line;
while (std::getline(in, line)) {
if (line.empty()) {
continue;
}
const std::size_t pos = line.find(',');
assert(pos != std::string::npos);
const int a = std::stoi(line.substr(0, pos));
const int b = std::stoi(line.substr(pos + 1));
out.push_back({a, b});
}
return out;
}
std::vector<Comp> build_components(int n, const std::vector<std::pair<int, int>>& beds,
const std::vector<std::pair<int, int>>& desks) {
std::vector<int> b(static_cast<std::size_t>(n + 1));
std::vector<int> d(static_cast<std::size_t>(n + 1));
for (int i = 1; i <= n; ++i) {
b[static_cast<std::size_t>(i)] = i;
d[static_cast<std::size_t>(i)] = i;
}
for (const auto& p : beds) {
b[static_cast<std::size_t>(p.first)] = p.second;
b[static_cast<std::size_t>(p.second)] = p.first;
}
for (const auto& p : desks) {
d[static_cast<std::size_t>(p.first)] = p.second;
d[static_cast<std::size_t>(p.second)] = p.first;
}
std::vector<char> seen(static_cast<std::size_t>(n + 1), 0);
std::vector<int> loc(static_cast<std::size_t>(n + 1), -1);
std::vector<Comp> comps;
for (int s = 1; s <= n; ++s) {
if (seen[static_cast<std::size_t>(s)] != 0) {
continue;
}
std::vector<int> stack{s};
seen[static_cast<std::size_t>(s)] = 1;
std::vector<int> verts;
while (!stack.empty()) {
const int v = stack.back();
stack.pop_back();
verts.push_back(v);
const int nb = b[static_cast<std::size_t>(v)];
const int nd = d[static_cast<std::size_t>(v)];
if (seen[static_cast<std::size_t>(nb)] == 0) {
seen[static_cast<std::size_t>(nb)] = 1;
stack.push_back(nb);
}
if (seen[static_cast<std::size_t>(nd)] == 0) {
seen[static_cast<std::size_t>(nd)] = 1;
stack.push_back(nd);
}
}
for (int i = 0; i < static_cast<int>(verts.size()); ++i) {
loc[static_cast<std::size_t>(verts[static_cast<std::size_t>(i)])] = i;
}
Comp c;
c.b.resize(verts.size());
c.d.resize(verts.size());
for (int i = 0; i < static_cast<int>(verts.size()); ++i) {
const int v = verts[static_cast<std::size_t>(i)];
c.b[static_cast<std::size_t>(i)] =
loc[static_cast<std::size_t>(b[static_cast<std::size_t>(v)])];
c.d[static_cast<std::size_t>(i)] =
loc[static_cast<std::size_t>(d[static_cast<std::size_t>(v)])];
}
for (int v : verts) {
loc[static_cast<std::size_t>(v)] = -1;
}
comps.push_back(std::move(c));
}
return comps;
}
bool try_map_root(const Comp& a, const Comp& b, int start_b) {
const int m = static_cast<int>(a.b.size());
std::vector<int> map_a(static_cast<std::size_t>(m), -1);
std::vector<int> map_b(static_cast<std::size_t>(m), -1);
std::vector<int> stack;
stack.reserve(static_cast<std::size_t>(m));
map_a[0] = start_b;
map_b[static_cast<std::size_t>(start_b)] = 0;
stack.push_back(0);
int assigned = 1;
auto step = [&](int nx, int ny) -> bool {
const int cur = map_a[static_cast<std::size_t>(nx)];
if (cur == -1) {
if (map_b[static_cast<std::size_t>(ny)] != -1) {
return false;
}
map_a[static_cast<std::size_t>(nx)] = ny;
map_b[static_cast<std::size_t>(ny)] = nx;
stack.push_back(nx);
++assigned;
return true;
}
return cur == ny;
};
while (!stack.empty()) {
const int x = stack.back();
stack.pop_back();
const int y = map_a[static_cast<std::size_t>(x)];
const int nx_b = a.b[static_cast<std::size_t>(x)];
const int ny_b = b.b[static_cast<std::size_t>(y)];
if (!step(nx_b, ny_b)) {
return false;
}
const int nx_d = a.d[static_cast<std::size_t>(x)];
const int ny_d = b.d[static_cast<std::size_t>(y)];
if (!step(nx_d, ny_d)) {
return false;
}
}
return assigned == m;
}
int isomorphism_count(const Comp& a, const Comp& b) {
if (a.b.size() != b.b.size()) {
return 0;
}
const int m = static_cast<int>(b.b.size());
int count = 0;
for (int s = 0; s < m; ++s) {
if ((a.b[0] == 0) != (b.b[static_cast<std::size_t>(s)] == s)) {
continue;
}
if ((a.d[0] == 0) != (b.d[static_cast<std::size_t>(s)] == s)) {
continue;
}
if (try_map_root(a, b, s)) {
++count;
}
}
return count;
}
i64 count_valid_permutations(int n, const std::vector<std::pair<int, int>>& beds,
const std::vector<std::pair<int, int>>& desks) {
const std::vector<Comp> comps = build_components(n, beds, desks);
const int c = static_cast<int>(comps.size());
std::vector<char> used(static_cast<std::size_t>(c), 0);
i64 ans = 1;
for (int i = 0; i < c; ++i) {
if (used[static_cast<std::size_t>(i)] != 0) {
continue;
}
used[static_cast<std::size_t>(i)] = 1;
const int aut = isomorphism_count(comps[static_cast<std::size_t>(i)],
comps[static_cast<std::size_t>(i)]);
assert(aut > 0);
int mult = 1;
for (int j = i + 1; j < c; ++j) {
if (used[static_cast<std::size_t>(j)] != 0) {
continue;
}
if (isomorphism_count(comps[static_cast<std::size_t>(i)],
comps[static_cast<std::size_t>(j)]) > 0) {
used[static_cast<std::size_t>(j)] = 1;
++mult;
}
}
i64 fac = 1;
for (int t = 2; t <= mult; ++t) {
fac = static_cast<i64>((static_cast<__int128>(fac) * t) % MOD);
}
ans = static_cast<i64>((static_cast<__int128>(ans) * mod_pow(aut, mult)) % MOD);
ans = static_cast<i64>((static_cast<__int128>(ans) * fac) % MOD);
}
return ans;
}
const std::string kBeds500 = R"BED(1,352
2,251
3,243
4,311
5,312
6,231
7,416
8,166
9,384
10,330
11,89
12,316
13,394
14,57
15,177
16,341
17,149
18,199
19,310
20,421
21,459
22,189
23,308
25,46
26,460
27,63
28,34
29,295
30,412
31,49
32,247
33,326
35,429
36,211
37,104
38,376
39,263
40,187
41,500
42,161
43,407
44,60
45,118
47,85
48,56
50,403
51,239
52,415
53,444
54,246
55,288
58,410
59,432
61,160
62,438
65,225
67,392
68,333
69,478
70,365
71,213
72,294
73,360
74,499
75,267
76,493
77,108
78,428
79,440
80,116
81,117
82,257
83,306
84,195
86,216
87,226
88,151
90,172
91,355
93,237
94,156
95,147
96,343
97,424
98,112
100,240
101,163
102,371
103,361
106,315
107,230
109,227
110,336
111,377
113,253
114,367
115,139
119,290
120,121
122,174
123,159
124,282
125,142
126,435
127,452
128,338
129,445
130,448
131,183
132,179
133,196
134,268
135,170
136,357
137,368
138,242
141,400
143,278
144,208
145,204
146,378
148,252
152,238
153,380
154,269
155,270
157,373
158,339
162,272
164,332
167,466
168,327
169,266
173,471
175,494
176,463
178,433
180,198
181,258
182,464
184,467
186,409
188,191
190,346
192,446
193,418
197,474
200,354
201,479
202,436
205,404
206,475
207,349
210,476
212,372
214,379
217,232
218,320
219,366
220,356
221,299
222,426
223,484
224,264
228,359
229,405
233,483
234,391
235,381
236,262
241,420
244,393
245,337
248,296
249,370
250,325
254,351
255,302
256,364
260,431
261,447
265,318
271,397
273,375
274,469
275,453
276,328
279,313
280,292
283,434
284,495
285,386
286,454
287,385
289,363
291,304
293,382
297,389
298,383
301,461
303,347
305,369
309,439
314,344
317,491
319,443
321,470
322,437
323,411
324,406
331,340
334,358
335,456
342,414
345,396
350,390
374,408
387,422
395,487
398,423
399,485
401,441
402,473
413,457
417,449
425,451
427,477
430,496
442,488
450,480
462,490
465,482
472,492
481,486
497,498
)BED";
const std::string kDesks500 = R"DESK(1,106
2,429
4,94
6,349
7,362
8,100
9,368
10,477
11,132
12,328
13,319
14,185
15,225
16,279
17,72
18,51
19,482
20,270
21,50
22,449
23,398
24,492
25,478
26,360
27,428
28,240
29,103
30,32
31,484
33,296
34,371
35,251
36,444
37,460
38,491
39,180
40,264
41,81
42,67
43,472
44,173
45,209
46,135
47,218
48,69
49,137
52,324
54,210
55,330
56,316
57,436
58,212
59,193
61,233
62,211
63,158
64,439
65,419
66,455
70,153
71,198
73,283
74,76
75,250
77,418
78,191
79,144
80,352
82,195
85,192
86,329
87,340
88,306
89,181
90,299
91,383
92,358
93,276
95,119
96,176
97,129
98,235
99,487
101,336
102,332
104,183
105,281
107,432
109,273
110,416
111,304
112,465
113,385
114,167
115,497
116,399
117,404
118,384
121,450
122,247
124,486
125,402
127,344
130,175
131,310
133,149
134,147
136,289
138,453
139,184
140,351
141,256
142,422
143,440
145,481
146,201
148,293
150,231
151,170
152,223
154,314
155,395
156,249
157,414
159,341
160,446
161,410
162,286
163,166
164,307
165,242
168,282
172,234
174,224
177,320
178,258
179,433
182,461
186,257
187,312
188,339
189,388
190,373
194,325
196,322
197,427
200,483
202,357
204,268
205,206
207,285
208,244
213,425
214,294
215,354
216,420
217,382
219,297
220,378
222,400
226,323
229,337
230,499
237,437
238,408
239,489
241,405
243,389
245,392
246,361
248,364
252,424
253,454
254,374
255,301
259,292
260,409
261,347
262,280
263,451
265,381
266,379
267,355
271,456
272,369
274,298
275,431
277,412
278,473
284,490
287,494
288,413
290,343
291,396
295,348
300,315
302,464
303,345
305,468
308,480
309,448
311,331
313,463
317,495
318,367
321,438
327,366
334,426
338,466
342,346
350,445
353,471
356,447
363,476
365,415
370,442
372,458
375,434
376,462
377,423
380,406
386,469
387,459
390,498
391,479
394,496
397,485
401,457
403,474
407,470
411,452
417,443
421,430
435,475
467,493
488,500
)DESK";
} // namespace
int main() {
assert(count_valid_permutations(4, {{2, 3}}, {{1, 3}, {2, 4}}) == 2LL);
assert(count_valid_permutations(6, {{1, 2}, {3, 4}, {5, 6}},
{{3, 6}, {4, 5}}) == 8LL);
const std::vector<std::pair<int, int>> beds36{
{2, 13}, {4, 30}, {5, 27}, {6, 16}, {10, 18}, {12, 35}, {14, 19},
{15, 20}, {17, 26}, {21, 32}, {22, 33}, {24, 34}, {25, 28},
};
const std::vector<std::pair<int, int>> desks36{
{1, 35}, {2, 22}, {3, 36}, {4, 28}, {5, 25}, {7, 18}, {9, 23},
{13, 19}, {14, 33}, {15, 34}, {20, 24}, {26, 29}, {27, 30},
};
assert(count_valid_permutations(36, beds36, desks36) == 663'552LL);
const std::vector<std::pair<int, int>> beds500 = parse_pairs(kBeds500);
const std::vector<std::pair<int, int>> desks500 = parse_pairs(kDesks500);
assert(beds500.size() == 235);
assert(desks500.size() == 236);
std::cout << count_valid_permutations(500, beds500, desks500) << "\n";
return 0;
}
Python
MOD = 999999937
class Comp:
def __init__(self, b, d):
self.b = b
self.d = d
def parse_pairs(data):
out = []
for line in data.strip().split('\n'):
if not line: continue
parts = line.split(',')
out.append((int(parts[0]), int(parts[1])))
return out
def build_components(n, beds, desks):
b = list(range(n + 1))
d = list(range(n + 1))
for u, v in beds:
b[u] = v
b[v] = u
for u, v in desks:
d[u] = v
d[v] = u
seen = [0] * (n + 1)
loc = [-1] * (n + 1)
comps = []
for s in range(1, n + 1):
if seen[s]: continue
stack = [s]
seen[s] = 1
verts = []
while stack:
v = stack.pop()
verts.append(v)
nb = b[v]
nd = d[v]
if not seen[nb]:
seen[nb] = 1
stack.append(nb)
if not seen[nd]:
seen[nd] = 1
stack.append(nd)
for i, v in enumerate(verts):
loc[v] = i
cb = [0] * len(verts)
cd = [0] * len(verts)
for i, v in enumerate(verts):
cb[i] = loc[b[v]]
cd[i] = loc[d[v]]
for v in verts:
loc[v] = -1
comps.append(Comp(cb, cd))
return comps
def try_map_root(a, b, start_b):
m = len(a.b)
map_a = [-1] * m
map_b = [-1] * m
stack = []
map_a[0] = start_b
map_b[start_b] = 0
stack.append(0)
assigned = 1
def step(nx, ny):
nonlocal assigned
cur = map_a[nx]
if cur == -1:
if map_b[ny] != -1:
return False
map_a[nx] = ny
map_b[ny] = nx
stack.append(nx)
assigned += 1
return True
return cur == ny
while stack:
x = stack.pop()
y = map_a[x]
nx_b = a.b[x]
ny_b = b.b[y]
if not step(nx_b, ny_b): return False
nx_d = a.d[x]
ny_d = b.d[y]
if not step(nx_d, ny_d): return False
return assigned == m
def isomorphism_count(a, b):
if len(a.b) != len(b.b):
return 0
m = len(b.b)
count = 0
for s in range(m):
if (a.b[0] == 0) != (b.b[s] == s):
continue
if (a.d[0] == 0) != (b.d[s] == s):
continue
if try_map_root(a, b, s):
count += 1
return count
def count_valid_permutations(n, beds, desks):
comps = build_components(n, beds, desks)
c = len(comps)
used = [0] * c
ans = 1
for i in range(c):
if used[i]: continue
used[i] = 1
aut = isomorphism_count(comps[i], comps[i])
mult = 1
for j in range(i + 1, c):
if used[j]: continue
if isomorphism_count(comps[i], comps[j]) > 0:
used[j] = 1
mult += 1
fac = 1
for t in range(2, mult + 1):
fac = (fac * t) % MOD
ans = (ans * pow(aut, mult, MOD)) % MOD
ans = (ans * fac) % MOD
return ans
BEDS_500 = """1,352
2,251
3,243
4,311
5,312
6,231
7,416
8,166
9,384
10,330
11,89
12,316
13,394
14,57
15,177
16,341
17,149
18,199
19,310
20,421
21,459
22,189
23,308
25,46
26,460
27,63
28,34
29,295
30,412
31,49
32,247
33,326
35,429
36,211
37,104
38,376
39,263
40,187
41,500
42,161
43,407
44,60
45,118
47,85
48,56
50,403
51,239
52,415
53,444
54,246
55,288
58,410
59,432
61,160
62,438
65,225
67,392
68,333
69,478
70,365
71,213
72,294
73,360
74,499
75,267
76,493
77,108
78,428
79,440
80,116
81,117
82,257
83,306
84,195
86,216
87,226
88,151
90,172
91,355
93,237
94,156
95,147
96,343
97,424
98,112
100,240
101,163
102,371
103,361
106,315
107,230
109,227
110,336
111,377
113,253
114,367
115,139
119,290
120,121
122,174
123,159
124,282
125,142
126,435
127,452
128,338
129,445
130,448
131,183
132,179
133,196
134,268
135,170
136,357
137,368
138,242
141,400
143,278
144,208
145,204
146,378
148,252
152,238
153,380
154,269
155,270
157,373
158,339
162,272
164,332
167,466
168,327
169,266
173,471
175,494
176,463
178,433
180,198
181,258
182,464
184,467
186,409
188,191
190,346
192,446
193,418
197,474
200,354
201,479
202,436
205,404
206,475
207,349
210,476
212,372
214,379
217,232
218,320
219,366
220,356
221,299
222,426
223,484
224,264
228,359
229,405
233,483
234,391
235,381
236,262
241,420
244,393
245,337
248,296
249,370
250,325
254,351
255,302
256,364
260,431
261,447
265,318
271,397
273,375
274,469
275,453
276,328
279,313
280,292
283,434
284,495
285,386
286,454
287,385
289,363
291,304
293,382
297,389
298,383
301,461
303,347
305,369
309,439
314,344
317,491
319,443
321,470
322,437
323,411
324,406
331,340
334,358
335,456
342,414
345,396
350,390
374,408
387,422
395,487
398,423
399,485
401,441
402,473
413,457
417,449
425,451
427,477
430,496
442,488
450,480
462,490
465,482
472,492
481,486
497,498"""
DESKS_500 = """1,106
2,429
4,94
6,349
7,362
8,100
9,368
10,477
11,132
12,328
13,319
14,185
15,225
16,279
17,72
18,51
19,482
20,270
21,50
22,449
23,398
24,492
25,478
26,360
27,428
28,240
29,103
30,32
31,484
33,296
34,371
35,251
36,444
37,460
38,491
39,180
40,264
41,81
42,67
43,472
44,173
45,209
46,135
47,218
48,69
49,137
52,324
54,210
55,330
56,316
57,436
58,212
59,193
61,233
62,211
63,158
64,439
65,419
66,455
70,153
71,198
73,283
74,76
75,250
77,418
78,191
79,144
80,352
82,195
85,192
86,329
87,340
88,306
89,181
90,299
91,383
92,358
93,276
95,119
96,176
97,129
98,235
99,487
101,336
102,332
104,183
105,281
107,432
109,273
110,416
111,304
112,465
113,385
114,167
115,497
116,399
117,404
118,384
121,450
122,247
124,486
125,402
127,344
130,175
131,310
133,149
134,147
136,289
138,453
139,184
140,351
141,256
142,422
143,440
145,481
146,201
148,293
150,231
151,170
152,223
154,314
155,395
156,249
157,414
159,341
160,446
161,410
162,286
163,166
164,307
165,242
168,282
172,234
174,224
177,320
178,258
179,433
182,461
186,257
187,312
188,339
189,388
190,373
194,325
196,322
197,427
200,483
202,357
204,268
205,206
207,285
208,244
213,425
214,294
215,354
216,420
217,382
219,297
220,378
222,400
226,323
229,337
230,499
237,437
238,408
239,489
241,405
243,389
245,392
246,361
248,364
252,424
253,454
254,374
255,301
259,292
260,409
261,347
262,280
263,451
265,381
266,379
267,355
271,456
272,369
274,298
275,431
277,412
278,473
284,490
287,494
288,413
290,343
291,396
295,348
300,315
302,464
303,345
305,468
308,480
309,448
311,331
313,463
317,495
318,367
321,438
327,366
334,426
338,466
342,346
350,445
353,471
356,447
363,476
365,415
370,442
372,458
375,434
376,462
377,423
380,406
386,469
387,459
390,498
391,479
394,496
397,485
401,457
403,474
407,470
411,452
417,443
421,430
435,475
467,493
488,500"""
def solve():
b_pairs = parse_pairs(BEDS_500)
d_pairs = parse_pairs(DESKS_500)
ans = count_valid_permutations(500, b_pairs, d_pairs)
return str(ans)
if __name__ == '__main__':
print(solve())
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Euler673 {
static final long MOD = 999999937L;
static class Pair {
int first, second;
Pair(int f, int s) {
first = f;
second = s;
}
}
static class Comp {
int[] b, d;
Comp(int[] b, int[] d) {
this.b = b;
this.d = d;
}
}
static long modPow(long a, long e) {
long r = 1;
long x = a % MOD;
while (e > 0) {
if ((e & 1) != 0) {
r = (r * x) % MOD;
}
x = (x * x) % MOD;
e >>= 1;
}
return r;
}
static List<Pair> parsePairs(String data) {
List<Pair> out = new ArrayList<>();
String[] lines = data.split("\n");
for (String line : lines) {
line = line.trim();
if (line.isEmpty())
continue;
int pos = line.indexOf(',');
int a = Integer.parseInt(line.substring(0, pos));
int b = Integer.parseInt(line.substring(pos + 1));
out.add(new Pair(a, b));
}
return out;
}
static List<Comp> buildComponents(int n, List<Pair> beds, List<Pair> desks) {
int[] b = new int[n + 1];
int[] d = new int[n + 1];
for (int i = 1; i <= n; ++i) {
b[i] = i;
d[i] = i;
}
for (Pair p : beds) {
b[p.first] = p.second;
b[p.second] = p.first;
}
for (Pair p : desks) {
d[p.first] = p.second;
d[p.second] = p.first;
}
boolean[] seen = new boolean[n + 1];
int[] loc = new int[n + 1];
for (int i = 0; i <= n; i++)
loc[i] = -1;
List<Comp> comps = new ArrayList<>();
for (int s = 1; s <= n; ++s) {
if (seen[s])
continue;
Stack<Integer> stack = new Stack<>();
stack.push(s);
seen[s] = true;
List<Integer> verts = new ArrayList<>();
while (!stack.isEmpty()) {
int v = stack.pop();
verts.add(v);
int nb = b[v];
int nd = d[v];
if (!seen[nb]) {
seen[nb] = true;
stack.push(nb);
}
if (!seen[nd]) {
seen[nd] = true;
stack.push(nd);
}
}
for (int i = 0; i < verts.size(); ++i) {
loc[verts.get(i)] = i;
}
int[] cb = new int[verts.size()];
int[] cd = new int[verts.size()];
for (int i = 0; i < verts.size(); ++i) {
int v = verts.get(i);
cb[i] = loc[b[v]];
cd[i] = loc[d[v]];
}
for (int v : verts) {
loc[v] = -1;
}
comps.add(new Comp(cb, cd));
}
return comps;
}
static class Matcher {
Comp a, b;
int[] mapA, mapB;
Stack<Integer> stack;
int assigned;
Matcher(Comp a, Comp b) {
this.a = a;
this.b = b;
int m = a.b.length;
mapA = new int[m];
mapB = new int[m];
for (int i = 0; i < m; i++) {
mapA[i] = -1;
mapB[i] = -1;
}
stack = new Stack<>();
}
boolean step(int nx, int ny) {
int cur = mapA[nx];
if (cur == -1) {
if (mapB[ny] != -1)
return false;
mapA[nx] = ny;
mapB[ny] = nx;
stack.push(nx);
assigned++;
return true;
}
return cur == ny;
}
boolean tryMapRoot(int startB) {
mapA[0] = startB;
mapB[startB] = 0;
stack.push(0);
assigned = 1;
while (!stack.isEmpty()) {
int x = stack.pop();
int y = mapA[x];
int nxB = a.b[x];
int nyB = b.b[y];
if (!step(nxB, nyB))
return false;
int nxD = a.d[x];
int nyD = b.d[y];
if (!step(nxD, nyD))
return false;
}
return assigned == a.b.length;
}
}
static boolean tryMapRootWrapper(Comp a, Comp b, int startB) {
return new Matcher(a, b).tryMapRoot(startB);
}
static int isomorphismCount(Comp a, Comp b) {
if (a.b.length != b.b.length)
return 0;
int m = b.b.length;
int count = 0;
for (int s = 0; s < m; ++s) {
if ((a.b[0] == 0) != (b.b[s] == s))
continue;
if ((a.d[0] == 0) != (b.d[s] == s))
continue;
if (tryMapRootWrapper(a, b, s))
count++;
}
return count;
}
static long countValidPermutations(int n, List<Pair> beds, List<Pair> desks) {
List<Comp> comps = buildComponents(n, beds, desks);
int c = comps.size();
boolean[] used = new boolean[c];
long ans = 1;
for (int i = 0; i < c; ++i) {
if (used[i])
continue;
used[i] = true;
int aut = isomorphismCount(comps.get(i), comps.get(i));
int mult = 1;
for (int j = i + 1; j < c; ++j) {
if (used[j])
continue;
if (isomorphismCount(comps.get(i), comps.get(j)) > 0) {
used[j] = true;
mult++;
}
}
long fac = 1;
for (int t = 2; t <= mult; ++t) {
fac = (fac * t) % MOD;
}
ans = (ans * modPow(aut, mult)) % MOD;
ans = (ans * fac) % MOD;
}
return ans;
}
static final String BEDS_500 = "1,352\n" +
"2,251\n" +
"3,243\n" +
"4,311\n" +
"5,312\n" +
"6,231\n" +
"7,416\n" +
"8,166\n" +
"9,384\n" +
"10,330\n" +
"11,89\n" +
"12,316\n" +
"13,394\n" +
"14,57\n" +
"15,177\n" +
"16,341\n" +
"17,149\n" +
"18,199\n" +
"19,310\n" +
"20,421\n" +
"21,459\n" +
"22,189\n" +
"23,308\n" +
"25,46\n" +
"26,460\n" +
"27,63\n" +
"28,34\n" +
"29,295\n" +
"30,412\n" +
"31,49\n" +
"32,247\n" +
"33,326\n" +
"35,429\n" +
"36,211\n" +
"37,104\n" +
"38,376\n" +
"39,263\n" +
"40,187\n" +
"41,500\n" +
"42,161\n" +
"43,407\n" +
"44,60\n" +
"45,118\n" +
"47,85\n" +
"48,56\n" +
"50,403\n" +
"51,239\n" +
"52,415\n" +
"53,444\n" +
"54,246\n" +
"55,288\n" +
"58,410\n" +
"59,432\n" +
"61,160\n" +
"62,438\n" +
"65,225\n" +
"67,392\n" +
"68,333\n" +
"69,478\n" +
"70,365\n" +
"71,213\n" +
"72,294\n" +
"73,360\n" +
"74,499\n" +
"75,267\n" +
"76,493\n" +
"77,108\n" +
"78,428\n" +
"79,440\n" +
"80,116\n" +
"81,117\n" +
"82,257\n" +
"83,306\n" +
"84,195\n" +
"86,216\n" +
"87,226\n" +
"88,151\n" +
"90,172\n" +
"91,355\n" +
"93,237\n" +
"94,156\n" +
"95,147\n" +
"96,343\n" +
"97,424\n" +
"98,112\n" +
"100,240\n" +
"101,163\n" +
"102,371\n" +
"103,361\n" +
"106,315\n" +
"107,230\n" +
"109,227\n" +
"110,336\n" +
"111,377\n" +
"113,253\n" +
"114,367\n" +
"115,139\n" +
"119,290\n" +
"120,121\n" +
"122,174\n" +
"123,159\n" +
"124,282\n" +
"125,142\n" +
"126,435\n" +
"127,452\n" +
"128,338\n" +
"129,445\n" +
"130,448\n" +
"131,183\n" +
"132,179\n" +
"133,196\n" +
"134,268\n" +
"135,170\n" +
"136,357\n" +
"137,368\n" +
"138,242\n" +
"141,400\n" +
"143,278\n" +
"144,208\n" +
"145,204\n" +
"146,378\n" +
"148,252\n" +
"152,238\n" +
"153,380\n" +
"154,269\n" +
"155,270\n" +
"157,373\n" +
"158,339\n" +
"162,272\n" +
"164,332\n" +
"167,466\n" +
"168,327\n" +
"169,266\n" +
"173,471\n" +
"175,494\n" +
"176,463\n" +
"178,433\n" +
"180,198\n" +
"181,258\n" +
"182,464\n" +
"184,467\n" +
"186,409\n" +
"188,191\n" +
"190,346\n" +
"192,446\n" +
"193,418\n" +
"197,474\n" +
"200,354\n" +
"201,479\n" +
"202,436\n" +
"205,404\n" +
"206,475\n" +
"207,349\n" +
"210,476\n" +
"212,372\n" +
"214,379\n" +
"217,232\n" +
"218,320\n" +
"219,366\n" +
"220,356\n" +
"221,299\n" +
"222,426\n" +
"223,484\n" +
"224,264\n" +
"228,359\n" +
"229,405\n" +
"233,483\n" +
"234,391\n" +
"235,381\n" +
"236,262\n" +
"241,420\n" +
"244,393\n" +
"245,337\n" +
"248,296\n" +
"249,370\n" +
"250,325\n" +
"254,351\n" +
"255,302\n" +
"256,364\n" +
"260,431\n" +
"261,447\n" +
"265,318\n" +
"271,397\n" +
"273,375\n" +
"274,469\n" +
"275,453\n" +
"276,328\n" +
"279,313\n" +
"280,292\n" +
"283,434\n" +
"284,495\n" +
"285,386\n" +
"286,454\n" +
"287,385\n" +
"289,363\n" +
"291,304\n" +
"293,382\n" +
"297,389\n" +
"298,383\n" +
"301,461\n" +
"303,347\n" +
"305,369\n" +
"309,439\n" +
"314,344\n" +
"317,491\n" +
"319,443\n" +
"321,470\n" +
"322,437\n" +
"323,411\n" +
"324,406\n" +
"331,340\n" +
"334,358\n" +
"335,456\n" +
"342,414\n" +
"345,396\n" +
"350,390\n" +
"374,408\n" +
"387,422\n" +
"395,487\n" +
"398,423\n" +
"399,485\n" +
"401,441\n" +
"402,473\n" +
"413,457\n" +
"417,449\n" +
"425,451\n" +
"427,477\n" +
"430,496\n" +
"442,488\n" +
"450,480\n" +
"462,490\n" +
"465,482\n" +
"472,492\n" +
"481,486\n" +
"497,498";
static final String DESKS_500 = "1,106\n" +
"2,429\n" +
"4,94\n" +
"6,349\n" +
"7,362\n" +
"8,100\n" +
"9,368\n" +
"10,477\n" +
"11,132\n" +
"12,328\n" +
"13,319\n" +
"14,185\n" +
"15,225\n" +
"16,279\n" +
"17,72\n" +
"18,51\n" +
"19,482\n" +
"20,270\n" +
"21,50\n" +
"22,449\n" +
"23,398\n" +
"24,492\n" +
"25,478\n" +
"26,360\n" +
"27,428\n" +
"28,240\n" +
"29,103\n" +
"30,32\n" +
"31,484\n" +
"33,296\n" +
"34,371\n" +
"35,251\n" +
"36,444\n" +
"37,460\n" +
"38,491\n" +
"39,180\n" +
"40,264\n" +
"41,81\n" +
"42,67\n" +
"43,472\n" +
"44,173\n" +
"45,209\n" +
"46,135\n" +
"47,218\n" +
"48,69\n" +
"49,137\n" +
"52,324\n" +
"54,210\n" +
"55,330\n" +
"56,316\n" +
"57,436\n" +
"58,212\n" +
"59,193\n" +
"61,233\n" +
"62,211\n" +
"63,158\n" +
"64,439\n" +
"65,419\n" +
"66,455\n" +
"70,153\n" +
"71,198\n" +
"73,283\n" +
"74,76\n" +
"75,250\n" +
"77,418\n" +
"78,191\n" +
"79,144\n" +
"80,352\n" +
"82,195\n" +
"85,192\n" +
"86,329\n" +
"87,340\n" +
"88,306\n" +
"89,181\n" +
"90,299\n" +
"91,383\n" +
"92,358\n" +
"93,276\n" +
"95,119\n" +
"96,176\n" +
"97,129\n" +
"98,235\n" +
"99,487\n" +
"101,336\n" +
"102,332\n" +
"104,183\n" +
"105,281\n" +
"107,432\n" +
"109,273\n" +
"110,416\n" +
"111,304\n" +
"112,465\n" +
"113,385\n" +
"114,167\n" +
"115,497\n" +
"116,399\n" +
"117,404\n" +
"118,384\n" +
"121,450\n" +
"122,247\n" +
"124,486\n" +
"125,402\n" +
"127,344\n" +
"130,175\n" +
"131,310\n" +
"133,149\n" +
"134,147\n" +
"136,289\n" +
"138,453\n" +
"139,184\n" +
"140,351\n" +
"141,256\n" +
"142,422\n" +
"143,440\n" +
"145,481\n" +
"146,201\n" +
"148,293\n" +
"150,231\n" +
"151,170\n" +
"152,223\n" +
"154,314\n" +
"155,395\n" +
"156,249\n" +
"157,414\n" +
"159,341\n" +
"160,446\n" +
"161,410\n" +
"162,286\n" +
"163,166\n" +
"164,307\n" +
"165,242\n" +
"168,282\n" +
"172,234\n" +
"174,224\n" +
"177,320\n" +
"178,258\n" +
"179,433\n" +
"182,461\n" +
"186,257\n" +
"187,312\n" +
"188,339\n" +
"189,388\n" +
"190,373\n" +
"194,325\n" +
"196,322\n" +
"197,427\n" +
"200,483\n" +
"202,357\n" +
"204,268\n" +
"205,206\n" +
"207,285\n" +
"208,244\n" +
"213,425\n" +
"214,294\n" +
"215,354\n" +
"216,420\n" +
"217,382\n" +
"219,297\n" +
"220,378\n" +
"222,400\n" +
"226,323\n" +
"229,337\n" +
"230,499\n" +
"237,437\n" +
"238,408\n" +
"239,489\n" +
"241,405\n" +
"243,389\n" +
"245,392\n" +
"246,361\n" +
"248,364\n" +
"252,424\n" +
"253,454\n" +
"254,374\n" +
"255,301\n" +
"259,292\n" +
"260,409\n" +
"261,347\n" +
"262,280\n" +
"263,451\n" +
"265,381\n" +
"266,379\n" +
"267,355\n" +
"271,456\n" +
"272,369\n" +
"274,298\n" +
"275,431\n" +
"277,412\n" +
"278,473\n" +
"284,490\n" +
"287,494\n" +
"288,413\n" +
"290,343\n" +
"291,396\n" +
"295,348\n" +
"300,315\n" +
"302,464\n" +
"303,345\n" +
"305,468\n" +
"308,480\n" +
"309,448\n" +
"311,331\n" +
"313,463\n" +
"317,495\n" +
"318,367\n" +
"321,438\n" +
"327,366\n" +
"334,426\n" +
"338,466\n" +
"342,346\n" +
"350,445\n" +
"353,471\n" +
"356,447\n" +
"363,476\n" +
"365,415\n" +
"370,442\n" +
"372,458\n" +
"375,434\n" +
"376,462\n" +
"377,423\n" +
"380,406\n" +
"386,469\n" +
"387,459\n" +
"390,498\n" +
"391,479\n" +
"394,496\n" +
"397,485\n" +
"401,457\n" +
"403,474\n" +
"407,470\n" +
"411,452\n" +
"417,443\n" +
"421,430\n" +
"435,475\n" +
"467,493\n" +
"488,500";
public static String solve() {
List<Pair> bPairs = parsePairs(BEDS_500);
List<Pair> dPairs = parsePairs(DESKS_500);
long ans = countValidPermutations(500, bPairs, dPairs);
return Long.toString(ans);
}
public static void main(String[] args) {
System.out.println(solve());
}
}