Submission #1120089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120089		fyan	Mobitel (COCI19_mobitel)	C++14	130 / 130	2779 ms	19140 KiB

mobitel

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define i64 long long

const int mxn = 405;
const int mxp = 3e3;
const int mod = 1e9+7;

i64 ksm(int a, int b = mod-2) {
	i64 res=1, aux=a;
	for (int i=1; i<=b; i*=2) {
		if (i&b) res=res*aux%mod;
		aux=aux*aux%mod;
	}
	return res;
}

i64 ft[2*mxn],ift[2*mxn];

i64 nck(int n, int k) {
	return ft[n]*ift[k]%mod*ift[n-k]%mod;
}

int r,c,n,g[mxn][mxn];
int dp[2][mxn][mxp];

vector<int> pv;
int pos[mxp*mxp];

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	ft[0] = ift[0] = 1;
	for (int i=1; i<2*mxn; i++) {
		ft[i] = i*ft[i-1]%mod;
		ift[i] = ksm(ft[i]);
	}
	
	cin>>r>>c>>n; n--;
	
	for (int i=0; i<r; i++) {
		for (int j=0; j<c; j++) {
			cin>>g[i][j];
		}
	}
		
	cin>>r>>c>>n;
	
	for (int i=1; i<=n+1; i++) {
		pv.push_back(n/i);
	}
	sort(all(pv)); pv.erase(unique(all(pv)),pv.end());
	
	for (int i=0; i<sz(pv); i++) {
		pos[pv[i]] = i;
	}
	
	int cp = 0, pp = 1;
	
	dp[cp][0][pos[n/g[0][0]]]++;
		
	for (int i=0; i<r-1; i++) {
		swap(cp,pp);
		//first - propogate
		for (int j=0; j<c-1; j++) {
			for (int k=0; k<sz(pv); k++) {
				if (!dp[pp][j][k]) continue;
				int v = pv[k];
				int ni = pos[v/g[i][j+1]];
				dp[pp][j+1][ni] += dp[pp][j][k];
				dp[pp][j+1][ni] %= mod;
			}
		}
		//second - propogate
		memset(dp[cp],0,sizeof(dp[cp]));
		for (int j=0; j<c; j++) {
			for (int k=0; k<sz(pv); k++) {
				if (!dp[pp][j][k]) continue;
				int v = pv[k];
				int ni = pos[v/g[i+1][j]];
				dp[cp][j][ni] += dp[pp][j][k];
				dp[cp][j][ni] %= mod;
			}
		}
	}
	
	for (int j=0; j<c-1; j++) {
		for (int k=0; k<sz(pv); k++) {
			if (!dp[cp][j][k]) continue;
			int v = pv[k];
			int ni = pos[v/g[r-1][j+1]];
			dp[cp][j+1][ni] += dp[cp][j][k];
			dp[cp][j+1][ni] %= mod;
		}
	}
	
	int cnt = 0;
	for (int i=1; i<sz(pv); i++) {
		cnt += dp[cp][c-1][i];
		cnt %= mod;
	}
		
	cnt = (mod+nck(r+c-2,c-1)-cnt)%mod;
	cout<<cnt;
}

• Subtask 1: 130 / 130