結果

問題 No.3105 Parallel Connection and Spanning Trees
ユーザー shobonvip
提出日時 2025-01-18 05:47:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,898 bytes
コンパイル時間 5,429 ms
コンパイル使用メモリ 273,604 KB
実行使用メモリ 80,428 KB
最終ジャッジ日時 2025-01-28 23:00:06
合計ジャッジ時間 101,067 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

// O(K^2N^3) ... のはず
// これは落としたい！！

#include<bits/stdc++.h>
using namespace std;

//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/

/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/

typedef long long ll;

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

template <typename T> bool chmin(T &a, const T &b) {
	if (a <= b) return false;
	a = b;
	return true;
}

template <typename T> bool chmax(T &a, const T &b) {
	if (a >= b) return false;
	a = b;
	return true;
}

template <typename T> T max(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
	return ret;
}

template <typename T> T min(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
	return ret;
}

template <typename T> T sum(vector<T> &a){
	T ret = 0;
	for (int i=0; i<(int)a.size(); i++) ret += a[i];
	return ret;
}

// https://nyaannyaan.github.io/library/fps/nth-term.hpp.html
template<typename mint>
vector<mint> BerlekampMassey(const vector<mint> &s) {
	const int N = (int)s.size();
	vector<mint> b, c;
	b.reserve(N + 1);
	c.reserve(N + 1);
	b.push_back(mint(1));
	c.push_back(mint(1));
	mint y = mint(1);
	for (int ed = 1; ed <= N; ed++) {
		int l = int(c.size()), m = int(b.size());
		mint x = 0;
		for (int i = 0; i < l; i++) x += c[i] * s[ed - l + i];
		b.emplace_back(mint(0));
		m++;
		if (x == mint(0)) continue;
		mint freq = x / y;
		if (l < m) {
			auto tmp = c;
			c.insert(begin(c), m - l, mint(0));
			for (int i = 0; i < m; i++) c[m - 1 - i] -= freq * b[m - 1 - i];
			b = tmp;
			y = x;
		} else {
			for (int i = 0; i < m; i++) c[l - 1 - i] -= freq * b[m - 1 - i];
		}
	}
	reverse(begin(c), end(c));
	return c;
}

// https://yukicoder.me/wiki/black_box_linear_algebra
template<typename mint>
mint sparse_det(int n, vector<tuple<int,int,mint>> &a) {
	random_device seed_gen;
	mt19937 engine(seed_gen());
	uniform_int_distribution<int> dist(1, mint::mod() - 1);
	
	if ((int)a.size() == 0) return 0;

	vector<mint> d(n);
	mint ddet = 1;
	for (int i=0; i<n; i++) {
		d[i] = mint(dist(engine));
		ddet *= d[i];
	}

	vector<mint> g(0);
	vector<mint> b(n), c(n);
	for (int i=0; i<n; i++) {
		b[i] = mint(dist(engine));
		c[i] = mint(dist(engine));
	}

	vector<mint> f(2 * n);
	for (int i=0; i<2*n; i++) {
		for (int z=0; z<n; z++) {
			f[i] += c[z] * b[z];
		}
		if (i == 2*n-1) break;
		vector<mint> nb(n);
		for (int z=0; z<n; z++) {
			b[z] *= d[z];
		}
		for (auto [x, y, val]: a) {
			nb[x] += val * b[y];
		}
		swap(b, nb);
	}

	g = BerlekampMassey<mint>(f);
	if (n % 2 == 1) g.back() *= -1;
	return g.back() / ddet;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int k; cin >> k;
	int cnt = 2;
	vector<int> a, b;
	vector<int> s, t;
	for(int i=0; i<k; i++) {
		int n, m; cin >> n >> m;
		a.push_back(0);
		b.push_back(cnt);
		a.push_back(1);
		b.push_back(cnt + 1);
		for (int j=0; j<m; j++) {
			int x, y; cin >> x >> y;
			x--; y--;
			a.push_back(x + cnt);
			b.push_back(y + cnt);
		}
		cnt += n;
	}

	vector<mint> vals;
	map<pair<int,int>,int> mp;
	auto add = [&](int x, int y, mint val) -> void {
		if (mp.find(pair(x,y)) == mp.end()){
			mp[pair(x,y)] = (int)vals.size();
			vals.push_back(0);
		}
		vals[mp[pair(x,y)]] += val;
	};
	for (int i=0; i<(int)a.size(); i++) {
		if (a[i] - 1 >= 0 && b[i] - 1 >= 0) {
			add(a[i]-1,b[i]-1,-1);
			add(b[i]-1,a[i]-1,-1);
		}
		if (a[i] - 1 >= 0) {
			add(a[i]-1,a[i]-1,+1);
		}
		if (b[i] - 1 >= 0) {
			add(b[i]-1,b[i]-1,+1);
		}
	}
	
	vector<tuple<int,int,mint>> mat;
	for (auto[x,v]:mp)mat.push_back(make_tuple(x.first,x.second,vals[v]));
	cout << sparse_det(cnt-1, mat).val() << endl;
}
0