Submission #814825

#	Time	Username	Problem	Language	Result	Execution time	Memory
814825		christinelynn	Tents (JOI18_tents)	C++17	0 / 100	227 ms	524288 KiB

tents

#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];

// Rem is dependent on zero and one?????
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[zero][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
• Subtask 2: 0 / 52