必要十分条件の考察 (置換)

文字の位置を頂点番号とし，各操作を辺 \((A_i, B_i)\) とした \(N\) 頂点 \(M\) 辺の無向グラフ \(G\) をおきます． このとき，各操作は辺の両端点の文字を交換する操作と言い換えられます．

頂点 \(i\) にあった文字を 頂点 \(p_i\) に移動させた状態を置換 \(p = (p_1, \dots, p_N)\) で表すことにします．

また，置換の転倒数 (\(i < j\) かつ \(p_i > p_j\) を満たす \((i,j)\) 組の個数) の偶奇によって，置換を偶置換と奇置換に二分します．

このとき，操作を何回か行って得られる置換 \(p\) について以下が成り立ちます．

• 条件 A: 操作の合計回数が偶数であれば \(p\) は偶置換，奇数であれば \(p\) は奇置換．
• 条件 B: \(G\) の任意の連結成分における頂点集合 \(\{v_1, \dots, v_k\}\) について，\(\{v_1, \dots, v_k\}\) と \(\{p_{v_1}, \dots, p_{v_k}\}\) は集合として等しい．

これらはいずれも，操作の合計回数についての帰納法で示せます(証明略)．

逆に，条件 B を満たす任意の置換 \(p\) について，\(N^2\) 回以下の操作で最終状態 \(p\) を達成することが可能です．以下に証明を載せます．

ちょうど \(10^{100}\) 回の操作で置換 \(p\) の状態を得るには，\(p\) が偶置換かつ条件 B を満たすことが必要です．

逆に，条件 B を満たす任意の偶置換 \(p\) について，ちょうど \(10^{100}\) 回の操作で \(p\) の状態を得ることが可能です(\(N^2\) 回以下の偶数回の操作で \(p\) を得たあと，適当な特定の操作を偶数回繰り返せばよい)．

よって，達成可能な文字の配置は，条件 B を満たす任意の偶置換 \(p\) で得られるものと言い換えられます．

各連結成分ごとに独立に文字を並べかえる配置を考えます． そのうち偶置換で得られるものの個数は，以下の \(2\) 通りの場合分けによって求まります．

• ある連結成分に同じ文字が \(2\) 個以上ある場合
  • 連結な \(2\) 頂点 \(v, u\) に同じ文字が書いてあるとする．このとき，条件 B を満たす任意の偶置換 \(p\) に対して，\(p_v, p_u\) を入れ替えた奇置換 \(p'\) が一対一対応し，\(p, p'\) から得られる文字配置は一致する．したがって，すべての配置は偶置換で得られる．
• どの連結成分にも同じ文字が \(2\) 個以上ない場合
  • 条件 B を満たす任意の置換と，任意の配置が一対一対応する．連結な \(2\) 頂点を任意にとって上と同様の議論をすることで，すべての配置のうちちょうど半分が偶置換でのみ得られるもので，残りの半分が奇置換でのみ得られるものとわかる．

数え上げ

各連結成分ごとに独立に文字を並べかえる配置を数え上げ，上の場合分けによって \(1\) 倍または \(\frac{1}{2}\) 倍すれば答えが得られる．

ある連結成分において，各種類の文字の個数が \(c_1, c_2, \dots, c_{\sigma}\) のとき，その連結成分における文字の順列の個数は \(\displaystyle \frac{(c_1 + c_2 + \dots + c_{\sigma})!}{c_1! \cdot c_2! \cdot \ldots \cdot c_{\sigma}!}\) です．これらをすべての連結成分について求め，その積を取ればよいです．

実装例 (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;
}