Submission #362243

#TimeUsernameProblemLanguageResultExecution timeMemory
362243YeboiTents (JOI18_tents)C++14
100 / 100
263 ms70764 KiB
#include <bits/stdc++.h>
#define ll long long
#define mod 998244353
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(long long i(a); i<b ; i++)
#define inf -pow(10,9)
#define MAXN 100000 
const ll INF = 1000000000;
const ll N = 50005;
const ll modi = 1000000007;
const ll modi2= 1000000006;
using namespace std;

int main(){
    ll h,w;
    cin >> h >> w;
    ll dp[h+1][w+1];
    rep(i,h+1){
        rep(j,w+1){
            dp[i][j]=0;
        }
    }
    rep(i,h+1){
        dp[i][0]=1;
    }
    rep(i,w+1){
        dp[0][i]=1;
    }
    f(i,1,h+1){
        f(j,1,w+1){
            dp[i][j]=(dp[i][j]+dp[i][j-1]+modi)%modi;
            dp[i][j]=(dp[i][j]+4*i*dp[i-1][j-1] + modi)%modi;
            ll val1=(i*(i-1))/2;
            ll val2=(i*(j-1));
            if(i>1){
                ll x1=(val1*dp[i-2][j-1]+modi)%modi;
                dp[i][j]=(dp[i][j]+x1+modi)%modi;
            }
            if(j>1){
                ll x2=(val2*dp[i-1][j-2]+modi)%modi;
                dp[i][j]=(dp[i][j]+x2+modi)%modi;
            }
            
            // cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    cout << dp[h][w]-1 << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...