oj.uz

Submission #199029

# Submission time Handle Problem Language Result Execution time Memory
199029 2020-01-28T17:08:26 Z ZwariowanyMarcin Mobitel (COCI19_mobitel) C++14
130 / 130
 1453 ms 5752 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define LL long long
#define ld long double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define boost cin.tie(0), ios_base::sync_with_stdio(0);


using namespace std;		

const int nax = 310;
const int MOD = 1e9 + 7;

LL pt(LL a, LL b) {
	if (b == 0) return 1;
	if (b & 1) return a * pt(a, b - 1) % MOD;
	return pt(a * a % MOD, b / 2);
}

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

int n, m, s;
int a[nax][nax];
int dp[2][nax][1010][2];

int main() {	
	scanf ("%d%d%d", &n, &m, &s);
	s--;
	int p = sqrt(s);
	while (1000 < p) p--;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			scanf ("%d", &a[i][j]);
			
	LL ans = 1;
	for (int i = n; i <= n + m - 2; ++i) ans = ans * i % MOD;
	for (int i = 1; i <= m - 1; ++i) ans = ans * pt(i, MOD - 2) % MOD;
	
	if (s == 0) {
		printf ("%lld", ans);
		exit(0);
	}
	
	if (1 < p) 
		dp[0][1][1][0] = 1;
	else 
		dp[0][1][s][1] = 1;
	
	for (int row = 1; row <= n; ++row) {
		int ja = row & 1;
		int on = !ja;
		
		for (int col = 1; col <= m; ++col) {
			
			for (int v = 1; v <= max(p, s / p); ++v)
				for (int k = 0; k < 2; ++k)
					dp[ja][col][v][k] = 0;
			
			for (int v = 1; v <= max(p, s / p); ++v) {
				
				int vv = v * a[row][col];
				if (vv < p) {
					add(dp[ja][col][vv][0], dp[ja][col - 1][v][0]);
					add(dp[ja][col][vv][0], dp[on][col][v][0]);
				}
				else {
					add(dp[ja][col][s / vv][1], dp[ja][col - 1][v][0]);
					add(dp[ja][col][s / vv][1], dp[on][col][v][0]);
				}
				
				vv = v / a[row][col];
				
				add(dp[ja][col][vv][1], dp[ja][col - 1][v][1]);
				add(dp[ja][col][vv][1], dp[on][col][v][1]);
			}
		}
	}
		
	for (int i = 1; i <= max(p, s / p); ++i) {
		ans = (ans - dp[n & 1][m][i][0] + MOD) % MOD;
		ans = (ans - dp[n & 1][m][i][1] + MOD) % MOD;
	}
	printf ("%lld", ans);
	return 0;
}

Compilation message

mobitel.cpp: In function 'int main()':
mobitel.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d", &n, &m, &s);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d", &a[i][j]);
    ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
130.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3320 KB Output is correct
2 Correct 41 ms 3320 KB Output is correct
3 Correct 105 ms 2168 KB Output is correct
4 Correct 115 ms 2168 KB Output is correct
5 Correct 138 ms 2112 KB Output is correct
6 Correct 135 ms 2044 KB Output is correct
7 Correct 63 ms 1528 KB Output is correct
8 Correct 750 ms 4216 KB Output is correct
9 Correct 1429 ms 5752 KB Output is correct
10 Correct 1453 ms 5752 KB Output is correct