Submission #1319992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319992		pobe	Tents (JOI18_tents)	C++20	48 / 100	2103 ms	213364 KiB

tents

#include <bits/stdc++.h>

#define int long long
using namespace std;
int mod = 1e9 + 7;
struct mint {
    int v = 0;
    mint(int nv = 0) {
        v = nv;
        if (v >= mod || v < 0) {
            v = (v % mod + mod) % mod;
        }
    }
};
mint operator+(mint v1, mint v2) {
    return (v1.v + v2.v >= mod ? v1.v + v2.v - mod : v1.v + v2.v);
}
void operator +=(mint &v1, mint v2) {
    v1 = v1 + v2;
}
mint operator-(mint v1, mint v2) {
    return (v1.v - v2.v < 0 ? v1.v - v2.v + mod : v1.v - v2.v);
}
mint operator *(mint v1, mint v2) {
    return 1LL * v1.v * v2.v % mod;
}
mint exp(mint a, int b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2 == 1) {
        return a * exp(a, b - 1);
    }
    return exp(a * a, b / 2);
}
const int k = 5e4;
mint f[k], rf[k];
mint a(int n, int i, int j) {
    if (n < i + j) {
        return 0;
    }
    return f[n] * rf[n - (i + j)];
}
void solve() {
    f[0] = 1;
    rf[0] = 1;
    for (int i = 1; i < k; ++i) {
        f[i] = f[i - 1] * i;
        rf[i] = exp(f[i], mod - 2);
    }
    int n, m;
    cin >> n >> m;
    vector <vector <mint>> dp(2 * max(m, n) + 1, vector <mint> (2 * max(m, n) + 1));
    auto last = dp;
    last[0][0] = 1;
    mint dwa = exp(2, mod - 2);
    vector <mint> chetire(dp.size()* 2);
    chetire[0] = 1;
    for (int i = 1; i < chetire.size(); ++i) {
        chetire[i] = chetire[i - 1] * 4;
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < dp.size(); ++j) {
            for (int f = 0; f < dp.size(); ++f) {
                dp[j][f] += last[j][f];
                if (f) {
                    dp[j][f] += last[j][f - 1];
                }
                if (j > 1) {
                    dp[j][f] += last[j - 2][f] * dwa;
                }
                if (f != dp.size() - 1 && j > 0) {
                    dp[j][f] += last[j - 1][f + 1] * (f + 1);
                }
            }
        }
        swap(last, dp);
        for (int j = 0; j < dp.size(); ++j) {
            for (int f = 0; f < dp.size(); ++f) {
//                cout << last[j][f].v << " ";
                dp[j][f] = 0;
            }
//            cout << '\n';
        }
//        cout << '\n';
    }
    swap(last, dp);
    mint ans = 0;
    for (int i = 0; i < dp.size(); ++i) {
        for (int j = 0; j < dp.size(); ++j) {
            if ((i) || (j)) {
                if (dp[i][j].v != 0) {
                    ans += dp[i][j] * a(n, i, j) * chetire[j];
//                    if ((dp[i][j] * a(n, i, j) * exp(4, j)).v != 0) {
//                        cout << (dp[i][j] * a(n, i, j) * exp(4, j)).v << " " << i << " " << j << '\n';
//                        cout << dp[i][j].v << " " << a(n, i, j).v << ' ' << exp(4, j).v << '\n';
//                        cout << '\n';

//                    }
                }
            }
        }
    }
    cout << ans.v << '\n';
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
}

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