Submission #3327347

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi(a, b) for(int i=a; i<=b; i++)
#define fj(a, b) for(int j=a; j<=b; j++)
#define fo(a, b) for(int o=a; o<=b; o++)
#define fdi(a, b) for(int i=a; i>=b; i--)
#define fdj(a, b) for(int j=a; j>=b; j--)
#define fdo(a, b) for(int o=a; o>=b; o--)
#define clr(x) memset(x, 0, sizeof(x))
#define cpy(x,y) memcpy(x, y, sizeof(y))
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

char __buffer[100000];

#ifdef _DEBUG
#define LOCAL
#endif

void err(const char *format, ... ) {
#ifdef LOCAL
	va_list ap;
	va_start(ap, format);
	vsprintf(__buffer, format, ap);
	va_end(ap);
	
	fprintf(stderr, "\t%s", __buffer);
#else
	if (format < 0) {
		__buffer[0]++;
	}
#endif
}

void errln(const char *format, ... ) {
#ifdef LOCAL
	va_list ap;
	va_start(ap, format);
	vsprintf(__buffer, format, ap);
	va_end(ap);
	
	fprintf(stderr, "\t%s\n", __buffer);
#else
	if (format < 0) {
		__buffer[0]++;
	}
#endif
}

void errln() {
#ifdef LOCAL	
	fprintf(stderr, "\n");
#endif	
}

double START_TIME;

void exit() {
#ifdef LOCAL	
	cerr << "TIME: " << setprecision(5) << fixed << (clock() - START_TIME) / CLOCKS_PER_SEC << endl;
#endif	
	exit(0);
}

template<typename A, typename B>
ostream& operator<<(ostream& os, pair<A, B> p) {
	os << "(" << p.first << ", " << p.second << ")";
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, vector<T> v) {
	fi(0, sz(v) - 1) {
		os << v[i] << " ";
	}
	return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T> t) {
	for (auto z : t) {
		os << z << " ";
	}
	return os;
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, map<T1, T2> t) {
	cerr << endl;
	for (auto z : t) {
		os << "\t" << z.first << " -> " << z.second << endl;
	}
	return os;
}

#ifdef LOCAL
#define dbg(x) {cerr << __LINE__ << "\t" << #x << ": " << x << endl;}
#define dbg0(x, n) {cerr << __LINE__ << "\t" << #x << ": "; for (int ABC = 0; ABC < n; ABC++) cerr << x[ABC] << ' '; cerr << endl;}
#define dbg1(x, n) {cerr << __LINE__ << "\t" << #x << ": "; for (int ABC = 1; ABC <= n; ABC++) cerr << x[ABC] << ' '; cerr << endl;}
#else
#define dbg(x) while(0){}
#define dbg0(x, n) while(0){}
#define dbg1(x, n) while(0){}
#endif

#ifdef LOCAL
#define ass(x) if (!(x)) { cerr << __LINE__ << "\tassertion failed: " << #x << endl, abort(); }
#else
#define ass(x) assert(x)
#endif

///////////////////////////////////////////////////

const int MAX = 341;
const int MOD = 1000 * 1000 * 1000 + 7;

int mul(int a, int b) {
	return (ll) a * b % MOD;
}

int add(int a, int b) {
	a += b;
	if (a >= MOD) a -= MOD;
	return a;
}

int n;
int deg[MAX];

int f[MAX];
int invf[MAX];
int inum[MAX];

int bp(int x, int d) {
	int res = 1;
	while (d) {
		if (d & 1) res = mul(res, x);
		x = mul(x, x);
		d >>= 1;
	}
	return res;
}

int inv(int x) {
	return bp(x, MOD - 2);
}

void init() {
	f[0] = 1;
	fi(1, MAX - 1) {
		f[i] = mul(f[i - 1], i);
	}
	fi(0, MAX - 1) {
		invf[i] = inv(f[i]);
	}
	fi(0, MAX - 1) {
		inum[i] = inv(i);
	}
}

int d[2][MAX][MAX * 2];

void solve() {	
	
	int cnt2 = 0;
	fi(1, n) {
		if (deg[i] == 2) cnt2++;
	}
	if (cnt2 == n) {
		printf("%d\n", mul(inum[2], f[n - 1]));
		return;
	}

	d[0][0][0] = 1;
	fi(1, n) {
		memset(d[1], 0, sizeof(d[1]));
		for (int k = 0; k < n; k++) {
			for (int dc = 0; dc <= n * 2; dc++) {
				if (!d[0][k][dc]) continue;

				d[1][k][dc] = add(d[1][k][dc], mul(invf[deg[i] - 1], d[0][k][dc]));
				if (deg[i] > 1) {
					d[1][k + 1][dc + deg[i] - 2] = add(d[1][k + 1][dc + deg[i] - 2], mul(invf[deg[i] - 2], d[0][k][dc]));
				}
			}
		}
		memcpy(d[0], d[1], sizeof(d[1]));
	}
	int ans = 0;
	for (int k = 3; k <= n; k++) {
		for (int dc = 0; dc <= n * 2; dc++) {
			if (!d[0][k][dc]) continue;
			err("k = %d dc = %d\n", k, dc);
			int v1 = mul(inum[2], f[k - 1]);
			int v2 = f[dc];
			int remd = n * 2 - dc - k * 2 - (n - k) + dc - 1;
			int v3 = f[remd];
			int v4 = d[0][k][dc];
			int v5 = invf[dc - 1];
			err("v1 = %d v2 = %d v3 = %d v4 = %d v5 = %d\n", v1, v2, v3, v4, v5);
			ans = add(ans, mul(v1, mul(v2, mul(v3, mul(v4, v5)))));
		}
	}
	printf("%d\n", ans);
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	START_TIME = (double)clock();
#endif

	init();
	scanf("%d", &n);
	fi(1, n) {
		scanf("%d", &deg[i]);
	}
	solve();

	exit();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:228:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:230:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &deg[i]);
                       ^

Judge Result