Submission #22620

#	Time	Username	Problem	Language	Result	Execution time	Memory
22620		↓우리보다잘하는팀 (#40)	hi (KRIII5_HI)	C++14	7 / 7	406 ms	99088 KiB

HI

#include <cstdio>

const int p = 1000000007;

int a[55], b[101], c[101], B[101], C[101];
int d[101][101], D[101][101];
int e[5005][5005];
int r[5005], R[5005];

int main() {
	int i, j, k, n;
	for (i = 1; i <= 100; i++) {
		for (j = 1; j < i; j++) {
			b[i] = (b[i] + 1ll * b[j] * c[i - j]) % p;
			B[i] = (B[i] + 1ll * b[j] * C[i - j] + 1ll * B[j] * c[i - j]) % p;
		}
		c[i] = (i - b[i] + p) % p;
		C[i] = (i * i - B[i] + p) % p;
		b[i] = (b[i] + c[i]) % p;
		B[i] = (B[i] + C[i]) % p;
	}
	d[0][0] = 1;
	for (i = 1; i <= 100; i++) for (j = 1; j <= 100; j++) for (k = 1; k <= j; k++) {
		d[i][j] = (d[i][j] + 1ll * c[k] * d[i - 1][j - k]) % p;
		D[i][j] = (D[i][j] + (i == 1 ? k == j ? C[k] : 0 : 1ll * c[k] * D[i - 1][j - k])) % p;
	}
	for (i = 0; i <= 5000; i++) {
		e[i][0] = 1;
		for (j = 1; j <= i; j++) e[i][j] = (e[i - 1][j - 1] + e[i - 1][j]) % p;
	}
	r[0] = 1;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		for (j = 5000; j >= 0; j--) {
			r[j] = 0;
			R[j] = 0;
			for (k = 1; k <= j && k <= a[i]; k++) {
				r[j] = (r[j] + 1ll * r[j - k] * e[j][k] % p * d[k][a[i]]) % p;
				R[j] = (R[j] + 1ll * R[j - k] * d[k][a[i]] % p * e[j - 1][k] + 1ll * r[j - k] * D[k][a[i]] % p * e[j - 1][k - 1]) % p;
			}
		}
	}

	k = 0;
	for (i = 0; i <= 5000; i++) k = (k + 1ll * R[i]) % p;
	printf("%d", k);
}

Compilation message (stderr)

HI.cpp: In function 'int main()':
HI.cpp:32:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
HI.cpp:34:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5