#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 1000000007;
ll Power(ll a,ll b) {
if (b==0)return 1;
ll x = Power(a,b/2);
x = (x*x)%mod;
if (b%2)x=(x*a)%mod;
return x;
}
const int problemsettersIQ = 404; // not found
vector<pair<int,int> > dp[2][problemsettersIQ];
int a[problemsettersIQ][problemsettersIQ];
ll inv(ll x) {return Power(x,mod-2);}
int main()
{
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
if (a[1][1]>k){
printf("0\n");
return 0;
}
dp[1][1].emplace_back(a[1][1],1);
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (i==1 && j==1)continue;
if (i==1){
for (auto x:dp[i%2][j-1]){
if (k/x.first < a[i][j])
break;
dp[i%2][j].emplace_back(x.first*a[i][j],x.second);
}
}
else if (j==1){
for (auto x:dp[(i+1)%2][j]){
if (k/x.first < a[i][j])
break;
dp[i%2][j].emplace_back(x.first*a[i][j],x.second);
}
}
else {
int l=0,r=0;
vector<pair<int,int> >& L = dp[(i+1)%2][j];
vector<pair<int,int> >& R = dp[i%2][j-1];
while(l<L.size() && r<R.size()) {
if (L[l].first==R[r].first) {
if (k/L[l].first < a[i][j])break;
dp[i%2][j].emplace_back(L[l].first*a[i][j],(L[l].second+R[r].second)%mod);
l++,r++;
} else if (L[l].first<R[r].first) {
if (k/L[l].first < a[i][j])break;
dp[i%2][j].emplace_back(L[l].first*a[i][j],L[l].second);
l++;
} else {
if (k/R[r].first < a[i][j])break;
dp[i%2][j].emplace_back(R[r].first*a[i][j],R[r].second);
r++;
}
}
while(l<L.size()) {
if (k/L[l].first < a[i][j])break;
dp[i%2][j].emplace_back(L[l].first*a[i][j],L[l].second);
l++;
}
while(r<R.size()) {
if (k/R[r].first < a[i][j])break;
dp[i%2][j].emplace_back(R[r].first*a[i][j],R[r].second);
r++;
}
}
if (dp[i%2][j].size()>=3000 && (n>=200 || m>=200)) {
vector<pair<int, int> > tmp;
for (auto x:dp[i % 2][j]) {
if (tmp.empty())tmp.push_back(x);
else if (k / tmp.back().first == k / x.first) {
tmp[tmp.size() - 1].second = (tmp[tmp.size() - 1].second + x.second) % mod;
} else {
tmp.push_back(x);
}
}
dp[i % 2][j] = tmp;
}
}
for (int j=1;j<=m;j++) dp[(i+1)%2][j].clear();
}
ll ret=1;
for (int i=n+m-2 - (n-1) +1;i<=n+m-2;i++)ret=(ret*i)%mod;
for (int i=1;i<=(n-1);i++)ret=(ret*inv(i))%mod;
for (auto x:dp[n%2][m]) {
if (x.first==k)break;
ret-=x.second;
ret+=mod;
ret%=mod;
}
printf("%lld\n",ret);
}
Compilation message
mobitel.cpp: In function 'int main()':
mobitel.cpp:53:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l<L.size() && r<R.size()) {
~^~~~~~~~~
mobitel.cpp:53:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l<L.size() && r<R.size()) {
~^~~~~~~~~
mobitel.cpp:68:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(l<L.size()) {
~^~~~~~~~~
mobitel.cpp:73:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(r<R.size()) {
~^~~~~~~~~
mobitel.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&n,&m,&k);
~~~~~^~~~~~~~~~~~~~~~~~~
mobitel.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i][j]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
216 ms |
2812 KB |
Output is correct |
| 2 |
Correct |
226 ms |
2808 KB |
Output is correct |
| 3 |
Correct |
236 ms |
3576 KB |
Output is correct |
| 4 |
Correct |
247 ms |
3584 KB |
Output is correct |
| 5 |
Runtime error |
1100 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
1529 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
1720 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Correct |
3091 ms |
20968 KB |
Output is correct |
| 9 |
Execution timed out |
6017 ms |
27536 KB |
Time limit exceeded |
| 10 |
Correct |
5951 ms |
28404 KB |
Output is correct |
