結果

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

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
2015 AC 12 ms
10,748 KB
happy AC 16 ms
10,796 KB
max AC 16 ms
10,796 KB
new AC 12 ms
10,772 KB
superrich AC 16 ms
10,824 KB
year AC 12 ms
10,768 KB
yukicoder AC 12 ms
10,732 KB
zero AC 12 ms
10,732 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