結果

問題 No.310 2文字しりとり
ユーザー pekempeypekempey
提出日時 2015-12-13 16:09:36
言語 C++11
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 4,879 bytes
コンパイル時間 2,295 ms
コンパイル使用メモリ 174,864 KB
実行使用メモリ 634,368 KB
最終ジャッジ日時 2024-09-15 11:43:03
合計ジャッジ時間 9,747 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 4 ms
5,376 KB
testcase_19 AC 4 ms
5,376 KB
testcase_20 AC 5 ms
5,376 KB
testcase_21 MLE -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘std::vector<long long int> SparseDeterminant::minpoly_vector(std::vector<std::vector<long long int> >)’:
main.cpp:81:9: warning: no return statement in function returning non-void [-Wreturn-type]
   81 |         }
      |         ^
main.cpp: In member function ‘std::vector<long long int> SparseDeterminant::minpoly_matrix(std::vector<std::vector<long long int> >)’:
main.cpp:85:9: warning: no return statement in function returning non-void [-Wreturn-type]
   85 |         }
      |         ^

ソースコード

diff # 

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;

struct UF {
	vector<int> parent, size;
	UF(int n) : parent(n), size(n, 1) {
		rep (i, n) parent[i] = i;
	}
	int root(int x) {
		if (x == parent[x]) return x;
		else return parent[x] = root(parent[x]);
	}
	void merge(int x, int y) {
		x = root(x); y = root(y);
		if (x == y) return;
		if (size[x] < size[y]) swap(x, y);
		size[x] += size[y];
		parent[y] = x;
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
};

struct SparseDeterminant {
	unsigned long long xor64() {
		static unsigned long long x = time(NULL);
		x ^= x << 13; x ^= x >> 7; x ^= x << 17;
		return x;
	}

	vector<ll> random_vector(int n) {
		vector<ll> res(n);
		rep (i, n) res[i] = xor64() % mod;
		return res;
	}

	// Berlekamp-Massey algorithm
	vector<ll> minpoly(vector<ll> a) {
		const int N = a.size();
		vector<ll> b(N), c(N), t(N);
		b[0] = 1;
		c[0] = 1;
		int l = 0;
		int m = -1;
		for (int n = 0; n < N; n++) {
			int d = 0;
			for (int i = 0; i <= l; i++) {
				(d += c[i] * a[n - i]) %= mod;
			}
			if (d == 1) {
				t = c;
				int N_M = n - m;
				for (int j = 0; j < N - N_M; j++) {
					(c[N_M + j] += b[j]) %= mod;
				}
				if (l <= n / 2) {
					l = n + 1 - l;
					m = n;
					b = t;
				}
			}
		}
		return c;
	}

	vector<ll> minpoly_vector(vector<vector<ll>> b) {
		// TODO: implement
	}

	vector<ll> minpoly_matrix(vector<vector<ll>> A) {
		// TODO: implement
	}
};


ll F[5050];

ll modpow(ll a, ll b, ll mod) {
	ll res = 1;
	while (b) {
		if (b & 1) (res *= a) %= mod;
		(a *= a) %= mod;
		b /= 2;
	}
	return res;
}

ll modinv(ll a, ll mod) {
	return modpow(a, mod - 2, mod);
}

void show(vector<vector<ll>> A) {
	rep (i, A.size()) {
		rep (j, A[0].size()) {
			cout << A[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

ll det(vector<vector<ll>> A) {
	int n = A.size();
	rep (j, n) {
		rep (i, j, n) {
			if (A[i][j] != 0) {
				swap(A[j], A[i]);
				break;
			}
		}
		ll inv = modinv(A[j][j], mod);
		rep (i, j + 1, n) {
			repr (k, j, n) {
				A[i][k] -= A[i][j] * A[j][k] % mod * inv % mod;
				if (A[i][k] < 0) A[i][k] += mod;
			}
		}
	}
	ll res = 1;
	rep (i, n) if (A[i][i] != 0) (res *= A[i][i]) %= mod;
	return res;
}

vector<vector<ll>> remove(vector<vector<ll>> A, vector<char> rm) {
	int N = A.size();
	int cnt = 0;
	rep (i, N) {
		if (rm[i]) cnt++;
		rep (j, N) if (j + cnt < N) A[i][j] = A[i][j + cnt];
	}
	cnt = 0;
	rep (j, N) {
		if (rm[j]) cnt++;
		rep (i, N) if (i + cnt < N) A[i][j] = A[i + cnt][j];
	}
	rep (i, N) A[i].resize(N - cnt);
	A.resize(N - cnt);
	return A;
}


int main() {
	F[0] = 1;
	rep (i, 1, 5050) F[i] = i * F[i - 1] % mod;

	int N, M;
	cin >> N >> M;

	vector<vector<ll>> L(N, vector<ll>(N)); // laplacian matrix
	vector<vector<ll>> A(N, vector<ll>(N)); // adjacent matrix
	vector<vector<ll>> D(N, vector<ll>(N)); // degree matrix
	vector<int> outdeg(N, N), indeg(N, N);

	rep (i, N) rep (j, N) A[i][j] = 1;
	rep (i, N) D[i][i] = N;

	rep (i, M) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		D[u][u]--;
		A[u][v] = 0;
		outdeg[u]--;
		indeg[v]--;
	}

	UF uf(N);
	rep (i, N) rep (j, N) {
		if (A[i][j]) uf.merge(i, j);
	}
	int kind = -1;
	rep (i, N) if (indeg[i] > 0 || outdeg[i] > 0) {
		if (kind == -1) {
			kind = uf.root(i);
		} else {
			if (kind != uf.root(i)) {
				cout << 0 << endl;
				return 0;
			}
		}
	}

	int u = -1, v = -1;
	rep (i, N) {
		if (indeg[i] == outdeg[i] + 1) {
			if (u == -1) {
				u = i;
			} else {
				cout << 0 << endl;
				return 0;
			}
		} else if (indeg[i] == outdeg[i] - 1) {
			if (v == -1) {
				v = i;
			} else {
				cout << 0 << endl;
				return 0;
			}
		} else if (indeg[i] != outdeg[i]) {
			cout << 0 << endl;
			return 0;
		}
	}

	bool cycle = false;
	if (u == -1 && v == -1) {
		u = 0, v = 0;
		cycle = true;
	} else if (u != -1 ^ v != -1) {
		cout << 0 << endl;
		return 0;
	}

	if (!cycle) {
		D[u][v]++;
		A[u][v] = 1;
		outdeg[u]++;
		indeg[v]++;
	}

	rep (i, N) rep (j, N) L[i][j] = D[i][j] - A[i][j];
	vector<char> rm(N);
	rm[u] = true;
	// rep (i, N) if (indeg[i] == 0 && outdeg[i] == 0) rm[i] = true;

	auto Lw = remove(L, rm);
	ll d = det(Lw);

	ll ans = d;

	rep (i, N) if (outdeg[i] > 0) (ans *= F[outdeg[i] - 1]) %= mod;
	if (cycle) (ans *= N * N - M) %= mod;
	if (N * N - M == 0) ans = 1;

	cout << ans << endl;

	return 0;
}
0