結果
| 問題 |
No.122 傾向と対策：門松列（その３）
|
| コンテスト | |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2016-04-05 20:04:26 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 8 |
ソースコード
#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;
}