Submission #102003

#	Time	Username	Problem	Language	Result	Execution time	Memory
102003		polyfish	Mobitel (COCI19_mobitel)	C++14	0 / 130	154 ms	66560 KiB

mobitel

//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 = 102;
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();
}

• Subtask 1: 0 / 130