제출 #1120089

#제출 시각아이디문제언어결과실행 시간메모리
1120089fyanMobitel (COCI19_mobitel)C++14
130 / 130
2779 ms19140 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...