Submission #1349503
Source Code Expand
#include <cstdio> #include <algorithm> #include <set> #include <vector> typedef long long int64; static const int MAXN = 52; static const int MAXM = 202; static const int MAXK = 102; static const int MODULUS = 1e9 + 7; #define _ % MODULUS #define __ %= MODULUS template <typename T> inline T gcd(const T a, const T b) { return b == 0 ? a : gcd<T>(b, a % b); } int64 fact[MAXM + MAXK], fact_inv[MAXM + MAXK]; inline int64 fpow(int64 base, int exp) { int64 ans = 1; for (; exp; exp >>= 1, (base *= base)__) if (exp & 1) (ans *= base)__; return ans; } inline void preprocess() { fact[0] = 1; for (int i = 1; i < MAXM + MAXK; ++i) fact[i] = fact[i - 1] * i _; fact_inv[MAXM + MAXK - 1] = fpow(fact[MAXM + MAXK - 1], MODULUS - 2); for (int i = MAXM + MAXK - 2; i >= 0; --i) fact_inv[i] = fact_inv[i + 1] * (i + 1)_; } inline int64 binom(int n, int m) { if (n < m) return 0; else return fact[n] * fact_inv[n - m]_ * fact_inv[m]_; } int n, m, k; int head[MAXN], dest[MAXM], next[MAXM]; inline void add_edge(int u, int v) { static int w = 0; dest[w] = v; next[w] = head[u]; head[u] = w++; } int dfn[MAXN], low[MAXN]; int stk[MAXN], top = 0; std::vector<int> bcc[MAXN]; int bcc_ct = 0; void dfs_bcc(int u, int p = -1) { static int epoch = 0; dfn[u] = low[u] = epoch++; for (int w = head[u]; w != -1; w = next[w]) if (dest[w] != p) { if (dfn[dest[w]] == -1) { stk[top++] = w; dfs_bcc(dest[w], u); if (low[dest[w]] >= dfn[u]) { do bcc[bcc_ct].push_back(stk[--top]); while (stk[top] != w); ++bcc_ct; } low[u] = std::min(low[u], low[dest[w]]); } else if (dfn[dest[w]] < dfn[u]) { stk[top++] = w; low[u] = std::min(low[u], dfn[dest[w]]); } } } inline bool check_cycle(const std::vector<int> &block) { std::set<int> s; for (int w : block) { s.insert(dest[w]); s.insert(dest[w ^ 1]); } return s.size() == block.size(); } int main() { preprocess(); scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; ++i) head[i] = -1; int u, v; for (int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); --u, --v; add_edge(u, v); add_edge(v, u); } for (int i = 0; i < n; ++i) dfn[i] = -1; for (int i = 0; i < n; ++i) if (dfn[i] == -1) dfs_bcc(i, -1); int64 ans = 1; for (int i = 0; i < bcc_ct; ++i) { //for (int w : bcc[i]) printf(" %d-%d", dest[w], dest[w ^ 1]); putchar('\n'); if (bcc[i].size() == 1u) { (ans *= k)__; } else if (check_cycle(bcc[i])) { int sz = bcc[i].size(); int64 cur = 0; for (int i = 0; i < sz; ++i) cur += fpow(k, gcd(i, sz)); (ans *= cur * fpow(sz, MODULUS - 2))__; } else { int sz = bcc[i].size(); (ans *= binom(sz + k - 1, k - 1))__; } } printf("%lld\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Painting Graphs with AtCoDeer |
User | cyand1317 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3092 Byte |
Status | WA |
Exec Time | 1 ms |
Memory | 256 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:79:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d", &n, &m, &k); ^ ./Main.cpp:83:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &u, &v); --u, --v; ^
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1300 | ||||||
Status |
|
|
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 | 256 KB |
1_005.txt | AC | 1 ms | 256 KB |
1_006.txt | AC | 1 ms | 256 KB |
1_007.txt | AC | 1 ms | 256 KB |
1_008.txt | AC | 1 ms | 256 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 | 256 KB |
1_013.txt | AC | 1 ms | 256 KB |
1_014.txt | WA | 1 ms | 256 KB |
1_015.txt | WA | 1 ms | 256 KB |
1_016.txt | AC | 1 ms | 256 KB |
1_017.txt | AC | 1 ms | 256 KB |
1_018.txt | WA | 1 ms | 256 KB |
1_019.txt | AC | 1 ms | 256 KB |
1_020.txt | WA | 1 ms | 256 KB |
1_021.txt | WA | 1 ms | 256 KB |
1_022.txt | WA | 1 ms | 256 KB |
1_023.txt | AC | 1 ms | 256 KB |
1_024.txt | AC | 1 ms | 256 KB |
1_025.txt | WA | 1 ms | 256 KB |
1_026.txt | AC | 1 ms | 256 KB |
1_027.txt | WA | 1 ms | 256 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 | 256 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 | 256 KB |
1_036.txt | AC | 1 ms | 256 KB |
1_037.txt | AC | 1 ms | 256 KB |
1_038.txt | AC | 1 ms | 256 KB |
1_039.txt | AC | 1 ms | 256 KB |
1_040.txt | AC | 1 ms | 256 KB |
1_041.txt | AC | 1 ms | 256 KB |
1_042.txt | AC | 1 ms | 256 KB |
1_043.txt | AC | 1 ms | 256 KB |
1_044.txt | AC | 1 ms | 256 KB |
1_045.txt | WA | 1 ms | 256 KB |
1_046.txt | AC | 1 ms | 256 KB |
1_047.txt | AC | 1 ms | 256 KB |
1_048.txt | AC | 1 ms | 256 KB |
1_049.txt | AC | 1 ms | 256 KB |
1_050.txt | AC | 1 ms | 256 KB |
1_051.txt | AC | 1 ms | 256 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 | 256 KB |
1_056.txt | AC | 1 ms | 256 KB |
1_057.txt | AC | 1 ms | 256 KB |
1_058.txt | AC | 1 ms | 256 KB |
1_059.txt | AC | 1 ms | 256 KB |
1_060.txt | AC | 1 ms | 256 KB |
1_061.txt | AC | 1 ms | 256 KB |
1_062.txt | AC | 1 ms | 256 KB |
1_063.txt | AC | 1 ms | 256 KB |