#513688 (C++14) No.1116 Cycles of Dense Graph

提出ソース

結果

問題	No.1116 Cycles of Dense Graph
ユーザー	cn_449
提出日時	2020-07-18 01:31:01
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	4,193 bytes
コンパイル時間	1,684 ms
コンパイル使用メモリ	147,820 KB
実行使用メモリ	9,600 KB
最終ジャッジ日時	2024-05-07 14:44:29
合計ジャッジ時間	4,822 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	10 ms 9,600 KB
testcase_32	WA	-
testcase_33	AC	10 ms 9,472 KB
testcase_34	AC	9 ms 9,472 KB
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

//あとでしっかり詰める
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#define debug(x) cerr << #x << ':' << x << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

constexpr ll mod = 1000000007;
vector<ll> fac, inv, facinv;

void modcalc(int modsize) {
	fac.resize(modsize); inv.resize(modsize); facinv.resize(modsize);
	fac[0] = 1; fac[1] = 1; inv[1] = 1;
	facinv[0] = 1; facinv[1] = 1;
	for (ll i = 2; i < modsize; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		facinv[i] = facinv[i - 1] * inv[i] % mod;
	}
}

ll modinv(ll a) {
	a %= mod;
	if (a == 0) abort();
	if (a < (ll)inv.size()) return inv[a];
	ll b = mod, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= mod;
	if (u < 0) u += mod;
	return u;
}

ll modpow(ll a, ll b) {
	ll ans = 1;
	a %= mod;
	while (b) {
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

ll modcomb(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[k] % mod * facinv[n - k] % mod;
}

ll modperm(ll n, ll k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * facinv[n - k] % mod;
}

ll modhom(ll n, ll k) {
	if (n < 0 || k < 0 || n == 0 && k > 0) return 0;
	if (n == 0 && k == 0) return 1;
	return fac[n + k - 1] * facinv[k] % mod * facinv[n - 1] % mod;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	modcalc(200010);
	
	vector<ll> sum(200010);
	rep(i, 200005) sum[i + 1] = (sum[i] + fac[i]) % mod;

	int n, m;
	cin >> n >> m;
	vector<ll> a(m), b(m);
	rep(i, m) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
	}
	ll ng = 0;
	for (int i = 1; i < (1 << m); i++) {
		int pcnt = 0;
		rep(j, m) if ((i >> j) & 1) pcnt++;
		map<int, vector<int>> graph;
		map<int, int> deg;
		rep(j, m) {
			if ((i >> j) & 1) {
				deg[a[j]]++; deg[b[j]]++;
				graph[a[j]].pb(b[j]);
				graph[b[j]].pb(a[j]);
			}
		}
		vector<int> use;
		for (auto x : deg) use.pb(x.first);
		map<ll, bool> vis;
		queue<P> que;
		int cycle = 0; int r = 0;
		bool ok = true;
		rep(j, use.size()) {
			int v = use[j];
			if (!vis[v]) {
				r++;
				que.push({ v,-1 });
				while (!que.empty()) {
					P p = que.front(); que.pop();
					int nowv = p.first; int prev = p.second;
					vis[nowv] = true;
					int cnt = 0;
					for (int nxtv : graph[nowv]) {
						if (nxtv == prev) continue;
						cnt++;
						if (vis[nxtv] && nxtv != v) ok = false;
						if (nxtv == v) cycle++;
						if (!vis[nxtv]) {
							que.push({ nxtv,nowv });
						}
					}
					if (cnt > 1) ok = false;
				}
			}
		}
		if (i == 1) debug(cycle), debug(r);
		if (cycle > 1) ok = false;
		if (cycle == 1 && r > 1) ok = false;
		ll res = 0;
		if (ok) {
			if (cycle == 1 && r == 1) res = 1;
			else {
				res = modpow(2, r - 1) * (sum[n - use.size() + r] - sum[r - 1] + mod) % mod;
			}
		}
		if (pcnt & 1) ng += res;
		else ng -= res;
	}
	ng %= mod;
	if (ng < 0) ng += mod;
	ll ans = 0;
	for (int i = 3; i <= n; i++) {
		ll c = fac[n] * facinv[n - i] % mod;
		c *= modinv(2); c %= mod;
		c *= modinv(i); c %= mod;
		ans += c;
	}
	ans -= ng;
	ans %= mod;
	if (ans < 0) ans += mod;
	cout << ans << '\n';
}

yukicoder

結果

テストケース

ソースコード