제출 #1324712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324712		lesinhhung	Tents (JOI18_tents)	C++20	100 / 100	565 ms	42248 KiB

tents

#include <bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
const int N = 3007;
const int MOD = (1e9) + 7;
 
int n,m;
bool used[N][N];
int state[N][N];
 
int choose(int n, int k) {
    if(k==0) return 1;
    if(k==1) return n;
    return n*(n-1)/2;
}
 
int ways(int k) {
    if(k==0) return 1;
    if(k==1) return 4;
    return 1;
}
 
int recurse(int n, int m) {
    if(n==0 || m==0) return 1;
 
    if(used[n][m]) return state[n][m];
    
    long long ans=0;
 
    //1) There is a tent in (1,1) and no other tents in row 1 or column 1
    ans+=4ll*recurse(n-1,m-1);
 
    //2) There is a tent in (1,1) and a tent in (1,x)
    if(m>=2) ans+=(m-1)*1ll*recurse(n-1,m-2);
 
    //3) There is a tent in (1,1) and a tent in (x,1)
    if(n>=2) ans+=(n-1)*1ll*recurse(n-2,m-1);
 
    int row,col;
 
    for(row=0;row<=2 && row+1<=n;row++) {
        for(col=0;col<=2 && col+1<=m;col++) {
            ans+=choose(n-1,row)*1ll*choose(m-1,col)*ways(row)*ways(col)%MOD*recurse(n-1-row,m-1-col);
            
            int rows_left=n-1-row,cols_left=m-1-col;
 
            if(row==1 && cols_left>=1) ans+=choose(n-1,row)*1ll*choose(m-1,col)*cols_left*ways(col)%MOD*recurse(rows_left,cols_left-1);
            if(col==1 && rows_left>=1) ans+=choose(n-1,row)*1ll*choose(m-1,col)*ways(row)*rows_left%MOD*recurse(rows_left-1,cols_left);
            if(row==1 && col==1 && rows_left>=1 && cols_left>=1) ans+=choose(n-1,row)*1ll*choose(m-1,col)*rows_left*cols_left%MOD*recurse(rows_left-1,cols_left-1);
        }
    }
 
    used[n][m]=true;
    return state[n][m]=ans%MOD;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    scanf("%d %d", &n, &m);
    printf("%d\n", (recurse(n,m)-1+MOD)%MOD);
    
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

tents.cpp: In function 'int main()':
tents.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~

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