Submission #1165927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165927		antonn	Tents (JOI18_tents)	C++20	100 / 100	216 ms	35708 KiB

tents

#include <bits/stdc++.h> 

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 3e3 + 7;
const int M = 1e9 + 7;

int dp[N][N];

int add(int a, int b) {
    a += b;
    if (a >= M) a -= M;
    if (a < 0) a += M;
    return a;
}

int mul(int a, int b) {
    return (ll) a * b % M;
}

int mul(int a, int b, int c) {
    return mul(a, mul(b, c));
}

int mul(int a, int b, int c, int d) {
    return mul(a, mul(b, c, d));
}

int g(int x) {
    if (x % 2 == 0) return mul(x / 2, x - 1);
    if (x % 2 == 1) return mul(x, (x - 1) / 2);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, m; cin >> n >> m;
    for (int i = 0; i <= m; ++i) dp[0][i] = 1;
    for (int i = 0; i <= n; ++i) dp[i][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (m >= 2) dp[i][j] = add(dp[i][j], mul(dp[i - 1][j - 2], g(j)));
            if (n >= 2) dp[i][j] = add(dp[i][j], mul(i - 1, j, dp[i - 2][j - 1]));
            dp[i][j] = add(dp[i][j], mul(4, j, dp[i - 1][j - 1]));
        }
    }
    cout << add(dp[n][m], -1) << "\n";
}

Compilation message (stderr)

tents.cpp: In function 'int g(int)':
tents.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^

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