F - Googol Swaps 解説 by en_translator
Observations on necessary and sufficient conditions (permutation)
Define an undirected graph \(G\) with \(N\) vertices and \(M\) edges, whose vertices represent the positions of characters and each edge \((A_i, B_i)\) represent the choice of \(i\) in the operation. Then each operation can be regarded as swapping the characters on both endpoints of an edge.
When the character originally at vertex \(i\) has moved to vertex \(p_i\), let us represent the state by a permutation \(p = (p_1, \dots, p_N)\).
Also, let us classify the permutations by the parity of its inversion number (the number of pairs \((i, j)\) such that \(i < j\) and \(p_i > p_j\)) into odd and even permutations.
Then any permutation \(p\) resulting from operations satisfies the following:
- Condition A: if an even number of operations was applied, \(p\) is an even permutation; if it is odd, \(p\) is an odd permutation.
- Condition B: for any vertex set \(\{v_1, \dots, v_k\}\) formed by a connected component in \(G\), \(\{v_1, \dots, v_k\}\) and \(\{p_{v_1}, \dots, p_{v_k}\}\) are equal as sets.
Both can be proved by induction on the number of operations applied (proof omitted).
Conversely, any permutation \(p\) satisfying condition B can be achieved by \(N^2\) or fewer operations, which we will prove in the following:
Proof of reachability with $N^2$ or fewer operations:
We will prove by induction on $N$. It is trivial to verify $N = 2$.Take any connected component $C$ of $G$, then any of its spanning trees $T_C$, then any of its leaves $v_1$. Suppose the connected component is formed by the vertex set $\{v_1, \dots, v_{|C|}\}$.
By Condition B, there exists a vertex $v_s$ in $C$ such that $p_{v_s} = v_1$.
By performing operations along the path between $v_1$ and $v_s$ on $T_C$, one can move the character originally at vertex $v_s$ onto vertex $v_1$ with $(N-1)$ or fewer operations. Let $p'$ be the permutation from this state to the goal state.
Here, if we take the graph $G'$ by removing vertex $v_1$ and adjacent edges, the connected components other than $C$ do not change, and $C - \{v_1\}$ is empty or forms a single connected component (because $v_1$ was a leaf of the spanning tree $T_C$). Hence, $p'$ satisfies Condition B on $G'$, so the goal state can be reached with $(N-1)^2$ or fewer operations after removing vertex $v_1$.
Since $(N-1) + (N-1)^2 \leq N^2$, we see that $p$ can be achieved with $N^2$ or fewer operations.
To obtain the state of a permutation \(p\) with exactly \(10^{100}\), it is necessary that \(p\) is an even permutation, and satisfies Condition B.
Conversely, for any even permutation \(p\) satisfying Condition B, one can obtain the state of \(p\) with exactly \(10^{100}\) operations (by first obtaining \(p\) with an even number, not greater than \(N^2\), of operations, then repeating an arbitrary specific operation even number of times).
Hence, the achievable arrangements of the characters are precisely those obtained by an even permutation \(p\) satisfying Condition B.
We consider the arrangements for each connected component independently. Among them, those obtained with an even permutation can be counted by considering the following two cases:
- If the same letter occurs twice or more in a connected component
- Suppose that vertices \(v\) and \(u\) in the connected component have the same letter. Then, for any even permutation \(p\) satisfying condition B, an odd permutation \(p'\) obtained by swapping \(p_v\) and \(p_u\) corresponds one-to-one, and the character arrangements obtained by \(p\) and \(p'\) are equal. Hence, all arrangements can be obtained with an even permutation.
- If no same letter occurs twice or more in a connected component
- For any even permutation \(p\) satisfying condition B, an arrangement of characters correspond one-to-one. By taking any two vertices and applying the same discussion as above, we conclude that exactly half the arrangement can be obtained only with even permutations, and the other half with odd permutations.
Counting
The answer can be obtained by counting the number of possible arrangements independently for each connected component, and multiply it by \(1\) or \(\frac{1}{2}\) according to the discussion above.
For a connected component, if the number of occurrences of each character is \(c_1, c_2, \dots, c_{\sigma}\), the number of arrangements within that connected component is \(\displaystyle \frac{(c_1 + c_2 + \dots + c_{\sigma})!}{c_1! \cdot c_2! \cdot \ldots \cdot c_{\sigma}!}\). Evaluate this for all connected components, and take the product.
Sample code (C++)
#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
#include <map>
using std::map;
#include <string>
using std::string;
using std::max;
using std::min;
using std::swap;
#include <atcoder/modint.hpp>
using mint = atcoder::modint998244353;
#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif
using ll = int64_t;
using P = pair<ll, ll>;
const ll FOD = 998244353;
ll n, m;
string s;
vector<ll> a, b;
void output (const ll x) {
cout << x << "\n";
}
void output (const mint x) {
cout << x.val() << "\n";
}
vector<mint> frac, invf;
void f_init (const ll n) {
frac.resize(n+1);
invf.resize(n+1);
frac[0] = 1;
for (ll i = 1; i <= n; i++) {
frac[i] = frac[i-1] * i;
}
invf[n] = frac[n].inv();
for (ll i = n; i >= 1; i--) {
invf[i-1] = invf[i] * i;
}
assert(invf[0] == 1);
}
mint ncr (const ll n, const ll r) {
if (!(n >= r && r >= 0)) return 0;
return frac.at(n) * invf.at(r) * invf.at(n-r);
}
class dsu {
private:
const ll n;
struct DSUnode {
ll p;
ll sz;
};
vector<DSUnode> dnodes;
public:
dsu (const ll n_): n(n_) {
dnodes.resize(n);
for (ll i = 0; i < n; i++) {
dnodes[i] = {p: i, sz: 1};
}
}
ll find (const ll x) {
if (dnodes.at(x).p == x) return x;
return dnodes.at(x).p = find(dnodes.at(x).p);
}
bool unite (ll l, ll r) {
l = find(l);
r = find(r);
if (l == r) return false;
if (dnodes[l].sz < dnodes[r].sz) swap(l, r);
dnodes[l].sz += dnodes[r].sz;
dnodes[r].p = l;
return true;
}
ll size (const ll x) {
return dnodes[find(x)].sz;
}
};
void solve() {
f_init(n*2+5);
dsu g(n);
for (ll i = 0; i < m; i++) {
g.unite(a[i], b[i]);
}
vector<map<char, ll>> cnts(n); // cnts[v][c] := count of i s.t. g.find(i) == v && s[i] == c
bool hassameswap = false;
for (ll i = 0; i < n; i++) {
cnts[g.find(i)][s[i]] += 1;
if (cnts[g.find(i)][s[i]] >= 2) hassameswap = true;
}
bool ishalf = (!hassameswap);
mint ans = 1;
for (ll i = 0; i < n; i++) {
if (cnts[i].empty()) continue;
ll sz = g.size(i);
for (const auto &[ch, r] : cnts[i]) {
ans *= ncr(sz, r);
sz -= r;
}
assert(sz == 0);
}
if (ishalf) ans /= 2;
output(ans);
return;
}
int main (void) {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
cin >> n >> m;
cin >> s;
a.resize(m);
b.resize(m);
for (ll i = 0; i < m; i++) {
cin >> a[i] >> b[i];
--a[i];
--b[i];
}
solve();
return 0;
}
投稿日時:
最終更新: