#806087 (C++17) No.122 傾向と対策：門松列（その３）

提出ソース
結果

問題	No.122 傾向と対策：門松列（その３）
ユーザー	ytqm3
提出日時	2022-10-11 16:39:25
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	149 ms / 5,000 ms
コード長	11,550 bytes
コンパイル時間	5,288 ms
コンパイル使用メモリ	287,576 KB
実行使用メモリ	27,520 KB
最終ジャッジ日時	2024-06-25 11:51:56
合計ジャッジ時間	6,917 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	117 ms 27,392 KB
testcase_01	AC	121 ms 27,468 KB
testcase_02	AC	149 ms 27,516 KB
testcase_03	AC	132 ms 27,520 KB
testcase_04	AC	119 ms 27,488 KB
testcase_05	AC	146 ms 27,520 KB
testcase_06	AC	115 ms 27,520 KB
testcase_07	AC	113 ms 27,368 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif

namespace ttl {

    using namespace std;
    using f80 = long double;
    using i64 = int64_t;
    using u64 = uint64_t;

    template<int mod> struct mymodint {
        i64 vl;
        static constexpr i64 get_mod() { return mod; }
        i64 val() { return vl; }
        mymodint(i64 vl_ = 0) :vl(vl_% mod) {}
        mymodint operator-() { return (vl == 0) ? 0 : mod - vl; }
        mymodint operator+(mymodint rhs) { return mymodint(*this) += rhs; }
        mymodint operator-(mymodint rhs) { return mymodint(*this) -= rhs; }
        mymodint operator*(mymodint rhs) { return mymodint(*this) *= rhs; }
        mymodint operator/(mymodint rhs) { return mymodint(*this) /= rhs; }
        mymodint pow(i64 rhs) {
            mymodint res = 1, now = (*this);
            while (rhs) {
                res *= ((rhs & 1) ? now : 1), now *= now, rhs >>= 1;
            }
            return res;
        }
        mymodint& operator+=(mymodint rhs) {
            vl += rhs.vl, vl -= ((vl >= mod) ? mod : 0);
            return (*this);
        }
        mymodint& operator-=(mymodint rhs) {
            vl += ((vl < rhs.vl) ? mod : 0), vl -= rhs.vl;
            return (*this);
        }
        mymodint& operator*=(mymodint rhs) {
            vl = vl * rhs.vl % mod;
            return (*this);
        }
        mymodint& operator/=(mymodint rhs) { return (*this) *= rhs.pow(mod - 2); }
        bool operator==(mymodint rhs) { return vl == rhs.vl; }
        bool operator!=(mymodint rhs) { return vl != rhs.vl; }
    };

    template<u64 mod> using modint =
#if __has_include(<atcoder/all>)
        atcoder::static_modint<mod>;
#else
        mymodint<mod>;
#endif

    template<int mod> std::ostream& operator<<(std::ostream& os, modint<mod> x) {
        return os << (x.val());
    }
    template<int mod> std::istream& operator>>(std::istream& is, modint<mod>& x) {
        i64 t;
        is >> t, x = t;
        return is;
    }

    template<class T> void scn_(T& a) { cin >> a; }
    template<class T, class U> void scn_(pair<T, U>& a) { scn_(a.first), scn_(a.second); }
    template<class T> void scn_(vector<T>& a) {
        for (auto& v : a) {
            scn_(v);
        }
    }
    template<class T> void scn_(vector<vector<T>>& a) {
        for (auto& v : a) {
            for (auto& u : v) {
                cin >> u;
            }
        }
    }
    void scn() {}
    template<class T, class... Args> void scn(T& n, Args&... args) { scn_(n), scn(args...); }
    template<class T> void prt_(T a) { cout << a; }
    template<class T, class U> void prt_(pair<T, U> a) { cout << "{" << a.first << ", " << a.second << "}"; }
    void prt_(f80 a) { printf("%.15Lf", a); }
    template<class T> void prt(vector<T> a) {
        for (size_t i = 0; i < a.size(); ++i) {
            prt_(a[i]);
            cout << " \n"[i == a.size() - 1];
        }
    }
    template<class T> void prt(vector<vector<T>> a) {
        for (auto& v : a) {
            for (size_t i = 0; i < v.size(); ++i) {
                cout << v[i] << " \n"[i == v.size() - 1];
            }
        }
    }
    template<class T> void prt(T a) { prt_(a), cout << "\n"; }
    template<class T, class... Args> void prt(T a, Args... args) { prt_(a), cout << " ", prt(args...); }

    template<class Head, class... Tail> struct multi_dim_vector { using type = vector<typename multi_dim_vector<Tail...>::type>; };
    template<class T> struct multi_dim_vector<T> { using type = T; };
    template<class T, class Arg> vector<T> mvec(int n, Arg&& arg) { return vector<T>(n, arg); }
    template<class T, class... Args> class multi_dim_vector<Args..., T>::type mvec(int n, Args&&... args) {
        return typename multi_dim_vector<Args..., T>::type(n, mvec<T>(args...));
    }

    template<class T> void rev(T& a) { reverse(a.begin(), a.end()); }
    template<class T> void srt(T& a) { sort(a.begin(), a.end()); }
    template<class T> void rsrt(T& a) { sort(a.rbegin(), a.rend()); }
    template<class T> T revd(T a) {
        reverse(a.begin(), a.end());
        return a;
    }
    template<class T> T srtd(T a) {
        sort(a.begin(), a.end());
        return a;
    }
    template<class T> T rsrtd(T a) {
        sort(a.rbegin(), a.rend());
        return a;
    }
    template<class T> T summ(vector<T> a) { return accumulate(a.begin(), a.end(), T(0)); }
    template<class T> T maxi(vector<T> a) { return *max_element(a.begin(), a.end()); }
    template<class T> T mini(vector<T> a) { return *min_element(a.begin(), a.end()); }
    template<class T> void chmx(T& a, T b) { a = max(a, b); }
    template<class T> void chmn(T& a, T b) { a = min(a, b); }
    i64 ppcnt(u64 k) { return __builtin_popcountll(k); }
    template<class T> T powe(T a, i64 n) {
        T res = 1;
        while (n) {
            if (n & 1) { res *= a; }
            a *= a;
            n /= 2;
        }
        return res;
    }
    i64 powe(i64 a, i64 n, i64 m) {
        i64 res = 1;
        while (n) {
            if (n & 1) { res = res * a % m; }
            a = a * a % m;
            n /= 2;
        }
        return res;
    }
    template<class T> void zip(vector<T>& a) {
        auto b = srtd(a);
        b.erase(unique(b.begin(), b.end()), b.end());
        map<T, int> mp;
        for (int i = 0; i < b.size(); ++i) {
            mp[b[i]] = i;
        }
        for (auto& v : a) {
            v = mp[v];
        }
    }
    i64 sqrf(i64 n) {
        i64 ok = 0, ng = 1e9 + 5;
        while (std::abs(ok - ng) > 1) {
            i64 mid = (ok + ng) / 2;
            (mid * mid <= n ? ok : ng) = mid;
        }
        return ok;
    }
    i64 sqrc(i64 n) {
        i64 ok = 1e9 + 5, ng = 0;
        while (std::abs(ok - ng) > 1) {
            i64 mid = (ok + ng) / 2;
            (mid * mid >= n ? ok : ng) = mid;
        }
        return ok;
    }
    i64 dvf(i64 a, i64 b) {
        if (b < 0) { a *= -1, b *= -1; }
        if (a < 0) { return -(-a + b - 1) / b; }
        return a / b;
    }
    i64 dvc(i64 a, i64 b) {
        if (b < 0) { a *= -1, b *= -1; }
        if (a < 0) { return -(-a) / b; }
        return (a + b - 1) / b;
    }
    vector<int> bfs(vector<vector<int>> G, int v) {
        int N = G.size();
        vector<int> dst(N, -1);
        queue<int> q;
        dst[v] = 0;
        q.emplace(v);
        while (q.size()) {
            int t = q.front();
            q.pop();
            for (auto u : G[t]) {
                if (dst[u] == -1) {
                    dst[u] = dst[t] + 1;
                    q.emplace(u);
                }
            }
        }
        return dst;
    }
    vector<i64> dijkstra(vector<vector<pair<int, i64>>>& G, int s) {
        int N = G.size();
        vector<i64> dst(N, 1e18);
        dst[s] = 0;
        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
        pq.emplace(0, s);
        vector<int> f(N);
        while (pq.size()) {
            auto [t, u] = pq.top();
            pq.pop();
            if (f[u]) { continue; }
            f[u] = 1;
            for (auto [v, w] : G[u]) {
                if (dst[v] > dst[u] + w) {
                    dst[v] = dst[u] + w;
                    pq.emplace(dst[v], v);
                }
            }
        }
        return dst;
    }
    vector<pair<i64, i64>> pfct(i64 n) {
        vector<pair<i64, i64>> res;
        for (i64 i = 2; i * i <= n; ++i) {
            if (n % i != 0) { continue; }
            i64 ex = 0;
            while (n % i == 0) { ex++, n /= i; }
            res.emplace_back(i, ex);
        }
        if (n != 1) { res.emplace_back(n, 1); }
        return res;
    }
    vector<i64> ediv(i64 n) {
        vector<i64> res;
        for (i64 i = 1; i * i <= n; ++i) {
            if (n % i != 0) { continue; }
            res.emplace_back(i);
            if (i * i != n) { res.emplace_back(n / i); }
        }
        srt(res);
        return res;
    }
    template<class T> struct csm2d {
        int n, m;
        vector<vector<T>> a, c;
        csm2d(vector<vector<T>> a_) :n(a_.size()), m(a_[0].size()), a(a_) {
            auto b = mvec<T>(n, m + 1, 0);
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    b[i][j + 1] = b[i][j] + a[i][j];
                }
            }
            c = mvec<T>(n + 1, m + 1, 0);
            for (int j = 0; j < m + 1; ++j) {
                for (int i = 0; i < n; ++i) {
                    c[i + 1][j] = c[i][j] + b[i][j];
                }
            }
        }
        T operator()(int p, int q, int r, int s) {
            return c[p][r] - c[p][s] - c[q][r] + c[q][s];
        }
    };
    template<class T> auto runlng(T a) -> vector<pair<typename decltype(a)::value_type, i64>> {
        int n = a.size();
        vector<pair<typename decltype(a)::value_type, i64>> res;
        typename decltype(a)::value_type now = a[0];
        i64 l = 1;
        for (int i = 1; i < n; ++i) {
            if (a[i - 1] == a[i]) { l++; }
            else {
                res.emplace_back(now, l);
                now = a[i], l = 1;
            }
        }
        res.emplace_back(now, l);
        return res;
    }
    template<class T> struct cmb {
        vector<T> fac, ifac;
        cmb(int mx = 3000000) :fac(mx + 1, 1), ifac(mx + 1, 1) {
            for (int i = 1; i <= mx; ++i) { fac[i] = fac[i - 1] * i; }
            ifac[mx] /= fac[mx];
            for (int i = mx; i > 0; --i) { ifac[i - 1] = ifac[i] * i; }
        }
        T operator()(i64 n, i64 k) {
            if (n < 0 || k < 0 || n < k) { return 0; }
            return fac[n] * ifac[k] * ifac[n - k];
        }
        T f(i64 n) {
            return n < 0 ? T(0) : fac[n];
        }
        T fi(i64 n) {
            return n < 0 ? T(0) : ifac[n];
        }
    };

}

