#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 302;
const int MOD = 1e9 + 7;
vector<ii> paths[2][MAXN];
int matriz[MAXN][MAXN],R,S,N, current_x;
ll tot;
ll fast_expo(ll x, ll y){
if(y == 0) return 1;
if(y % 2 == 0){
ll temp = fast_expo(x, y/2);
return (temp*temp) % MOD;
}
else{
return (x*fast_expo(x, y - 1)) % MOD;
}
}
ll mod_inv(ll x){
return fast_expo(x, MOD - 2);
}
ll fatorial(int n){
ll ans = 1;
for(int i = 2;i<=n;i++){
ans = (ans * i) % MOD;
}
return ans;
}
ll binomial(int n, int k){
ll ans = (fatorial(n) * mod_inv(fatorial(k)) ) % MOD;
ans = (ans * mod_inv(fatorial(n - k))) % MOD;
return ans;
}
void in_place_merge(int x, int y, int factor){
int ptr[2], a[2], b[2], sz[2];
ptr[0] = ptr[1] = 0;
a[0] = x, a[1] = x ^ 1;
b[0] = y - 1, b[1] = y;
sz[0] = paths[a[0]][b[0]].size(), sz[1] = paths[a[1]][b[1]].size();
while(ptr[0] < sz[0] || ptr[1] < sz[1]){
ii element = ii(-1, -1);
if(ptr[0] == sz[0]){
if(paths[a[1]][b[1]][ptr[1]].first < factor){
ptr[1] = sz[1];
continue;
}
element = paths[a[1]][b[1]][ptr[1]];
ptr[1]++;
}
else if(ptr[1] == sz[1]){
if(paths[a[0]][b[0]][ptr[0]].first < factor){
ptr[0] = sz[0];
continue;
}
element = paths[a[0]][b[0]][ptr[0]];
ptr[0]++;
}
else if(paths[a[0]][b[0]][ptr[0]] >= paths[a[1]][b[1]][ptr[1]]){
if(paths[a[0]][b[0]][ptr[0]].first < factor){
ptr[0] = sz[0];
continue;
}
element = paths[a[0]][b[0]][ptr[0]];
ptr[0]++;
}
else{
if(paths[a[1]][b[1]][ptr[1]].first < factor){
ptr[1] = sz[1];
continue;
}
element = paths[a[1]][b[1]][ptr[1]];
ptr[1]++;
}
if(paths[x][y].empty() || paths[x][y].back().first != element.first){
paths[x][y].push_back(element);
}
else{
paths[x][y].back().second = (paths[x][y].back().second + element.second) % MOD;
}
}
for(int i = 0;i < paths[x][y].size();i++){
paths[x][y][i].first /= factor;
}
}
int main(){
scanf("%d %d %d", &R, &S, &N);
N--;
for(int i = 1;i<=R;i++){
for(int j = 1;j<=S;j++){
scanf("%d",&matriz[i][j]);
}
}
paths[current_x][1].push_back(ii(N / matriz[1][1], 1));
for(int i = 2;i<=S;i++){
in_place_merge(current_x, i, matriz[1][i]);
}
for(int i = 2;i <= R;i++){
current_x ^= 1;
for(int j = 1;j<=S;j++) paths[current_x][j].clear();
for(int j = 1;j<=S;j++){
in_place_merge(current_x, j, matriz[i][j]);
}
}
ll ans = binomial(R + S - 2, S - 1);
for(ii davez : paths[current_x][S]){
ans = ans - davez.second;
ans %= MOD;
}
if(ans < 0) ans += MOD;
printf("%lld\n",ans);
return 0;
}
Compilation message
mobitel.cpp: In function 'void in_place_merge(int, int, int)':
mobitel.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < paths[x][y].size();i++){
~~^~~~~~~~~~~~~~~~~~~~
mobitel.cpp: In function 'int main()':
mobitel.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &R, &S, &N);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:116:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&matriz[i][j]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
1172 KB |
Output is correct |
| 2 |
Correct |
33 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
71 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
77 ms |
1280 KB |
Output is correct |
| 5 |
Correct |
176 ms |
3592 KB |
Output is correct |
| 6 |
Correct |
169 ms |
3452 KB |
Output is correct |
| 7 |
Correct |
70 ms |
2428 KB |
Output is correct |
| 8 |
Correct |
1301 ms |
7928 KB |
Output is correct |
| 9 |
Correct |
2276 ms |
10820 KB |
Output is correct |
| 10 |
Correct |
2398 ms |
11016 KB |
Output is correct |
