Submission #1675077


Source Code Expand

#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 205;
const int mod = 1e9 + 7;

int n, m, k, tim, cnt, vis[MAXN], dfn[MAXN], low[MAXN], C[MAXN][MAXN];
vector <pii> q, edg[MAXN];
vector <int> adj[MAXN];

inline int Qow(int x, int y)
{
	int r = 1;
	for (; y; y >>= 1, x = 1LL * x * x % mod)
		if (y & 1)
			r = 1LL * r * x % mod;
	return r;
}

inline void Dfs(int x, int p = 0)
{
	dfn[x] = low[x] = ++ tim;
	for (auto y : adj[x])
		if (!dfn[y])
		{
			q.pb(mp(x, y));
			Dfs(y, x);
			low[x] = min(low[x], low[y]);
			if (low[y] >= dfn[x])
			{
				cnt ++;
				while (!q.empty())
				{
					pii e = q.back(); q.pop_back();
					edg[cnt].pb(e);
					if (e == mp(x, y))
						break;
				}
			}
		}
		else if (y ^ p)
		{
			low[x] = min(low[x], dfn[y]);
			if (dfn[x] > dfn[y])
				q.pb(mp(x, y));
		}
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read(), m = Read(), k = Read();
	for (int i = 0; i <= m + k; i ++)
	{
		C[i][0] = 1;
		for (int j = 1; j <= i; j ++)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
	}
	for (int i = 1, x, y; i <= m; i ++)
		x = Read(), y = Read(), adj[x].pb(y), adj[y].pb(x);
	for (int i = 1; i <= n; i ++)
		if (!dfn[i])
			Dfs(i);
	int ans = 1;
	for (int i = 1; i <= cnt; i ++)
	{
		tim ++;
		int v = 0, e = edg[i].size();
		m -= e;
		for (auto e : edg[i])
		{
			if (vis[e.xx] ^ tim)
				vis[e.xx] = tim, v ++;
			if (vis[e.yy] ^ tim)
				vis[e.yy] = tim, v ++;
		}
		if (v == e)
		{
			int ways = 0;
			for (int i = 1; i <= v; i ++)
				ways = (ways + Qow(k, __gcd(i, v))) % mod;
			ways = 1LL * ways * Qow(v, mod - 2) % mod;
			ans = 1LL * ans * ways % mod;
		}
		else if (v == 2 && e == 1)
			ans = 1LL * ans * k % mod;
		else
			ans = 1LL * ans * C[e + k - 1][k - 1] % mod;
	}
	return printf("%d\n", ans), 0;
}

Submission Info

Submission Time
Task F - Painting Graphs with AtCoDeer
User wxh010910
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 2316 Byte
Status AC
Exec Time 1 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 64
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt
Case Name Status Exec Time Memory
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 1 ms 256 KB
1_004.txt AC 1 ms 384 KB
1_005.txt AC 1 ms 384 KB
1_006.txt AC 1 ms 384 KB
1_007.txt AC 1 ms 384 KB
1_008.txt AC 1 ms 384 KB
1_009.txt AC 1 ms 256 KB
1_010.txt AC 1 ms 256 KB
1_011.txt AC 1 ms 256 KB
1_012.txt AC 1 ms 384 KB
1_013.txt AC 1 ms 384 KB
1_014.txt AC 1 ms 384 KB
1_015.txt AC 1 ms 384 KB
1_016.txt AC 1 ms 384 KB
1_017.txt AC 1 ms 384 KB
1_018.txt AC 1 ms 384 KB
1_019.txt AC 1 ms 384 KB
1_020.txt AC 1 ms 384 KB
1_021.txt AC 1 ms 384 KB
1_022.txt AC 1 ms 384 KB
1_023.txt AC 1 ms 384 KB
1_024.txt AC 1 ms 384 KB
1_025.txt AC 1 ms 384 KB
1_026.txt AC 1 ms 384 KB
1_027.txt AC 1 ms 384 KB
1_028.txt AC 1 ms 256 KB
1_029.txt AC 1 ms 256 KB
1_030.txt AC 1 ms 256 KB
1_031.txt AC 1 ms 384 KB
1_032.txt AC 1 ms 256 KB
1_033.txt AC 1 ms 256 KB
1_034.txt AC 1 ms 256 KB
1_035.txt AC 1 ms 384 KB
1_036.txt AC 1 ms 384 KB
1_037.txt AC 1 ms 384 KB
1_038.txt AC 1 ms 384 KB
1_039.txt AC 1 ms 384 KB
1_040.txt AC 1 ms 256 KB
1_041.txt AC 1 ms 256 KB
1_042.txt AC 1 ms 384 KB
1_043.txt AC 1 ms 384 KB
1_044.txt AC 1 ms 256 KB
1_045.txt AC 1 ms 384 KB
1_046.txt AC 1 ms 384 KB
1_047.txt AC 1 ms 384 KB
1_048.txt AC 1 ms 384 KB
1_049.txt AC 1 ms 384 KB
1_050.txt AC 1 ms 384 KB
1_051.txt AC 1 ms 384 KB
1_052.txt AC 1 ms 256 KB
1_053.txt AC 1 ms 256 KB
1_054.txt AC 1 ms 256 KB
1_055.txt AC 1 ms 384 KB
1_056.txt AC 1 ms 256 KB
1_057.txt AC 1 ms 256 KB
1_058.txt AC 1 ms 384 KB
1_059.txt AC 1 ms 384 KB
1_060.txt AC 1 ms 384 KB
1_061.txt AC 1 ms 384 KB
1_062.txt AC 1 ms 384 KB
1_063.txt AC 1 ms 384 KB