Submission #931393

#	Time	Username	Problem	Language	Result	Execution time	Memory
931393		alexander707070	Tents (JOI18_tents)	C++14	48 / 100	164 ms	245460 KiB

tents

#include<bits/stdc++.h>
#define MAXN 307
using namespace std;

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

bool li[MAXN][MAXN][MAXN];
long long dp[MAXN][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>=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,long long e){
    if(n==0){
        return ff2(e,m);
    }

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

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

    dp[n][m][e]%=mod;

    return dp[n][m][e];    
}

int main(){

    cin>>n>>m;

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

    return 0;
}

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