oj.uz

Submission #814933

# Submission time Handle Problem Language Result Execution time Memory
814933 2023-08-08T11:15:01 Z kebine Tents (JOI18_tents) C++17
0 / 100
 181 ms 524288 KB 
#include <bits/stdc++.h>
#define int long long
#define REP(i,o,n) for(int i=o;i<n;i++)
#define pb push_back
#define fi first
#define se second
#define FORI(v) for(auto i:v)
#define FORJ(v) for(auto j:v)
#define SETIO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
using pii = pair<int, int>;

const int mod = 1e9+7;
const int mi2 = (mod+1)/2;
int memo[400][400][400];
int memo2[4000][4000];

// R-e-m---i-s---d-e-p-e-n-d-e-n-t---o-n---z-e-r-o---a-n-d---o-n-e-?-?-?-?-?-
int dp(int zero, int one, int rem) {
    if(zero<0)return 0;
    if(one<0)return 0;
    if(rem<0)return 0;
    if(rem==0){
        int a = 1;
        REP(i,0,one)a*=4,a%=mod;
        return a;
    }
    
    int &ans=memo[one][zero][rem];
    if(ans!=-1)return ans;
    ans=0;
    ans=dp(zero-2,one,rem-1)*(((zero*(zero-1)))%mod); // Ambil 2
    ans%=mod;
    ans*=mi2;
    ans%=mod;
    ans+=dp(zero-1,one+1,rem-1)*((zero)%mod); // Ambil satu baru
    ans%=mod;
    ans+=dp(zero,one-1,rem-1)*((one)%mod); // Sambung yang lama
    ans%=mod;
    // ans+=dp(zero,one,rem-1); // _Nothing_
    // ans%=mod;   
    return ans;
}

int ncr(int n, int r){
    if(n<r)return 0;
    if(n<0)return 0;
    if(r<0)return 0;

    if(n==r)return 1;
    if(n==0)return 1;
    if(r==0)return 1;
    if(r==1)return n;
    if(n==1)return 1;

    auto&ans=memo2[n][r];
    if(ans!=-1)return ans;
    return ans=((ncr(n-1,r)+ncr(n-1,r-1))%mod);
}

#undef int
int main() 
#define int long long
{
    int h, w;cin>>h>>w;
    memset(memo,-1,sizeof memo);
    memset(memo2,-1,sizeof memo2);
    int ans=0;
    REP(i,0,h+1){
        int res=ncr(h,i);
        res*=dp(w,0,h-i);
        res%=mod;
        ans+=res;
        ans%=mod;
    }
    // ans--;
    // if(ans==-1)ans=(mod-1);
    // int ans=dp(w,0,h);
    if(ans==0)ans=mod-1;
    else ans--;
    cout<<ans<<endl;
}

Subtask #1
0 / 48.0

# Verdict Execution time Memory Grader output
1 Runtime error 181 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 181 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -