Submission #1243641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243641		Bui_Quoc_Cuong	Tents (JOI18_tents)	C++20	100 / 100	142 ms	47664 KiB

tents

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define ALL(A) A.begin(), A.end()
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define taskname "flagger"
const int N = 5e5 + 5;
const int mod = 1e9 + 7;
const int inv2 = 500000004;
int n, m;
int dp[5005][5005];
/*
	Ta nhận xét:
	Khi ta xét tại hàng i cột j thì các thao tác thao tác đặt sẽ làm mất hàng hoặc cột đó
	gọi dp(i, j) là số cách chọn khi còn i hàng và j cột và hàng i là thằng quan tâm duy nhất
*/
int Pow(int x, int y){
	if(y == 0) return 1;
	if(y == 1) return x;
	int c = Pow(x, y / 2);
	if(y & 1) return 1LL * c * c % mod * x % mod;
	else return 1LL * c * c % mod;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if(fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin); 
        freopen(taskname".out", "w", stdout);
    }
	cin >> n >> m;
	FOR(i, 0, n){
		FOR(j, 0, m){
			if(!i || !j){
				dp[i][j] = 1;
				continue;
			}
			/// không làm gì -> mất hàng
			if(i >= 1)
			(dp[i][j]+= 1LL * dp[i - 1][j]) %= mod;
			/// đặt 2 cột 
			if(i >= 1 && j >= 2)
			(dp[i][j]+= 1LL * dp[i - 1][j - 2] * j % mod * (j - 1) % mod * inv2 % mod) %= mod;
			/// đặt 2 hàng
			if(i >= 2 && j >= 1)
			(dp[i][j]+= 1LL * dp[i - 2][j - 1] * j % mod * (i - 1) % mod) %= mod;
			/// đặt tự do
			if(i >= 1 && j >= 1)
			(dp[i][j]+= 1LL * dp[i - 1][j - 1] * 4 % mod * j % mod) %= mod;
		}
	}
	cout << (dp[n][m] - 1 + mod) % mod;
    return 0;
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
tents.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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