Hướng dẫn giải của Bedao OI Contest 6 - Flagger


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define f first
#define s second

typedef pair<int, int> ii;

const int N = 5005;
const int MOD = 1e9 + 7;

int n, m;
int dp[N + 5][N + 5];

void solve() {
    cin >> n >> m;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j) {
            if (!i || !j) {
                dp[i][j] = 1LL;
                continue;
            }
            dp[i][j] += dp[i][j - 1]; // put nothing
            dp[i][j] = (dp[i - 1][j - 1] * i * 4 + dp[i][j]) %
                       MOD; //  1 tent only on j-th col
            if (i >= 2)
                dp[i][j] = (dp[i - 2][j - 1] * i * (i - 1) / 2 + dp[i][j]) %
                           MOD; // 2 tents on j-th col
            if (j >= 2)
                dp[i][j] =
                    (dp[i - 1][j - 2] * (j - 1) * i + dp[i][j]) %
                    MOD; // 2 tents on 1 row, 1 tent must be put on j column,
                         // thats why * (j - 1) instead of j * (j - 1) / 2
            // generally say, must put at least 1 tent at new j-th column
        }
    cout << (dp[n][m] - 1) % MOD;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("flagger.inp", "r", stdin);
    freopen("flagger.out", "w", stdout);
    int test;
    if (0)
        cin >> test;
    else
        test = 1;
    while (test--) {
        solve();
    }
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.