Submission #1868163
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int N = 305; const int mod = 1e9 + 7; int n, a[N], f[N][N][N], inv[N], prd[N]; void add(int &x, int y) { x = (x + y) >= mod ? x + y - mod : x + y; } int pw(int x, int y) { if (!y) return 1; int ret = pw(x, y >> 1); ret = 1LL * ret * ret % mod; if (y & 1) ret = 1LL * ret * x % mod; return ret; } int C(int k, int n) { return 1LL * prd[n] * inv[k] % mod * inv[n - k] % mod; } int cal(int x) { return 1LL * C(2, x - 1) * prd[x - 3] % mod; } int main() { ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; prd[0] = 1; for (int i = 1; i <= n; ++i) prd[i] = 1LL * i * prd[i - 1] % mod; inv[n] = pw(prd[n], mod - 2); for (int i = n; i >= 1; --i) inv[i - 1] = 1LL * inv[i] * i % mod; f[0][0][0] = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j <= n; ++j) { for (int k = 0; k <= i; ++k) { if (!f[i][j][k]) continue; add(f[i + 1][j][k], f[i][j][k]); if (a[i + 1] >= 2) { add(f[i + 1][j + a[i + 1] - 2][k + 1], 1LL * f[i][j][k] * prd[a[i + 1] - 1] % mod * C(a[i + 1] - 2, j + a[i + 1] - 2) % mod); } } } } int res = 0; for (int i = 0; i <= n; ++i) { for (int j = 3; j <= n; ++j) { if (!f[n][i][j]) continue; if (n == j && i == 0) { add(res, f[n][i][j]); continue; } if (n == j || i == 0) continue; int val = 1LL * inv[i - 1] * prd[n - j - 1] % mod * cal(j) % mod; for (int k = 1; k <= n; ++k) val = 1LL * val * inv[a[k] - 1] % mod; add(res, 1LL * val * f[n][i][j] % mod); } } cout << res; }
Submission Info
Submission Time | |
---|---|
Task | F - Unicyclic Graph Counting |
User | aome |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1617 Byte |
Status | WA |
Exec Time | 70 ms |
Memory | 108800 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | All | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 200 | 0 / 300 | 0 / 300 | ||||||||||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt |
Subtask1 | 00_example_01.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt |
Subtask2 | 00_example_01.txt, 00_example_02.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s2_15.txt, s2_16.txt |
Subtask3 | 00_example_01.txt, 00_example_02.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s3_17.txt, s3_18.txt, s3_19.txt, s3_20.txt, s3_21.txt, s3_22.txt, s3_23.txt, s3_24.txt, s3_25.txt, s3_26.txt |
All | 00_example_01.txt, 00_example_02.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s3_17.txt, s3_18.txt, s3_19.txt, s3_20.txt, s3_21.txt, s3_22.txt, s3_23.txt, s3_24.txt, s3_25.txt, s3_26.txt, s4_27.txt, s4_28.txt, s4_29.txt, s4_30.txt, s4_31.txt, s4_32.txt, s4_33.txt, s4_34.txt, s4_35.txt, s4_36.txt, s4_37.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 1 ms | 256 KB |
00_example_02.txt | AC | 2 ms | 4352 KB |
s1_01.txt | AC | 1 ms | 256 KB |
s1_02.txt | WA | 1 ms | 256 KB |
s1_03.txt | AC | 1 ms | 256 KB |
s1_04.txt | WA | 1 ms | 256 KB |
s1_05.txt | AC | 1 ms | 256 KB |
s1_06.txt | AC | 1 ms | 256 KB |
s1_07.txt | AC | 1 ms | 256 KB |
s1_08.txt | AC | 1 ms | 256 KB |
s2_09.txt | AC | 2 ms | 4352 KB |
s2_10.txt | AC | 2 ms | 6400 KB |
s2_11.txt | AC | 2 ms | 6400 KB |
s2_12.txt | AC | 2 ms | 6400 KB |
s2_13.txt | AC | 2 ms | 6400 KB |
s2_14.txt | WA | 2 ms | 6400 KB |
s2_15.txt | AC | 2 ms | 6400 KB |
s2_16.txt | AC | 2 ms | 6400 KB |
s3_17.txt | AC | 3 ms | 12544 KB |
s3_18.txt | AC | 3 ms | 12544 KB |
s3_19.txt | AC | 4 ms | 14592 KB |
s3_20.txt | AC | 4 ms | 12544 KB |
s3_21.txt | AC | 2 ms | 6400 KB |
s3_22.txt | AC | 5 ms | 16640 KB |
s3_23.txt | AC | 5 ms | 16640 KB |
s3_24.txt | WA | 4 ms | 16640 KB |
s3_25.txt | AC | 4 ms | 16640 KB |
s3_26.txt | AC | 4 ms | 16640 KB |
s4_27.txt | AC | 18 ms | 55552 KB |
s4_28.txt | AC | 9 ms | 35072 KB |
s4_29.txt | AC | 55 ms | 100608 KB |
s4_30.txt | AC | 13 ms | 43264 KB |
s4_31.txt | AC | 64 ms | 108800 KB |
s4_32.txt | AC | 63 ms | 108800 KB |
s4_33.txt | WA | 33 ms | 108800 KB |
s4_34.txt | AC | 33 ms | 108800 KB |
s4_35.txt | AC | 33 ms | 108800 KB |
s4_36.txt | AC | 49 ms | 108800 KB |
s4_37.txt | AC | 70 ms | 108800 KB |