Submission #199029

#	Time	Username	Problem	Language	Result	Execution time	Memory
199029		ZwariowanyMarcin	Mobitel (COCI19_mobitel)	C++14	130 / 130	1453 ms	5752 KiB

mobitel

#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 (stderr)

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 / 130