Submission #770133

#	Time	Username	Problem	Language	Result	Execution time	Memory
770133		Ahmed57	Tents (JOI18_tents)	C++17	100 / 100	349 ms	141712 KiB

tents

#include <bits/stdc++.h>

using namespace std;
long long nCr(long long x){
    return x*(x-1)/2;
}
long long n,m;
long long dp2[3001][3001],dp[3001][3001];
long long mod = 1000000007;
long long solve2(int i,int j){
    if(i==0){
        return 1;
    }
    if(dp2[i][j]!=-1)return dp2[i][j];
    long long c1 = solve2(i-1,j);
    if(j>=1)c1+=(solve2(i-1,j-1)*4ll*j)%mod;
    c1%=mod;
    if(j>=2)c1+=(solve2(i-1,j-2)*nCr(j))%mod;
    c1%=mod;
    return dp2[i][j] = c1;
}
long long solve(int i,int j){
    if(i==n){
        int rem = n-((m-j)/2);
        return solve2(j,rem);
        //base caseeee
    }
    if(dp[i][j]!=-1)return dp[i][j];
    long long c1 = solve(i+1,j);
    if(j>=2){
        c1+=(solve(i+1,j-2)*nCr(j))%mod;
    }c1%=mod;
    return dp[i][j] = c1;
}
int main(){
    cin>>n>>m;
    memset(dp,-1,sizeof dp);
    memset(dp2,-1,sizeof dp2);
    cout<<((solve(0,m)-1)%mod+mod)%mod;
    return 0;
}

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