oj.uz

Submission #814925

# Submission time Handle Problem Language Result Execution time Memory
814925 2023-08-08T11:10:12 Z kebine Tents (JOI18_tents) C++17
0 / 100
 43 ms 125492 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[4000][4000];
// 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][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 Correct 42 ms 125492 KB Output is correct
2 Incorrect 43 ms 125420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 125492 KB Output is correct
2 Incorrect 43 ms 125420 KB Output isn't correct
3 Halted 0 ms 0 KB -