oj.uz

Submission #727413

# Submission time Handle Problem Language Result Execution time Memory
727413 2023-04-20T15:49:06 Z model_code Festivals in JOI Kingdom 2 (JOI23_festival2) C++17
100 / 100
 6239 ms 3980 KB 
#include<bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for (ll i = ll(n) - 1; i >= 0; i--)
#define SZ(a) int(a.size())

using namespace std;

using ll = long long;

class mint {
    ll x;
    static int mod;
public:
    static void set_mod(int _mod) { mod = _mod; }
    
    mint(ll x = 0) : x((x % mod + mod) % mod) { assert(mod > 0); }
    
    constexpr int val() const { return x; }
    
    mint &operator+=(const mint &a) {
        if ((x += a.val()) >= mod) x -= mod;
        return *this;
    }
    
    mint &operator-=(const mint &a) {
        if ((x += mod - a.val()) >= mod) x -= mod;
        return *this;
    }
    
    mint &operator*=(const mint &a) {
        (x *= a.val()) %= mod;
        return *this;
    }
    
    mint operator+(const mint &a) const {
        mint res(*this);
        return res += a;
    }
    
    mint operator-(const mint &a) const {
        mint res(*this);
        return res -= a;
    }
    
    mint operator*(const mint &a) const {
        mint res(*this);
        return res *= a;
    }
    
    mint pow(ll t) const {
        mint res = 1, a(*this);
        while (t > 0) {
            if (t & 1) res *= a;
            t >>= 1;
            a *= a;
        }
        return res;
    }
    
    mint inv() const { return pow(mod - 2); }
};

int mint::mod = 0;

using vm = vector<mint>;

vm karatsuba(const vm &f, const vm &g) {
    int n = SZ(f);
    int m = SZ(g);
    if (!n or !m) return {};
    if (min(n, m) <= 40) {
        vm res(n + m - 1);
        rep(i, n) rep(j, m) res[i + j] += f[i] * g[j];
        return res;
    }
    int a = max(n, m) / 2;
    vm f0(f.begin(), f.begin() + min(a, n));
    vm f1(f.begin() + min(a, n), f.end());
    vm g0(g.begin(), g.begin() + min(a, m));
    vm g1(g.begin() + min(a, m), g.end());
    vm h0 = karatsuba(f0, g0);
    vm h2 = karatsuba(f1, g1);
    vm h1;
    {
        vm df(max(SZ(f0), SZ(f1)));
        rep(i, SZ(f0)) df[i] += f0[i];
        rep(i, SZ(f1)) df[i] -= f1[i];
        vm dg(max(SZ(g0), SZ(g1)));
        rep(i, SZ(g0)) dg[i] -= g0[i];
        rep(i, SZ(g1)) dg[i] += g1[i];
        h1 = karatsuba(df, dg);
    }
    if (SZ(h1) < max(SZ(h0), SZ(h2))) h1.resize(max(SZ(h0), SZ(h2)));
    rep(i, SZ(h0)) h1[i] += h0[i];
    rep(i, SZ(h2)) h1[i] += h2[i];
    vm res(n + m - 1);
    rep(i, SZ(h0)) res[i] += h0[i];
    rep(i, SZ(h1)) res[i + a] += h1[i];
    rep(i, SZ(h2)) res[i + a * 2] += h2[i];
    return res;
}

