結果
問題 | No.122 傾向と対策:門松列(その3) |
ユーザー | maine_honzuki |
提出日時 | 2020-05-17 17:19:56 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
11,004 KB |
testcase_01 | AC | 13 ms
10,880 KB |
testcase_02 | AC | 12 ms
10,956 KB |
testcase_03 | AC | 11 ms
10,952 KB |
testcase_04 | AC | 12 ms
11,008 KB |
testcase_05 | AC | 12 ms
10,960 KB |
testcase_06 | AC | 11 ms
10,912 KB |
testcase_07 | AC | 13 ms
10,960 KB |
ソースコード
#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; }