제출 #1283797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283797		tuongll	Tents (JOI18_tents)	C++20	100 / 100	154 ms	106788 KiB

tents

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

const int mod = 1e9 + 7;
const int N = 3003;

int po[N];

int C(int x){
    return (1ll * x * (x - 1) / 2) % mod;
}

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

void add(int &a, int b){
    a += b;
    if (a >= mod) a -= mod;
}

namespace Sub1 {
    int dp[301][301][301];
    void solve(int n, int m){
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; ++i){
            for (int o = 0; o <= m; ++o){
                for (int c = 0; o + c <= m; ++c){
                    // place none
                    add(dp[i][o][c], dp[i - 1][o][c]);
                    // place 1
                    if (m - o + 1 - c > 0 && o > 0)
                        add(dp[i][o][c], mul(m - o + 1 - c, dp[i - 1][o - 1][c]));
                    if (o < m && c > 0)
                        add(dp[i][o][c], mul(o + 1, dp[i - 1][o + 1][c - 1]));
                    // place 2
                    if (m - o - c + 2 > 0 && c >= 2)
                        add(dp[i][o][c], mul(C(m - o - c + 2), dp[i - 1][o][c - 2]));
                }
            }
        }

        int res = mod - 1;
        for (int o = 0; o <= m; ++o){
            for (int c = 0; o + c <= m; ++c)
                add(res, mul(po[o], dp[n][o][c]));
        }
        cout << res << '\n';
    }
};

namespace Sub2 {
    int dp[N][N];
    void solve(int n, int m){
        for (int i = 0; i <= n; ++i){
            for (int j = 0; j <= m; ++j){
                if (i == 0 || j == 0){
                    dp[i][j] = 1;
                    continue;
                }

                add(dp[i][j], dp[i - 1][j]);
                if (i >= 1 && j >= 1) add(dp[i][j], mul(4 * j, dp[i - 1][j - 1]));
                if (i >= 1 && j >= 2) add(dp[i][j], mul(C(j), dp[i - 1][j - 2]));
                if (i >= 2 && j >= 1) add(dp[i][j], mul((i - 1) * j, dp[i - 2][j - 1]));
            }
        }

        add(dp[n][m], mod - 1);
        cout << dp[n][m] << '\n';
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    po[0] = 1;
    for (int i = 1; i < N; ++i)
        po[i] = mul(po[i - 1], 4);

    int n, m; cin >> n >> m;
    if (max(n, m) <= 300){
        Sub1::solve(n, m);
        return 0;
    }

    Sub2::solve(n, m);
}

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