oj.uz

답안 #403026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403026 2021-05-12T16:47:18 Z 12tqian Tents (JOI18_tents) C++17
100 / 100
 325 ms 35904 KB 
#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 3005;
const int P = 1e9 + 7;

int mpow(ll b, ll e) {
    ll r = 1;
    while (e) {
        if (e & 1) {
            r *= b;
            r %= P;
        }
        b *= b;
        b %= P;
        e >>= 1;
    }
    return r;
}
int minv(ll b) { return mpow(b, P - 2); }
int add(int x, int y) { x += y; if (x >= P) x -= P; return x; }
int sub(int x, int y) { x -= y; if (x < 0) x += P; return x; }
int mult(int x, int y) { return 1LL * x * y % P; }
int madd(int&x, int y) { return x = add(x, y); }
int mmult(int& x, int y) { return x = mult(x, y); }
int msub(int& x, int y) { return x = sub(x, y); }
int fact[N], ifact[N];

int dp[N][N];

int C(int x, int y) { 
    if (x < y) return 0;
    return mult(fact[x], mult(ifact[y], ifact[x - y]));
}

int solve(int n, int m) {
    auto& res = dp[n][m];
    if (res != -1) return res;
    res = 1; // no more pairs
    if (n == 0 || m == 0) {
        return res;
    }
    { // first thing isn't paired
        madd(res, sub(solve(n - 1, m), 1));
    }
    if (m >= 2) { // first thing is double paired
        madd(res, mult(C(m, 2), solve(n - 1, m - 2)));
    }
    if (n >= 2) { // first thing is double paired with same side
        madd(res, mult(mult(n - 1, m), solve(n - 2, m - 1)));
    }
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    fact[0] = 1;
    f1r(i, 1, N) fact[i] = mult(fact[i - 1], i);
    ifact[N - 1] = minv(fact[N - 1]);
    f0r(i, N) f0r(j, N) dp[i][j] = -1;
    for (int i = N - 2; i >= 0; i--) ifact[i] = mult(ifact[i + 1], i + 1);
    int n, m; cin >> n >> m;
    int ans = 0;
    f0r(i, min(m, n) + 1) { // number of singles
        int res = mult(fact[i], mult(C(n, i), C(m, i)));
        mmult(res, mpow(4, i));
        int a = n - i;
        int b = m - i;
        madd(ans, mult(res, solve(a, b))); 
    }
    msub(ans, 1);
    cout << ans << '\n';
    return 0;
}

/**
 * each vertex has at most degree 2
 * no path of length greater than 3
 * 4^(number of single components)
 * 
 */

Subtask #1
48.0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 35660 KB Output is correct
2 Correct 16 ms 35592 KB Output is correct
3 Correct 16 ms 35644 KB Output is correct
4 Correct 16 ms 35676 KB Output is correct
5 Correct 16 ms 35588 KB Output is correct
6 Correct 16 ms 35684 KB Output is correct
7 Correct 16 ms 35556 KB Output is correct
8 Correct 16 ms 35660 KB Output is correct
9 Correct 16 ms 35668 KB Output is correct
10 Correct 17 ms 35604 KB Output is correct
11 Correct 16 ms 35660 KB Output is correct
12 Correct 18 ms 35680 KB Output is correct

Subtask #2
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 35660 KB Output is correct
2 Correct 16 ms 35592 KB Output is correct
3 Correct 16 ms 35644 KB Output is correct
4 Correct 16 ms 35676 KB Output is correct
5 Correct 16 ms 35588 KB Output is correct
6 Correct 16 ms 35684 KB Output is correct
7 Correct 16 ms 35556 KB Output is correct
8 Correct 16 ms 35660 KB Output is correct
9 Correct 16 ms 35668 KB Output is correct
10 Correct 17 ms 35604 KB Output is correct
11 Correct 16 ms 35660 KB Output is correct
12 Correct 18 ms 35680 KB Output is correct
13 Correct 17 ms 35624 KB Output is correct
14 Correct 15 ms 35788 KB Output is correct
15 Correct 213 ms 35872 KB Output is correct
16 Correct 19 ms 35680 KB Output is correct
17 Correct 38 ms 35820 KB Output is correct
18 Correct 62 ms 35660 KB Output is correct
19 Correct 246 ms 35788 KB Output is correct
20 Correct 189 ms 35848 KB Output is correct
21 Correct 119 ms 35788 KB Output is correct
22 Correct 136 ms 35868 KB Output is correct
23 Correct 89 ms 35788 KB Output is correct
24 Correct 325 ms 35888 KB Output is correct
25 Correct 240 ms 35880 KB Output is correct
26 Correct 276 ms 35880 KB Output is correct
27 Correct 309 ms 35904 KB Output is correct