結果

問題 No.122 傾向と対策:門松列(その3)
ユーザー fumiphys
提出日時 2019-09-12 02:09:40
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 18 ms
コード長 4,584 Byte
コンパイル時間 1,407 ms
使用メモリ 9,032 KB
最終ジャッジ日時 2019-09-12 02:09:42

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
2015 AC 16 ms
9,028 KB
happy AC 16 ms
9,028 KB
max AC 18 ms
9,024 KB
new AC 15 ms
9,028 KB
superrich AC 15 ms
9,028 KB
year AC 18 ms
9,032 KB
yukicoder AC 16 ms
9,032 KB
zero AC 16 ms
9,016 KB
テストケース一括ダウンロード

ソースコード

diff #
// includes
#include <bits/stdc++.h>
using namespace std;

// macros
#define pb emplace_back
#define mk make_pair
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define bit(n) (1LL<<(n))
// functions
template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;}
template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;}
template <typename T> ostream &operator<<(ostream &os, const vector<T>& vec){for(int i = 0; i < vec.size(); i++){ os << vec[i]; if(i + 1 != vec.size())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << p.first << " " << p.second; return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const unordered_map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
//  types
using ll = long long int;
using P = pair<int, int>;
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1000000007;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
// io
struct fast_io{
  fast_io(){ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20);}
} fast_io_;

ll dpu1[1<<4][20010], dpu2[1<<3][20010];
ll dpd1[1<<4][20010], dpd2[1<<3][20010];

int main(int argc, char const* argv[])
{
  ll amin[7], amax[7];
  rep(i, 7)cin >> amin[i] >> amax[i];
  dpd1[0][0] = 1;
  for(int i = 1; i <= 20000; i++){
    for(int j = 0; j < bit(4); j++){
      dpd1[j][i] = dpd1[j][i-1];
      for(int k = 0; k < 4; k++){
        if((j >> k) & 1 && amin[2*k] <= i && i <= amax[2*k]){
          (dpd1[j][i] += dpd1[j - bit(k)][i-1]) %= mod;
        }
      }
    }
  }
  dpd2[0][0] = 1;
  for(int i = 1; i <= 20000; i++){
    for(int j = 0; j < bit(3); j++){
      dpd2[j][i] = dpd2[j][i-1];
      for(int k = 0; k < 3; k++){
        if((j >> k) & 1 && amin[2*k+1] <= i && i <= amax[2*k+1]){
          (dpd2[j][i] += dpd2[j - bit(k)][i-1]) %= mod;
        }
      }
    }
  }
  dpu1[0][20001] = 1;
  for(int i = 20000; i > 0; i--){
    for(int j = 0; j < bit(4); j++){
      dpu1[j][i] = dpu1[j][i+1];
      for(int k = 0; k < 4; k++){
        if((j >> k) & 1 && amin[2*k] <= i && i <= amax[2*k]){
          (dpu1[j][i] += dpu1[j - bit(k)][i+1]) %= mod;
        }
      }
    }
  }
  dpu2[0][20001] = 1;
  for(int i = 20000; i > 0; i--){
    for(int j = 0; j < bit(3); j++){
      dpu2[j][i] = dpu2[j][i+1];
      for(int k = 0; k < 3; k++){
        if((j >> k) & 1 && amin[2*k+1] <= i && i <= amax[2*k+1]){
          (dpu2[j][i] += dpu2[j - bit(k)][i+1]) %= mod;
        }
      }
    }
  }
  ll res = 0;
  for(int x = 1; x <= 20000; x++){
    ll tmp = (dpu1[15][x] - dpu1[15][x+1]) * dpd2[7][x-1] % mod;
    res = (res + tmp) % mod;
    tmp = (dpd1[15][x] - dpd1[15][x-1]) * dpu2[7][x+1] % mod;
    res = (res + tmp) % mod;
  }
  if(res < 0)res += mod;
  cout << res << endl;
  return 0;
}
0