using namespace ttl;

int main() {
    constexpr int mod = 1000000007;
    using mint = modint<mod>;
    cmb<mint> Cb;
    int T = 7;
    vector<int> p(T), q(T);
    for (int i = 0; i < T; ++i) {
        scn(p[i], q[i]);
    }
    vector<int> r(T), s(T);
    for (int i = 0; i < T; i += 2) {
        r[i / 2] = p[i], s[i / 2] = q[i];
    }
    for (int i = 1; i < T; i += 2) {
        r[T / 2 + 1 + i / 2] = p[i], s[T / 2 + 1 + i / 2] = q[i];
    }
    auto dp = mvec<mint>(T, 20005, 0);
    auto sol = [&](vector<int> a, vector<int> b) {
        for (int i = 0; i < T; ++i) { for (int j = 0; j <= 20000; ++j) { dp[i][j] = 0; } }
        for (int j = a[0]; j <= b[0]; ++j) {
            dp[0][j] = 1;
        }
        for (int i = 0; i < T - 1; ++i) {
            mint sm = 0;
            for (int j = 0; j <= 20000; ++j) {
                if (a[i + 1] <= j && j <= b[i + 1]) {
                    dp[i + 1][j] += sm;
                }
                sm += dp[i][j];
            }
        }
        return summ(dp[T - 1]);
    };
    vector<int> P(T / 2 + 1), Q(T / 2);
    iota(P.begin(), P.end(), 0);
    iota(Q.begin(), Q.end(), 0);
    mint ans = 0;
    do {
        do {
            vector<int> t(T), u(T);
            for (int i = 0; i < T / 2 + 1; ++i) {
                t[i] = r[P[i]], u[i] = s[P[i]];
            }
            for (int i = 0; i < T / 2; ++i) {
                t[i + T / 2 + 1] = r[Q[i] + T / 2 + 1], u[i + T / 2 + 1] = s[Q[i] + T / 2 + 1];
            }
            ans += sol(t, u);
            rev(t), rev(u);
            ans += sol(t, u);
        } while (next_permutation(Q.begin(), Q.end()));
    } while (next_permutation(P.begin(), P.end()));
    prt(ans);
}
yukicoder

結果

テストケース

ソースコード
