Submission #1283689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283689		tuongll	Tents (JOI18_tents)	C++20	48 / 100	184 ms	106764 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;
    }
};

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;
    }
}

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