oj.uz

Submission #1115542

# Submission time Handle Problem Language Result Execution time Memory
1115542 2024-11-20T15:38:29 Z frankmauer1812 Tents (JOI18_tents) C++14
100 / 100
 148 ms 30024 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define MASK(x) ((1LL) << (x))
#define BIT(x, i) (((x) >> (i)) & (1LL))
#define eb emplace_back
#define pb push_back

const int N = 5000 + 5;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int base = 31;
const int BL = 350;

template<class X, class Y> bool maximize(X &x, Y y) {if(x < y){x = y; return true;} return false;}
template<class X, class Y> bool minimize(X &x, Y y) {if(x > y){x = y; return true;} return false;}
void add(int &x, int y){x += y; if(x >= mod) x -= mod;}
void sub(int &x, int y){x -= y; if(x < 0) x += mod;}
int mul(int x, int y){return 1LL * x * y % mod;}
int calPw(int x, int y){
    int ans = 1;
    while(y){
        if(y & 1) ans = 1LL * ans * x % mod;
        x = 1LL * x * x % mod;
        y >>= 1;
    }
    return ans;
}
///Deruck Phung - Luong The Vinh High School For The Gifted
int n, m;
int dp[N][N];
int fact[2 * N], finv[2 * N], pw[2 * N], val[2 * N];
///Code
int C(int k, int n){
    if(k > n) return 0;
    return mul(fact[n], mul(finv[k], finv[n - k]));
}

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

    #define TASK "main"
    if(fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    cin >> n >> m;
    if(n > m) swap(n, m);
    int num = n + m;

    fact[0] = 1;
    for(int i = 1; i <= num; i++) fact[i] = mul(fact[i - 1], i);
    finv[num] = calPw(fact[num], mod - 2);
    for(int i = num - 1; i >= 0; i--) finv[i] = mul(finv[i + 1], i + 1);
    pw[0] = 1;
    for(int i = 1; i <= num; i++) pw[i] = mul(pw[i - 1], 4);

    ///dp(i, j): 1 -> i, đã nối được j cạnh
    dp[0][0] = 1;
    for(int i = 1; i <= m; i++)
        for(int j = 0; j <= min(i, n); j++){
            ///Còn cả trên cả dưới
            if(i <= n){
                ///Không nối cả trên dưới
                add(dp[i][j], dp[i - 1][j]);
                ///Nối 1 trên hoặc 1 dưới
                if(j >= 1) add(dp[i][j], mul(mul(i - j, 2), dp[i - 1][j - 1]));
                ///Nối cả trên và dưới
                if(j >= 2) add(dp[i][j], mul(mul(i - j + 1, i - j + 1), dp[i - 1][j - 2]));
                ///Nối 2 thằng cho nhau
                if(j >= 1) add(dp[i][j], dp[i - 1][j - 1]);
            }
            else{
                ///Chỉ còn trên
                ///Không nối
                add(dp[i][j], dp[i - 1][j]);
                ///Nối
                if(j >= 1) add(dp[i][j], mul(n - j + 1, dp[i - 1][j - 1]));
            }

            //cout << i << " " << j << " " << dp[i][j] << "\n";
        }

    //cout << C(2, 4) << "\n";
    //cout << dp[4][2] << "\n";
    int Ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= i; j++){
            add(val[j], mul(mul(mul(fact[j], pw[i - j]), C(j, i)), mul(dp[m][i], C(j, n + m - 2 * i))));

        }
    }

    for(int i = 0; i <= n; i++){
//        if(i == 2)
//            cout << val[i] << "\n";
        add(Ans, mul(val[i], calPw(calPw(2, i), mod - 2)));
    }
    //Ans = mul(Ans, calPw(2, mod - 2));
    cout << Ans;
}

Compilation message

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

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 2 ms 1360 KB Output is correct
6 Correct 2 ms 1532 KB Output is correct
7 Correct 2 ms 1360 KB Output is correct
8 Correct 2 ms 1360 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 3 ms 1628 KB Output is correct
11 Correct 3 ms 1616 KB Output is correct
12 Correct 3 ms 1668 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 2 ms 1360 KB Output is correct
6 Correct 2 ms 1532 KB Output is correct
7 Correct 2 ms 1360 KB Output is correct
8 Correct 2 ms 1360 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 3 ms 1628 KB Output is correct
11 Correct 3 ms 1616 KB Output is correct
12 Correct 3 ms 1668 KB Output is correct
13 Correct 6 ms 7760 KB Output is correct
14 Correct 8 ms 9976 KB Output is correct
15 Correct 83 ms 25416 KB Output is correct
16 Correct 9 ms 8016 KB Output is correct
17 Correct 19 ms 11716 KB Output is correct
18 Correct 26 ms 9288 KB Output is correct
19 Correct 102 ms 27776 KB Output is correct
20 Correct 81 ms 21832 KB Output is correct
21 Correct 53 ms 16712 KB Output is correct
22 Correct 58 ms 17480 KB Output is correct
23 Correct 24 ms 19024 KB Output is correct
24 Correct 148 ms 30024 KB Output is correct
25 Correct 111 ms 23880 KB Output is correct
26 Correct 122 ms 27208 KB Output is correct
27 Correct 137 ms 29512 KB Output is correct