Submission #2151518
Source Code Expand
#include <stdio.h> #include <algorithm> #include <assert.h> #include <bitset> #include <cmath> #include <complex> #include <deque> #include <functional> #include <iostream> #include <limits.h> #include <map> #include <math.h> #include <queue> #include <set> #include <stdlib.h> #include <string.h> #include <string> #include <time.h> #include <unordered_map> #include <unordered_set> #include <vector> #pragma warning(disable:4996) #pragma comment(linker, "/STACK:336777216") using namespace std; #define mp make_pair #define all(x) (x).begin(), (x).end() #define ldb ldouble typedef tuple<int, int, int> t3; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <ll, int> pli; typedef pair <db, db> pdd; int IT_MAX = 1 << 18; int MOD = 1000000007; const int INF = 0x3f3f3f3f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const db PI = acos(-1); const db ERR = 1e-10; #define szz(x) (int)(x).size() #define rep(i, n) for(int i=0;i<n;i++) #define Se second #define Fi first const int MX = 205; const int MM = 1000000007; int D[MX]; ll F[MX], I[MX], FI[MX]; ll dp[MX][MX][MX]; int N; int main() { F[0] = I[1] = FI[0] = 1; for(int i = 2; i < MX; i++) I[i] = (MM - MM/i) * I[MM%i] % MM; for(int i = 1; i < MX; i++) F[i] = F[i-1] * i % MM; for(int i = 1; i < MX; i++) FI[i] = FI[i-1] * I[i] % MM; scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d", D+i); sort(D, D+N); if(D[0] >= 2) return !printf("%lld\n", F[N-1] * I[2] % MM); if(N > 18) return 0; ll ans = 0; /* for(int i = 0; i < 1<<N; i++){ ll mul = 1; int sz = 0, sum = 0, ch = 1; for(int j = 0; j < N; j++){ if(~i&1<<j) continue; if(D[j] <= 1 ) ch = 0; mul = mul * (D[j]-1) % MM; sz++; sum += D[j]-2; } if( !ch || sum <= 0 || sz <= 2) continue; mul = mul * F[sz-1] % MM * F[N-sz-1] % MM * sum % MM; ans = (ans + mul) % MM; } // */ dp[0][0][0] = 1; for(int i = 1; i <= N; i++){ dp[i][0][0] = 1; for(int j = 1; j <= N; j++){ if(D[i] >= 2){ for(int k = 0; k <= 2*N; k++){ dp[i][j][k] = (dp[i-1][j][k] + (k >= D[i]? dp[i-1][j-1][k-D[i]] * (D[i]-1) : 0)) % MM; } } else{ for(int k = 0; k <= 2*N; k++){ dp[i][j][k] = dp[i-1][j][k]; } } } } for(int i = 3; i <= N; i++){ for(int j = i*2+1; j <= N*2; j++){ ans = (ans + dp[N][i][j] * F[i-1] % MM * F[N-i-1] % MM * (j-i*2)) % MM; } } for(int i = 0; i < N; i++) ans = ans * FI[D[i]-1] % MM; printf("%lld\n", ans * I[2] % MM); }
Submission Info
Submission Time | |
---|---|
Task | F - Unicyclic Graph Counting |
User | zigui |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 2653 Byte |
Status | WA |
Exec Time | 2 ms |
Memory | 4480 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:66:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &N); ^ ./Main.cpp:67:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for(int i = 0; i < N; i++) scanf("%d", D+i); ^
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 200 / 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 | 4480 KB |
s1_01.txt | AC | 1 ms | 256 KB |
s1_02.txt | AC | 1 ms | 256 KB |
s1_03.txt | AC | 1 ms | 256 KB |
s1_04.txt | AC | 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 | 4480 KB |
s2_10.txt | AC | 2 ms | 4480 KB |
s2_11.txt | AC | 2 ms | 4480 KB |
s2_12.txt | AC | 2 ms | 4480 KB |
s2_13.txt | AC | 2 ms | 4480 KB |
s2_14.txt | AC | 1 ms | 256 KB |
s2_15.txt | AC | 2 ms | 4480 KB |
s2_16.txt | AC | 2 ms | 4480 KB |
s3_17.txt | WA | 1 ms | 256 KB |
s3_18.txt | WA | 1 ms | 256 KB |
s3_19.txt | WA | 1 ms | 256 KB |
s3_20.txt | WA | 1 ms | 256 KB |
s3_21.txt | WA | 1 ms | 256 KB |
s3_22.txt | WA | 1 ms | 256 KB |
s3_23.txt | WA | 1 ms | 256 KB |
s3_24.txt | AC | 1 ms | 256 KB |
s3_25.txt | WA | 1 ms | 256 KB |
s3_26.txt | WA | 1 ms | 256 KB |
s4_27.txt | WA | 1 ms | 256 KB |
s4_28.txt | WA | 1 ms | 256 KB |
s4_29.txt | WA | 1 ms | 256 KB |
s4_30.txt | WA | 1 ms | 256 KB |
s4_31.txt | WA | 1 ms | 256 KB |
s4_32.txt | WA | 1 ms | 256 KB |
s4_33.txt | WA | 1 ms | 256 KB |
s4_34.txt | WA | 1 ms | 256 KB |
s4_35.txt | WA | 1 ms | 256 KB |
s4_36.txt | WA | 1 ms | 256 KB |
s4_37.txt | WA | 1 ms | 256 KB |