結果

問題 No.122 傾向と対策：門松列（その３）
コンテスト
ユーザー maine_honzuki
提出日時 2020-05-17 17:19:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 13 ms / 5,000 ms
コード長 4,076 bytes
コンパイル時間 1,659 ms
コンパイル使用メモリ 170,660 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-09-25 10:14:42
合計ジャッジ時間 2,361 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const ll MOD = 1e9 + 7;

template <uint MD>
struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
    friend istream& operator>>(istream& is, M& r) { return is >> r.v; }
};
using Mint = ModInt<MOD>;

int main() {
    int a_min[5] = {}, a_max[5] = {}, b_min[4] = {}, b_max[4] = {};
    for (int i = 0; i < 3; i++) {
        cin >> a_min[i] >> a_max[i] >> b_min[i] >> b_max[i];
    }
    cin >> a_min[3] >> a_max[3];

    Mint a_cnt_high_sum[1 << 4][20010] = {}, a_cnt_high_just[1 << 4][20010] = {};
    a_cnt_high_sum[0][0] = 1;

    for (int i = 1; i <= 20000; i++) {
        for (int bit = 0; bit < 1 << 4; bit++) {
            for (int j = 0; j < 4; j++) {
                if (bit & (1 << j) && i >= a_min[j] && i <= a_max[j]) {
                    a_cnt_high_just[bit][i] += a_cnt_high_sum[bit ^ (1 << j)][i - 1];
                }
            }
            a_cnt_high_sum[bit][i] = a_cnt_high_sum[bit][i - 1] + a_cnt_high_just[bit][i];
        }
    }


    Mint b_cnt_high_sum[1 << 3][20010] = {}, b_cnt_high_just[1 << 3][20010] = {};
    b_cnt_high_sum[0][0] = 1;

    for (int i = 1; i <= 20000; i++) {
        for (int bit = 0; bit < 1 << 3; bit++) {
            for (int j = 0; j < 3; j++) {
                if (bit & (1 << j) && i >= b_min[j] && i <= b_max[j]) {
                    b_cnt_high_just[bit][i] += b_cnt_high_sum[bit ^ (1 << j)][i - 1];
                }
            }
            b_cnt_high_sum[bit][i] = b_cnt_high_sum[bit][i - 1] + b_cnt_high_just[bit][i];
        }
    }


    Mint a_cnt_low_sum[1 << 4][20010] = {}, a_cnt_low_just[1 << 4][20010] = {};
    a_cnt_low_sum[0][20001] = 1;

    for (int i = 20000; i >= 0; i--) {
        for (int bit = 0; bit < 1 << 4; bit++) {
            for (int j = 0; j < 4; j++) {
                if (bit & (1 << j) && i >= a_min[j] && i <= a_max[j]) {
                    a_cnt_low_just[bit][i] += a_cnt_low_sum[bit ^ (1 << j)][i + 1];
                }
            }
            a_cnt_low_sum[bit][i] = a_cnt_low_sum[bit][i + 1] + a_cnt_low_just[bit][i];
        }
    }

    Mint b_cnt_low_sum[1 << 3][20010] = {}, b_cnt_low_just[1 << 3][20010]{};
    b_cnt_low_sum[0][20001] = 1;

    for (int i = 20000; i >= 0; i--) {
        for (int bit = 0; bit < 1 << 3; bit++) {
            for (int j = 0; j < 3; j++) {
                if (bit & (1 << j) && i >= b_min[j] && i <= b_max[j]) {
                    b_cnt_low_just[bit][i] += b_cnt_low_sum[bit ^ (1 << j)][i + 1];
                }
            }
            b_cnt_low_sum[bit][i] = b_cnt_low_sum[bit][i + 1] + b_cnt_low_just[bit][i];
        }
    }

    Mint ans = 0;
    for (int i = 0; i <= 20000; i++) {
        ans += a_cnt_high_sum[(1 << 4) - 1][i] * b_cnt_low_just[(1 << 3) - 1][i + 1];
        ans += a_cnt_low_sum[(1 << 4) - 1][i + 1] * b_cnt_high_just[(1 << 3) - 1][i];
    }

    cout << ans << endl;
}
0