제출 #1346153

#제출 시각아이디문제언어결과실행 시간메모리
1346153Muhammad_AneeqMobitel (COCI19_mobitel)C++20
52 / 130
6092 ms110688 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=300;
int mod=1e9+7;
int gr[N][N]={};
int n,m,K;
int ans=0;
map<int,int>vls[N][N]={};
int fac[2*N]={},inv[2*N]={};
int power(int x,int y)
{
    int res=1;
    while (y)
    {
        if (y&1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return res;
}
int mul(int a,int b)
{
    return (a*b)%mod;
}
int C(int n,int k)
{
    return mul(fac[n],mul(inv[k],inv[n-k]));
}
inline void rec(int i,int j)
{
    // cout<<i<<' '<<j<<endl;
    for (auto& [k,l]:vls[i][j])
    {
        l%=mod;
        if (k>=K)
        {
            ans=(ans+mul(l,C(n-i+m-j-2,n-i-1)))%mod;
            continue;
        }
        if (i+1<n)
        {
            int pro=(k*gr[i+1][j]);
            pro=min(pro,K);
            vls[i+1][j][pro]+=l;
        }
        if (j+1<m)
        {
            int pro=(k*gr[i][j+1]);
            pro=min(pro,K);
            vls[i][j+1][pro]+=l;
        }
    }
    vls[i][j]={};
}
inline void solve()
{
    cin>>n>>m>>K;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            cin>>gr[i][j];
    vector<pair<int,int>>st;
    for (int i=0;i<m;i++)
        for (int j=0;j<n&&i-j>=0;j++)
            st.push_back({j,i-j});
    for (int i=1;i<n;i++)
        for (int j=0;i+j<n&&m-1-j>=0;j++)
            st.push_back({i+j,m-1-j});
    vls[0][0][gr[0][0]]=1;
    for (auto [i,j]:st)
        rec(i,j);
    cout<<ans<<endl;
}
signed main()
{
    fac[0]=inv[0]=1;
    for (int i=1;i<600;i++)
    {
        fac[i]=(fac[i-1]*i)%mod;
        inv[i]=power(fac[i],mod-2);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...