結果
問題 | No.122 傾向と対策:門松列(その3) |
ユーザー | koyumeishi |
提出日時 | 2016-04-05 20:04:26 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 17 ms / 5,000 ms |
コード長 | 5,919 bytes |
コンパイル時間 | 1,169 ms |
コンパイル使用メモリ | 119,504 KB |
実行使用メモリ | 7,552 KB |
最終ジャッジ日時 | 2024-10-10 23:53:55 |
合計ジャッジ時間 | 1,780 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 15 ms
7,552 KB |
testcase_01 | AC | 15 ms
7,552 KB |
testcase_02 | AC | 17 ms
7,552 KB |
testcase_03 | AC | 15 ms
7,552 KB |
testcase_04 | AC | 14 ms
7,552 KB |
testcase_05 | AC | 17 ms
7,552 KB |
testcase_06 | AC | 14 ms
7,552 KB |
testcase_07 | AC | 14 ms
7,552 KB |
ソースコード
#include <iostream> #include <vector> #include <cstdio> #include <sstream> #include <map> #include <string> #include <algorithm> #include <queue> #include <cmath> #include <functional> #include <set> #include <ctime> #include <random> #include <chrono> #include <cassert> using namespace std; namespace my_io{ template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;} template<class T> istream& operator , (istream& is, T& val){ return is >> val;} template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(int i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;} template<class T> ostream& operator , (ostream& os, const T& val){ return os << " " << val;} template<class T> ostream& operator >> (ostream& os, const T& val){ return os << " " << val;} template<class H> void println(const H& head){ cout << head << endl; } template<class H, class ... T> void println(const H& head, const T& ... tail){ cout << head << " "; println(tail...); } } using namespace my_io; namespace Montgomery{ template<long long MOD> constexpr long long PRE_COMP(long long r, long long res=0, long long t=0, long long i = 1){ return (r>1) ? ( PRE_COMP<MOD>(r/2, res + (t%2==0?i:0), (t%2==0?(t+MOD):t) / 2, i*2) ):( res ); } template<long long MOD> class Values{ public: static constexpr long long R = 1LL<<30; // R>MOD && gcd(R,MOD)==1 static constexpr long long mask = (1LL<<30)-1; static constexpr long long R2 = (R*R)%MOD; static constexpr long long Ninv = PRE_COMP<MOD>(1<<30); // N*Ninv = R-1 mod R static long long Reduction(long long x){ long long s = ((x & mask) * Ninv) & mask; long long ret = (x + s*MOD ) >> 30; if(ret>=MOD) ret -= MOD; return ret; } }; template<long long MOD> struct M_Int{ long long value; M_Int() : value(0) {} M_Int(long long val, bool convert=true) : value(convert ? Values<MOD>::Reduction(val * Values<MOD>::R2) : val){} //convert==true : int -> M_Int, false : M_Int::value -> M_Int M_Int(const M_Int& x) : value( x.value ){} //M_Int -> M_Int M_Int& operator = (const M_Int& x){ value = x.value; return *this; } M_Int& operator = (const long long& x){ value = Values<MOD>::Reduction(x * Values<MOD>::R2); return *this; } M_Int operator * (const M_Int& x) { return M_Int( Values<MOD>::Reduction(value * x.value) , false ); } M_Int operator * (const long long& x){ return (*this) * M_Int(x); } template<class T> M_Int& operator *= (const T& x){ return (*this) = (*this)*x; } M_Int operator + (const M_Int& x) { long long tmp = value + x.value; if(tmp >= MOD) tmp -= MOD; return M_Int(tmp, false); } M_Int operator + (const long long& x){ return (*this)+M_Int(x); } template<class T> M_Int& operator += (const T& x) { return (*this) = (*this) + x; } M_Int operator - (const M_Int& x) { long long tmp = value - x.value; if(tmp < 0 ) tmp += MOD; return M_Int(tmp, false); } M_Int operator - (const long long& x){ return (*this)-M_Int(x); } template<class T> M_Int& operator -= (const T& x) { return (*this) = (*this) - x; } bool operator == (const M_Int& x){ return value == x.value; } bool operator == (const long long& x){ M_Int tmp(x); return (*this)==tmp; } long long to_i () { // M_int -> int return Values<MOD>::Reduction(value); } operator long long () { // M_int -> int return Values<MOD>::Reduction(value); } }; template<long long MOD> istream& operator>>(istream& is, M_Int<MOD>& v){ long long tmp; is >> tmp; v=tmp; return is; } template<long long MOD> ostream& operator<<(ostream& os, M_Int<MOD> v){ return os << v.to_i(); } } using mint = Montgomery::M_Int<1000000007>; int main(){ vector<vector<int>> v(7, vector<int>(2)); cin >> v; int low = 1; int high = 20000; vector<int> A = {0,2,4,6}; vector<int> B = {1,3,5}; mint ans = 0; {//A < B vector<vector<mint>> dp_A(1<<4, vector<mint>(20005,0)); vector<vector<char>> dp_A_ok(1<<4, vector<char>(20005,0)); vector<vector<mint>> dp_B(1<<3, vector<mint>(20005,0)); vector<vector<char>> dp_B_ok(1<<3, vector<char>(20005,0)); for(int a=low; a<=high; a++){ for(int k=0; k<(1<<4)-1; k++){ dp_A[k][a] += dp_A[k][a-1]; for(int x=0; x<4; x++){ if((k>>x)&1) continue; if(a < v[A[x]][0] || v[A[x]][1] < a) continue; dp_A[k|(1<<x)][a] += dp_A[k][a-1] + mint(k==0?1:0); dp_A_ok[k|(1<<x)][a] = 1; } } } for(int a=high; a>=low; a--){ for(int k=0; k<(1<<3); k++){ dp_B[k][a] += dp_B[k][a+1]; for(int x=0; x<3; x++){ if((k>>x)&1) continue; if(a < v[B[x]][0] || v[B[x]][1] < a) continue; dp_B[k|(1<<x)][a] += dp_B[k][a+1] + mint(k==0?1:0); dp_B_ok[k|(1<<x)][a] = 1; } } } for(int a=low; a<=high; a++){ if(dp_A_ok[0b1111][a] == 0) continue; ans += dp_A[0b1111][a] * dp_B[0b111][a+1]; } } {//A > B vector<vector<mint>> dp_A(1<<4, vector<mint>(20005,0)); vector<vector<char>> dp_A_ok(1<<4, vector<char>(20005,0)); vector<vector<mint>> dp_B(1<<3, vector<mint>(20005,0)); vector<vector<char>> dp_B_ok(1<<3, vector<char>(20005,0)); for(int a=high; a>=low; a--){ for(int k=0; k<(1<<4); k++){ dp_A[k][a] += dp_A[k][a+1]; for(int x=0; x<4; x++){ if((k>>x)&1) continue; if(a < v[A[x]][0] || v[A[x]][1] < a) continue; dp_A[k|(1<<x)][a] += dp_A[k][a+1] + mint(k==0?1:0); dp_A_ok[k|(1<<x)][a] = 1; } } } for(int a=low; a<=high; a++){ for(int k=0; k<(1<<3)-1; k++){ dp_B[k][a] += dp_B[k][a-1]; for(int x=0; x<3; x++){ if((k>>x)&1) continue; if(a < v[B[x]][0] || v[B[x]][1] < a) continue; dp_B[k|(1<<x)][a] += dp_B[k][a-1] + mint(k==0?1:0); dp_B_ok[k|(1<<x)][a] = 1; } } } for(int a=low; a<=high; a++){ if(dp_B_ok[0b111][a] == 0) continue; ans += dp_B[0b111][a] * dp_A[0b1111][a+1]; } } println(ans); return 0; }