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
AC × 2
AC × 9
AC × 18
AC × 19
WA × 9
AC × 19
WA × 20
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