#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=105;
const int mod=1e9+7;
ll dp[2][N][21][14][10][10];
ll a[N][N];
int n,m,M;
ll pow(int x , int n)
{
ll ret=1;
for(int i=0;i<n;i++)
ret*=x;
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>M;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin>>a[i][j];
}
if(a[0][0]==1)
dp[0][0][0][0][0][0]=1;
if(a[0][0]==2)
dp[0][0][1][0][0][0]=1;
if(a[0][0]==3)
dp[0][0][0][1][0][0]=1;
if(a[0][0]==4)
dp[0][0][2][0][0][0]=1;
if(a[0][0]==5)
dp[0][0][0][0][1][0]=1;
if(a[0][0]==6)
dp[0][0][1][1][0][0]=1;
if(a[0][0]==7)
dp[0][0][0][0][0][1]=1;
if(a[0][0]==8)
dp[0][0][3][0][0][0]=1;
if(a[0][0]==9)
dp[0][0][0][2][0][0]=1;
if(a[0][0]==10)
dp[0][0][1][0][1][0]=1;
int cnt1,cnt2;
for(int I=0;I<n;I++)
{
int i=I%2;
for(int j=0;j<m;j++)
{
if(I==0&&j==0)
continue ;
cnt1=cnt2=0;
for(int to=3;to<11;to*=3)
if(a[I][j]%to==0)
cnt2++;
for(int to=2;to<11;to*=2)
if(a[I][j]%to==0)
cnt1++;
for(int to=0;to<21;to++)
for(int th=0;th<14;th++)
for(int fi=0;fi<10;fi++)
for(int se=0;se<10;se++)
dp[i][j][to][th][fi][se]=0;
for(int to=0;to<21;to++)
{
for(int th=0;th<14;th++)
{
for(int fi=0;fi<10;fi++)
{
for(int se=0;se<10;se++)
{
if(I)
if(dp[i^1][j][to][th][fi][se])
{
dp[i][j][min(to+cnt1,20)][min(cnt2+th,13)][min(fi+(int)(a[I][j]%5==0),9)][min(se+(int)(a[I][j]%7==0),9)]+=dp[i^1][j][to][th][fi][se];
}
if(j)
if(dp[i][j-1][to][th][fi][se])
{
dp[i][j][min(to+cnt1,20)][min(cnt2+th,13)][min(fi+(int)(a[I][j]%5==0),9)][min(se+(int)(a[I][j]%7==0),9)]+=dp[i][j-1][to][th][fi][se];
}
}
}
}
}
for(int to=0;to<21;to++)
{
for(int th=0;th<14;th++)
{
for(int fi=0;fi<10;fi++)
{
for(int se=0;se<10;se++)
{
dp[i][j][to][th][fi][se]%=mod;
}
}
}
}
}
}
ll sum=1;
ll ans=0;
for(int to=0;to<21;to++)
{
for(int th=0;th<14;th++)
{
for(int fi=0;fi<10;fi++)
{
for(int se=0;se<10;se++)
{
sum=pow(2,to)*pow(3,th);
ans%=mod;
if(sum>=M)
{
ans+=dp[(n-1)%2][m-1][to][th][fi][se];;
continue ;
}
sum*=pow(5,fi);
if(sum>=M)
{
ans+=dp[(n-1)%2][m-1][to][th][fi][se];
continue ;
}
sum*=pow(7,se);
if(sum>=M)
{
ans+=dp[(n-1)%2][m-1][to][th][fi][se];
continue ;
}
}
}
}
}
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
148 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
150 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
3541 ms |
46516 KB |
Output isn't correct |
| 4 |
Incorrect |
3603 ms |
46508 KB |
Output isn't correct |
| 5 |
Incorrect |
3578 ms |
46512 KB |
Output isn't correct |
| 6 |
Incorrect |
3583 ms |
46504 KB |
Output isn't correct |
| 7 |
Incorrect |
1646 ms |
32680 KB |
Output isn't correct |
| 8 |
Runtime error |
145 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
152 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
153 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