int main() {
    int n, p;
    cin >> n >> p;
    mint::set_mod(p);
    
    vm fact(2 * n + 10, 1);
    vm ifact(2 * n + 10);
    rep2(i, 1, SZ(fact)) fact[i] = fact[i - 1] * i;
    ifact.back() = fact.back().inv();
    rrep(i, SZ(fact) - 1) ifact[i] = ifact[i + 1] * (i + 1);
    
    // A : 正しい貪欲で選ぶ区間の集合　B : 嘘貪欲で選ぶ区間の集合
    // |A| = |B| のものを数える
    // A, B に含まれる区間を後ろから 1 çµ„ãšã¤åŠ ãˆã¦ã„ã (é–“ã«ã‚ã‚‹åŒºé–“ã‚‚åŒæ™‚ã«åŠ ãˆã‚‹)
    // dp[i][j]
    // i : åŠ ãˆãŸåŒºé–“ã®å€‹æ•°
    // j : A, B ã«å«ã¾ã‚Œã‚‹åŒºé–“ã®ã†ã¡æœ€å¾Œã«åŠ ãˆãŸçµ„ãŒåˆ¥ã€…ã®åŒºé–“ã‹ã©ã†ã‹
    vector dp(n + 1, vm(2));
    dp[1][0] = 1;
    if (n >= 2) dp[2][1] = 1;
    
//    O(N^2) での DP (subtask 5)

//    rep2(i, 1, n + 1) {
//        // 0 -> 0
//        if (i + 1 <= n) {
//            mint now = dp[i][0];
//            rep(j, n - i) {
//                dp[i + 1 + j][0] += now;
//                now *= 2 * i - 1 + j;
//            }
//        }
//        // 0 -> 1
//        if (i + 2 <= n) {
//            mint now = dp[i][0];
//            rep(j, n - i - 1) {
//                dp[i + 2 + j][1] += now * (j + 1);
//                now *= 2 * i - 1 + j;
//            }
//        }
//        // 1 -> 0
//        if (i + 1 <= n) {
//            mint now = dp[i][1];
//            rep(j, n - i) {
//                dp[i + 1 + j][0] += now * (j + 1);
//                now *= 2 * i - 2 + j;
//            }
//        }
//        // 1 -> 1
//        if (i + 2 <= n) {
//            mint now = dp[i][1];
//            rep(j, n - i - 1) {
//                dp[i + 2 + j][1] += now * (j + 2) * (j + 1);
//                now *= 2 * i - 2 + j;
//            }
//        }
//    }

//  O(N^1.59) での DP (満点解)
    
    // [l, m) から [m, r) への遷移をまとめて行う
    auto induce = [&](int l, int m, int r) -> void {
        vm f(m - l), g(r - l - 1);
        // 0 -> 0
        {
            rep2(i, l, m) f[m - 1 - i] = dp[i][0] * ifact[2 * i - 2];
            rep2(i, l + m, m + r - 1) g[i - (l + m)] = fact[i - 3];
            vm h = karatsuba(f, g);
            rep2(i, m, r) dp[i][0] += h[m - l - 1 + i - m];
        }
        // 0 -> 1
        if (m - l >= 2) {
            rep2(i, l, m - 1) f[m - 1 - i] = dp[i][0] * ifact[2 * i - 2];
            f[0] = 0;
            rep2(i, l + m, m + r - 1) g[i - (l + m)] = fact[i - 4];
            vm h = karatsuba(f, g);
            rep2(i, m, r) dp[i][1] += h[m - l - 1 + i - m] * (i - 1);
            
            rep2(i, l, m - 1) f[m - 1 - i] *= -i;
            h = karatsuba(f, g);
            rep2(i, m, r) dp[i][1] += h[m - l - 1 + i - m];
        }
        {
            int i = m - 1;
            rep2(j, m + 1, r) {
                dp[j][1] += dp[i][0] * (j - i - 1) * fact[i + j - 4] * ifact[2 * i - 2];
            }
        }
        // 1 -> 0
        {
            rep2(i, l, m) f[m - 1 - i] = dp[i][1] * (i >= 2 ? ifact[2 * i - 3] : 0);
            rep2(i, l + m, m + r - 1) g[i - (l + m)] = (i >= 4 ? fact[i - 4] : 0);
            vm h = karatsuba(f, g);
            rep2(i, m, r) dp[i][0] += h[m - l - 1 + i - m] * i;
            
            rep2(i, l, m) f[m - 1 - i] *= -i;
            h = karatsuba(f, g);
            rep2(i, m, r) dp[i][0] += h[m - l - 1 + i - m];
        }
        // 1 -> 1
        if (m - l >= 2) {
            rep2(i, l, m - 1) f[m - 1 - i] = dp[i][1] * (i >= 2 ? ifact[2 * i - 3] : 0);
            f[0] = 0;
            rep2(i, l + m, m + r - 1) g[i - (l + m)] = (i >= 5 ? fact[i - 5] : 0);
            vm h = karatsuba(f, g);
            rep2(i, m, r) dp[i][1] += h[m - l - 1 + i - m] * i * (i - 1);
            
            rep2(i, l, m - 1) f[m - 1 - i] *= i;
            h = karatsuba(f, g);
            rep2(i, m, r) dp[i][1] += h[m - l - 1 + i - m] * (-2 * i);
            
            rep2(i, l, m - 1) f[m - 1 - i] *= i + 1;
            h = karatsuba(f, g);
            rep2(i, m, r) dp[i][1] += h[m - l - 1 + i - m];
        }
        {
            int i = m - 1;
            rep2(j, m + 1, r) {
                dp[j][1] += dp[i][1] * (j * (j - 1) - 2 * i * j + i * (i + 1)) * fact[i + j - 5] * ifact[2 * i - 3];
            }
        }
    };
    
    auto solve = [&](auto &solve, int l, int r) -> void {
        assert(l < r);
        if (r - l == 1) return;
        int m = (l + r) / 2;
        solve(solve, l, m);
        induce(l, m, r);
        solve(solve, m, r);
    };
    solve(solve, 1, n + 1);
    
    mint ans = 1;
    rep(i, n) ans *= 2 * i + 1;
    rep2(i, 1, n + 1) {
        ans -= dp[i][0] * fact[n + i - 2] * ifact[2 * i - 2];
        if (i >= 2) ans -= dp[i][1] * (n - i + 1) * fact[n + i - 3] * ifact[2 * i - 3];
    }
    cout << ans.val() << endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 300 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 7 ms 368 KB Output is correct
20 Correct 7 ms 368 KB Output is correct
21 Correct 7 ms 360 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 2 ms 212 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 7 ms 368 KB Output is correct
20 Correct 7 ms 368 KB Output is correct
21 Correct 7 ms 360 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 2 ms 212 KB Output is correct
24 Correct 285 ms 824 KB Output is correct
25 Correct 287 ms 832 KB Output is correct
26 Correct 278 ms 832 KB Output is correct
27 Correct 9 ms 304 KB Output is correct
28 Correct 74 ms 468 KB Output is correct
29 Correct 59 ms 448 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 304 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 7 ms 368 KB Output is correct
20 Correct 7 ms 368 KB Output is correct
21 Correct 7 ms 360 KB Output is correct
22 Correct 1 ms 300 KB Output is correct
23 Correct 2 ms 212 KB Output is correct
24 Correct 285 ms 824 KB Output is correct
25 Correct 287 ms 832 KB Output is correct
26 Correct 278 ms 832 KB Output is correct
27 Correct 9 ms 304 KB Output is correct
28 Correct 74 ms 468 KB Output is correct
29 Correct 59 ms 448 KB Output is correct
30 Correct 6094 ms 3940 KB Output is correct
31 Correct 6239 ms 3968 KB Output is correct
32 Correct 6126 ms 3980 KB Output is correct
33 Correct 3509 ms 3104 KB Output is correct
34 Correct 805 ms 1420 KB Output is correct
35 Correct 736 ms 1304 KB Output is correct