結果

問題 No.122 傾向と対策：門松列（その３）
ユーザー koyumeishikoyumeishi
提出日時 2016-04-05 20:04:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 19 ms / 5,000 ms
コード長 5,919 bytes
コンパイル時間 1,282 ms
コンパイル使用メモリ 117,660 KB
実行使用メモリ 7,680 KB
最終ジャッジ日時 2024-04-19 07:14:27
合計ジャッジ時間 1,859 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 14 ms
7,680 KB
testcase_01 AC 15 ms
7,680 KB
testcase_02 AC 18 ms
7,680 KB
testcase_03 AC 16 ms
7,552 KB
testcase_04 AC 16 ms
7,680 KB
testcase_05 AC 19 ms
7,680 KB
testcase_06 AC 15 ms
7,680 KB
testcase_07 AC 15 ms
7,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0