제출 #236833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236833		aloo123	Tents (JOI18_tents)	C++14	100 / 100	247 ms	71160 KiB

tents

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define in insert
#define vll vector<ll>
#define endl "\n"
#define pll pair<ll,ll>
#define all(x) (x).begin() , (x).end()
#define f first
#define s second
#define pr(x) cout<<x<<endl;
#define pr2(x,y) cout<<x<<" "<<y<<endl;
#define pr3(x,y,z) cout<<x<<" "<<y<<endl;
#define prv(v) for(auto x:v) cout<<x<<" ";
#define ffs fflush(stdout);
#define int ll
#define sz(x) (ll)x.size()
using namespace std;
 
 
const ll MOD = 1e9+7;
const ll INF = LLONG_MAX;
const ll LOG = 29;
#define PI 3.141592653589793238 
 
 
 


const ll N =(2e5+5);

ll fact[N];

long long binpow(long long a, long long b) {
     a%=MOD;    
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%MOD;
        a = (a * a)%MOD;
 
        
        b >>= 1;
    }
     res%=MOD;
    return res;
}
void ini(){
    fact[0] = 1;
    for(int i = 1;i < N;i++){
        fact[i] = (fact[i-1] * i)%MOD;
    }
}
ll ncr(ll n,ll r){
    ll ret = fact[n];
    ret = (ret * binpow(fact[r],MOD-2))%MOD;
    ret = (ret * binpow(fact[n-r],MOD-2))%MOD;
    return ret;
}
ll dp[3005][3005];
ll n,m;
ll recurse(ll i,ll j){
    if(i < 0 || j < 0){
        return 0;
    }
    else if(i == 0 || j == 0)return 1;
    if(dp[i][j] != -1)
        return dp[i][j];
    ll gg1 = i*(i-1);gg1/=2ll;
    gg1 = (gg1 * recurse(i-2,j-1))%MOD;
    ll gg2 = (4ll*i)%MOD;
    
    gg2 = (gg2 * recurse(i-1,j-1))%MOD;
    ll gg3 = recurse(i,j-1)%MOD;
    ll gg4 = i*(j-1);
    gg4 = (gg4 * recurse(i-1,j-2))%MOD;
    ll gg = gg1;
    gg = (gg + gg2)%MOD;
    gg = (gg + gg3)%MOD;
    gg = (gg + gg4)%MOD;
    return dp[i][j]= gg;

}

void solve(){
    cin >> n >> m;

    for(int i = 0;i<=n;i++){
        for(int j = 0;j<=m;j++){
            dp[i][j]=-1;
        }
    }
    cout << (recurse(n,m)-1+MOD)%MOD << endl;
        

}   
/*
5
abcab
aabab

aabbc
aaabb

*/

 
   
 
 
 /*
 2 3 4 5 6 1
 3 6 10 15 21 
 4 10 20 35 56 
 5 15 35 70 126 
 6 21 56 126 252 
*/
 
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
       
 
     ll tt=1;
    while(tt--){
        solve();
    }    
}

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