Submission #2151529
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 = 1005; const int MM = 1000000007; int D[MX]; ll F[MX], I[MX], FI[MX]; ll dp[2][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); 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; } // */ auto S = dp[0], E = dp[1]; S[0][0] = 1; for(int i = 1; i <= N; i++){ memset(E, 0, sizeof dp[0]); E[0][0] = 1; for(int j = 1; j <= N; j++){ if(D[i] >= 2){ for(int k = 0; k <= 2*N; k++){ E[j][k] = (S[j][k] + (k >= D[i]? S[j-1][k-D[i]] * (D[i]-1) : 0)) % MM; } } else{ for(int k = 0; k <= 2*N; k++){ E[j][k] = S[j][k]; } } } swap(S, E); } for(int i = 3; i <= N; i++){ for(int j = i*2+1; j <= N*2; j++){ ans = (ans + S[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 | 1000 |
Code Size | 2667 Byte |
Status | AC |
Exec Time | 221 ms |
Memory | 16000 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 | 300 / 300 | 300 / 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 | 7 ms | 16000 KB |
00_example_02.txt | AC | 12 ms | 16000 KB |
s1_01.txt | AC | 1 ms | 256 KB |
s1_02.txt | AC | 1 ms | 256 KB |
s1_03.txt | AC | 7 ms | 16000 KB |
s1_04.txt | AC | 1 ms | 256 KB |
s1_05.txt | AC | 7 ms | 16000 KB |
s1_06.txt | AC | 7 ms | 16000 KB |
s1_07.txt | AC | 6 ms | 16000 KB |
s1_08.txt | AC | 7 ms | 16000 KB |
s2_09.txt | AC | 11 ms | 16000 KB |
s2_10.txt | AC | 12 ms | 16000 KB |
s2_11.txt | AC | 12 ms | 16000 KB |
s2_12.txt | AC | 12 ms | 16000 KB |
s2_13.txt | AC | 12 ms | 16000 KB |
s2_14.txt | AC | 1 ms | 256 KB |
s2_15.txt | AC | 12 ms | 16000 KB |
s2_16.txt | AC | 13 ms | 16000 KB |
s3_17.txt | AC | 19 ms | 16000 KB |
s3_18.txt | AC | 20 ms | 16000 KB |
s3_19.txt | AC | 22 ms | 16000 KB |
s3_20.txt | AC | 19 ms | 16000 KB |
s3_21.txt | AC | 13 ms | 16000 KB |
s3_22.txt | AC | 26 ms | 16000 KB |
s3_23.txt | AC | 26 ms | 16000 KB |
s3_24.txt | AC | 1 ms | 256 KB |
s3_25.txt | AC | 31 ms | 16000 KB |
s3_26.txt | AC | 25 ms | 16000 KB |
s4_27.txt | AC | 82 ms | 16000 KB |
s4_28.txt | AC | 47 ms | 16000 KB |
s4_29.txt | AC | 194 ms | 16000 KB |
s4_30.txt | AC | 63 ms | 16000 KB |
s4_31.txt | AC | 221 ms | 16000 KB |
s4_32.txt | AC | 220 ms | 16000 KB |
s4_33.txt | AC | 1 ms | 256 KB |
s4_34.txt | AC | 166 ms | 16000 KB |
s4_35.txt | AC | 166 ms | 16000 KB |
s4_36.txt | AC | 180 ms | 16000 KB |
s4_37.txt | AC | 214 ms | 16000 KB |