Submission #481423

#	Time	Username	Problem	Language	Result	Execution time	Memory
481423		rainboy	Zapina (COCI20_zapina)	C11	110 / 110	87 ms	288 KiB

zapina

#include <stdio.h>

#define N	350
#define MD	1000000007

int main() {
	static int vv[N + 1], ff[N + 1], gg[N + 1], dp[N + 1][2];
	int n, i, j, k;

	scanf("%d", &n);
	ff[0] = gg[0] = 1;
	for (i = 1; i <= n; i++) {
		vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
		ff[i] = (long long) ff[i - 1] * i % MD;
		gg[i] = (long long) gg[i - 1] * vv[i] % MD;
	}
	dp[0][0] = 1;
	for (i = 1; i <= n; i++)
		for (j = n; j >= 0; j--)
			for (k = 1; j + k <= n; k++)
				if (k == i)
					dp[j + k][1] = (dp[j + k][1] + (long long) (dp[j][0] + dp[j][1]) * gg[k] % MD) % MD;
				else {
					dp[j + k][0] = (dp[j + k][0] + (long long) dp[j][0] * gg[k]) % MD;
					dp[j + k][1] = (dp[j + k][1] + (long long) dp[j][1] * gg[k]) % MD;
				}
	printf("%lld\n", (long long) dp[n][1] * ff[n] % MD);
	return 0;
}

Compilation message (stderr)

zapina.c: In function 'main':
zapina.c:10:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55