Submission #931395

#	Time	Username	Problem	Language	Result	Execution time	Memory
931395		alexander707070	Tents (JOI18_tents)	C++14	100 / 100	286 ms	159056 KiB

tents

#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;
}

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