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
AC × 2
AC × 9
AC × 18
AC × 28
AC × 39
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