Submission #362289

#	Time	Username	Problem	Language	Result	Execution time	Memory
362289		n00bie_1004	Tents (JOI18_tents)	C++14	100 / 100	469 ms	73732 KiB

tents

#include <bits/stdc++.h>
 
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef long int li;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define test ll t; cin >> t; while(t--)
const long long int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0}; 
const long long int cons = 3005, ncr_cons = 100005;
const long long int MOD = 1000000007; // const long long int MOD = 998244353; 
const long long int const_INT_MAX = 1000000000000000000, const_INT_MIN = -1 * 1000000000000000000;
using namespace std;
bool sortinrev(const pair<ll,ll> &a, const pair<ll,ll> &b){return (a.first > b.first);}
bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b){return (a.second < b.second);}
bool sortbysecinrev(const pair<ll,ll> &a, const pair<ll,ll> &b){return (a.second > b.second);}
ll gcd(ll x, ll y){return (ll)(__gcd(x, y));}   
ll lcm(ll x, ll y){return (ll)((x * y) / gcd(x, y));}
ll mod_expo(ll x, ll y, ll p){  
    ll res = 1;
    if((x + p) % p == 0){
        return res = 0;
    }
    x = (x + p) % p;
    while (y > 0){   
        if(y & 1) res = (res*x + p) % p; 
        y = y>>1; x = (x*x + p) % p;  
    }  
    return res;    
}
void usaco(string str = ""){    
    fastio; 
    if(str.size()){
        freopen((str + ".in").c_str(), "r", stdin); 
        freopen((str + ".out").c_str(), "w", stdout);
    }   
}
ll invnum[ncr_cons], invfac[ncr_cons], fac[ncr_cons]; 
void pre_ncr(){ // add pre_ncr() in main 
    invnum[0] = invnum[1] = invfac[0] = invfac[1] = fac[0] = 1; 
    for(ll i=2;i<ncr_cons;i++){
        invnum[i] = ((invnum[MOD % i] * (MOD - (MOD / i)) + MOD) % MOD);
    }
    for(ll i=2;i<ncr_cons;i++){
        invfac[i] = ((invnum[i] * invfac[i-1] + MOD) % MOD);
    }
    for(ll i=1;i<ncr_cons;i++){
        fac[i] = ((fac[i-1] * i + MOD) % MOD); 
    }
}
ll ncr(ll n, ll r){
    ll ans = ((fac[n] * invfac[r] + MOD) % MOD) * ((invfac[n-r] + MOD) % MOD); 
    ans += MOD; ans %= MOD; return ans;
}
ll dp[cons][cons];
ll solve(ll h, ll w){
    if(min(h, w) < 0) return 0; 
    if(dp[h][w] != -1) return dp[h][w]; 
    
    ll var = 0; 
    var += (ll)(((solve(h-1, w-1) * h + MOD) % MOD * 4 + MOD) % MOD); var %= MOD; 
    var += (ll)(solve(h, w-1)); var %= MOD;
    var += (ll)(((solve(h-2, w-1) + MOD) % MOD) * ((ncr(h, 2) + MOD) % MOD)); var %= MOD; 
    var += (ll)(((solve(h-1, w-2) + MOD) % MOD) * ((h * (w-1) + MOD) % MOD)); var %= MOD;

    return dp[h][w] = var; 
} 
int main(){ 
    usaco(); pre_ncr();
    for(ll i=0;i<cons;i++){
        for(ll j=0;j<cons;j++){
            if(!(min(i, j))) dp[i][j] = 1; 
            else dp[i][j] = -1; 
        }
    }
    ll h, w; cin >> h >> w; 
    ll var = solve(h, w); var--; var += MOD; var %= MOD; cout << var << "\n";
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message (stderr)

tents.cpp: In function 'void usaco(std::string)':
tents.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         freopen((str + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tents.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |         freopen((str + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52