結果

問題 No.122 傾向と対策:門松列(その3)
ユーザー fumiphys
提出日時 2019-06-14 00:01:24
言語 C++14
(gcc 8.2.0)
結果
AC  
実行時間 14 ms
コード長 5,136 Byte
コンパイル時間 1,715 ms
使用メモリ 8,916 KB
最終ジャッジ日時 2019-07-10 20:29:34

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
2015 AC 10 ms
8,916 KB
happy AC 10 ms
7,100 KB
max AC 13 ms
8,712 KB
new AC 13 ms
7,824 KB
superrich AC 11 ms
7,056 KB
year AC 14 ms
8,692 KB
yukicoder AC 9 ms
6,872 KB
zero AC 12 ms
6,872 KB
テストケース一括ダウンロード

ソースコード

diff #
// includes
#include <bits/stdc++.h>

// macros
#define ll long long int
#define pb emplace_back
#define mk make_pair
#define pq priority_queue
#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 vrep(v, i) for(int i = 0; i < (v).size(); i++)
#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 FI first
#define SE second
#define dump(a, n) for(int i = 0; i < n; i++)cout << a[i] << "\n "[i + 1 != n];
#define dump2(a, n, m) for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)cout << a[i][j] << "\n "[j + 1 != m];
#define bit(n) (1LL<<(n))
#define INT(n) int n; cin >> n;
#define LL(n) ll n; cin >> n;
#define DOUBLE(n) double n; cin >> n;
using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef complex<double> cd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

// solve
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;}

ll dp1[8][20002];
ll dp2[16][20002];
ll dp3[8][20002];
ll dp4[16][20002];

int main(int argc, char const* argv[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  std::vector<vector<int>> v(7, std::vector<int>(2, 0));
  rep(i, 7)cin >> v[i][0] >> v[i][1];
  dp1[0][20001] = 1;
  rep(i, bit(3)){
	rep(k, 3)if((i >> k) & 1){
		ll curr = 0;
	  	for(int j = 20000; j >= 1; j--){
	  		curr += dp1[i ^ bit(k)][j + 1];
	  		if(v[k*2+1][0] <= j && j <= v[k*2+1][1])(dp1[i][j] += curr) %= mod;
  		}
  	}
  }
  dp2[0][0] = 1;
  rep(i, bit(4)){
  	rep(k, 4)if((i >> k) & 1){
  		ll curr = 0;
  		for(int j = 1; j <= 20000; j ++){
  			curr += dp2[i ^ bit(k)][j-1];
  			if(v[2*k][0] <= j && j <= v[2*k][1])(dp2[i][j] += curr) %= mod;
  		}
  	}
  }
  dp3[0][0] = 1;
  rep(i, bit(3)){
  	rep(k, 3)if((i >> k) & 1){
  		ll curr = 0;
  		for(int j = 1; j <= 20000; j ++){
  			curr += dp3[i ^ bit(k)][j-1];
  			if(v[2*k+1][0] <= j && j <= v[2*k+1][1])(dp3[i][j] += curr) %= mod;
  		}
  	}
  }
  dp4[0][20001] = 1;
  rep(i, bit(4)){
	rep(k, 4)if((i >> k) & 1){
		ll curr = 0;
	  	for(int j = 20000; j >= 1; j--){
	  		curr += dp4[i ^ bit(k)][j + 1];
	  		if(v[k*2][0] <= j && j <= v[k*2][1])(dp4[i][j] += curr) %= mod;
  		}
  	}
  }
  ll res = 0;
  ll curr = 0;
  for(int i = 19999; i >= 0; i--){
  	curr = (curr + dp1[7][i+1]) % mod;
  	res = (res + curr * dp2[15][i] % mod) % mod;
  }
  /*for(int i = 1; i < 20000; i++){
  	for(int j = i + 1; j <= 20000; j++){
  		res = (res + dp1[7][j] * dp2[15][i] % mod) % mod;
  	}
  }*/
  curr = 0;
  for(int i = 19999; i >= 0; i--){
  	curr = (curr + dp4[15][i+1]) % mod;
  	res = (res + curr * dp3[7][i] % mod) % mod;
  }
  /*for(int i = 1; i < 20000; i++){
  	for(int j = i + 1; j <= 20000; j++){
  		res = (res + dp4[15][j] * dp3[7][i] % mod) % mod;
  	}
  }*/
  cout << res << endl;
  return 0;
}
0