Submission #727413

#	Time	Username	Problem	Language	Result	Execution time	Memory
727413		model_code	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	100 / 100	6239 ms	3980 KiB

festival2

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 27 / 27
• Subtask 4: 14 / 14
• Subtask 5: 36 / 36
• Subtask 6: 13 / 13