Submission #931395

#TimeUsernameProblemLanguageResultExecution timeMemory
931395alexander707070Tents (JOI18_tents)C++14
100 / 100
286 ms159056 KiB
#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;

long long n,m,nn,mm;
const long long mod=1e9+7;

bool li[MAXN][MAXN];
long long dp[MAXN][MAXN];

long long dp2[MAXN][MAXN];
bool li2[MAXN][MAXN];

long long ff2(long long n,long long m){
    if(m==0)return 1;

    if(li2[n][m])return dp2[n][m];
    li2[n][m]=true;

    dp2[n][m]=ff2(n,m-1);
    if(n>=1)dp2[n][m]+=ff2(n-1,m-1)*n*4;
    if(n>=2)dp2[n][m]+=ff2(n-2,m-1)*n*(n-1)/2;

    dp2[n][m]%=mod;

    return dp2[n][m];
}

long long ff(long long n,long long m){
    if(n==0){
        return ff2(nn-(mm-m)/2,m);
    }

    if(li[n][m])return dp[n][m];
    li[n][m]=true;

    dp[n][m]=ff(n-1,m);
    if(m>=2)dp[n][m]+=ff(n-1,m-2)*m*(m-1)/2;

    dp[n][m]%=mod;

    return dp[n][m];    
}

int main(){

    cin>>n>>m;
    nn=n; mm=m;

    cout<<ff(n,m)-1<<"\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...