# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
102001 | polyfish | Mobitel (COCI19_mobitel) | C++14 | 137 ms | 66560 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Pantyhose(black) + glasses = infinity
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int MAX_N = 302;
const int MAX_A = 1002;
const int MOD = 1000000007;
int R, C, n, mid, a[MAX_N][MAX_N], P[MAX_N*2][MAX_N*2];
int f[MAX_N][MAX_N][MAX_A], g[MAX_N][MAX_N][MAX_A], ps[MAX_N][MAX_N][MAX_A];
void readInput() {
cin >> R >> C >> n;
for (int i=1; i<=R; ++i) {
for (int j=1; j<=C; ++j)
cin >> a[i][j];
}
mid = sqrt(n);
}
void dp1() {
f[1][0][1] = 1;
for (int i=1; i<=R; ++i) {
for (int j=1; j<=C; ++j) {
for (int k=a[i][j]; k<=mid; k += a[i][j])
f[i][j][k] = (f[i-1][j][k/a[i][j]] + f[i][j-1][k/a[i][j]]) % MOD;
}
}
}
void dp2() {
g[R+1][C][1] = 1;
for (int i=R; i>=1; --i) {
for (int j=C; j>=1; --j) {
for (int k=a[i][j]; k<=mid; k += a[i][j])
g[i][j][k] = (g[i+1][j][k/a[i][j]] + g[i][j+1][k/a[i][j]]) % MOD;
}
}
}
void solve() {
for (int i=0; i<=R; ++i) {
for (int j=0; j<=C; ++j) {
for (int k=1; k<=mid; ++k)
ps[i][j][k] = (ps[i][j][k-1] + g[i][j][k]) % MOD;
}
}
int res = 0;
for (int i=1; i<=R; ++i) {
for (int j=1; j<=C; ++j) {
for (int s1=1; s1*s1<=n; ++s1) {
if (s1*s1*a[i][j]*a[i][j]>=n) {
int64_t tmp = (f[i-1][j][s1] + f[i][j-1][s1]) % MOD;
tmp = tmp * (ps[i+1][j][n/(s1*a[i][j])] + ps[i][j+1][n/(s1*a[i][j])]) % MOD;
res = (res + tmp%MOD) % MOD;
}
}
}
}
for (int i=0; i<=R+C; ++i)
P[i][i] = P[i][0] = 1;
for (int i=1; i<=R+C; ++i) {
for (int j=1; j<i; ++j)
P[i][j] = (P[i-1][j] + P[i-1][j-1]) % MOD;
}
if (n==1)
res = 0;
cout << (P[R+C-2][R-1] - res + MOD) % MOD << '\n';
}
int main() {
#ifdef GLASSES_GIRL
freopen(FILE_NAME".in", "r", stdin);
// freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
readInput();
dp1();
dp2();
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |