Submission #479425

#	Time	Username	Problem	Language	Result	Execution time	Memory
479425		rainboy	Mobitel (COCI19_mobitel)	C11	130 / 130	3678 ms	44076 KiB

mobitel

#include <stdio.h>

#define N	300
#define N_	18
#define M	300
#define B	1000
#define MD	1000000007

int vv[N + M], ff[N + M], gg[N + M];

void init() {
	int i;

	ff[0] = gg[0] = 1;
	for (i = 1; i < N + M; 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;
	}
}

int choose(int n, int k) {
	return (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}

int main() {
	static int aa[N][M], dp[M][B], dp1[N_][M][B], dp2[N_][M][B], dq[M][B];
	int n, m, c, i, i_, i1, j, a, b, b1, b2, x, ans;

	init();
	scanf("%d%d%d", &n, &m, &c);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &aa[i][j]);
	if (c == 1)
		ans = 0;
	else {
		for (i = 0; i < n; i++) {
			for (j = 0; j < m; j++)
				if (i == 0 && j == 0)
					dp[j][1] = 1;
				else
					for (b = B - 1; b >= 1; b--) {
						int x = dp[j][b];

						dp[j][b] = 0;
						if (i > 0 && b % (a = aa[i - 1][j]) == 0)
							dp[j][b] = (dp[j][b] + (a == 1 ? x : dp[j][b / a])) % MD;
						if (j > 0 && b % (a = aa[i][j - 1]) == 0)
							dp[j][b] = (dp[j][b] + dp[j - 1][b / a]) % MD;
					}
			if (i % N_ == 0)
				for (j = 0; j < m; j++)
					for (b = 1; b < B; b++)
						dp1[i / N_][j][b] = dp[j][b];
		}
		a = aa[n - 1][m - 1];
		ans = 0;
		for (b = 0; b * a < c && b * a < B; b++)
			ans = (ans + dp[m - 1][b]) % MD;
		for (i = n - 1; i >= 0; i--) {
			if (i == n - 1 || (i + 1) % N_ == 0) {
				for (j = 0; j < m; j++)
					for (b = 1; b < B; b++)
						dp2[0][j][b] = dp1[i / N_][j][b];
				for (i_ = (i1 = i / N_ * N_) + 1; i_ <= i; i_++)
					for (j = 0; j < m; j++)
						for (b = B - 1; b >= 1; b--) {
							dp2[i_ - i1][j][b] = 0;
							if (b % (a = aa[i_ - 1][j]) == 0)
								dp2[i_ - i1][j][b] = (dp2[i_ - i1][j][b] + dp2[i_ - i1 - 1][j][b / a]) % MD;
							if (j > 0 && b % (a = aa[i_][j - 1]) == 0)
								dp2[i_ - i1][j][b] = (dp2[i_ - i1][j][b] + dp2[i_ - i1][j - 1][b / a]) % MD;
						}
			}
			for (j = m - 1; j >= 0; j--)
				if (i == n - 1 && j == m - 1)
					dq[j][1] = 1;
				else
					for (b = B - 1; b >= 1; b--) {
						int x = dq[j][b];

						dq[j][b] = 0;
						if (i + 1 < n && b % (a = aa[i + 1][j]) == 0)
							dq[j][b] = (dq[j][b] + (a == 1 ? x : dq[j][b / a])) % MD;
						if (j + 1 < m && b % (a = aa[i][j + 1]) == 0)
							dq[j][b] = (dq[j][b] + dq[j + 1][b / a]) % MD;
					}
			for (j = m - 1; j >= 0; j--) {
				a = aa[i][j];
				for (b1 = B - 1, b2 = 1, x = 0; b1 * a >= B; b1--) {
					while (b2 < B && (long long) b1 * a * b2 < c)
						x = (x + dq[j][b2++]) % MD;
					ans = (ans + (long long) dp2[i % N_][j][b1] * x) % MD;
				}
			}
		}
	}
	ans = (choose(n - 1 + m - 1, n - 1) - ans + MD) % MD;
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

mobitel.c: In function 'main':
mobitel.c:31:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%d%d", &n, &m, &c);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
mobitel.c:34:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |    scanf("%d", &aa[i][j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 130 / 130