結果

問題 No.907 Continuous Kadomatu
ユーザー HIR180HIR180
提出日時 2019-10-11 22:06:20
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 241 ms / 2,000 ms
コード長 4,009 bytes
コンパイル時間 3,407 ms
コンパイル使用メモリ 184,816 KB
実行使用メモリ 69,548 KB
最終ジャッジ日時 2023-08-16 18:00:56
合計ジャッジ時間 10,303 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 124 ms
4,380 KB
testcase_01 AC 125 ms
4,384 KB
testcase_02 AC 123 ms
4,376 KB
testcase_03 AC 124 ms
4,380 KB
testcase_04 AC 124 ms
4,376 KB
testcase_05 AC 141 ms
13,360 KB
testcase_06 AC 125 ms
4,376 KB
testcase_07 AC 132 ms
7,328 KB
testcase_08 AC 138 ms
11,708 KB
testcase_09 AC 133 ms
8,612 KB
testcase_10 AC 151 ms
17,876 KB
testcase_11 AC 159 ms
23,360 KB
testcase_12 AC 194 ms
39,916 KB
testcase_13 AC 200 ms
44,120 KB
testcase_14 AC 204 ms
44,748 KB
testcase_15 AC 201 ms
44,248 KB
testcase_16 AC 207 ms
48,388 KB
testcase_17 AC 210 ms
48,852 KB
testcase_18 AC 204 ms
45,496 KB
testcase_19 AC 212 ms
50,372 KB
testcase_20 AC 128 ms
5,700 KB
testcase_21 AC 127 ms
5,580 KB
testcase_22 AC 127 ms
5,572 KB
testcase_23 AC 235 ms
69,344 KB
testcase_24 AC 241 ms
69,548 KB
testcase_25 AC 124 ms
4,376 KB
testcase_26 AC 124 ms
4,384 KB
testcase_27 AC 124 ms
4,384 KB
testcase_28 AC 124 ms
4,380 KB
testcase_29 AC 125 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n;
vector<ll>za;
ll dp[205][405][205],a[205],b[205];
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[505],R[505];
void make(){
	F[0] = 1;
	for(int i=1;i<505;i++) F[i] = F[i-1]*i%mod;
	for(int i=0;i<505;i++) R[i] = modpow(F[i],mod-2);
}
ll C(int a,int b){
	return F[a]*R[b]%mod*R[a-b]%mod;
}
ll coef[205];
//k = n+1-2*m
//sum_{m=0...n/2} (-1)^m*2^{1-k}*sum_{j=0...k} binomial(k,j)*(-1)^j*(k-2*j)^(n+1)/k - [n=1]
void make2(){
	coef[1] = 1;
	for(int n=2;n<205;n++){
		for(int m=0;m<=n/2;m++){
			ll x = (m%2==0?1:-1);
			int k = n+1-2*m;
			x *= 2LL;
			x = x%mod*modpow(modpow(2,k),mod-2)%mod;
			ll S = 0;
			for(int j=0;j<=k;j++){
				ll c = C(k,j);
				if(j%2 == 1) c *= -1;
				c = c*modpow((k-j-j),n+1)%mod;
				c = c*modpow(k,mod-2)%mod;
				S += c;
			}
			S %= mod;
			coef[n] += x*S%mod;
		}
		coef[n] = (coef[n]%mod+mod)%mod;
	}
	for(int i=1;i<205;i++){
		coef[i] = coef[i] * R[i] % mod;
		if(i > 1) coef[i] = coef[i] * modpow(2LL,mod-2) % mod;
	}
	//for(int i=1;i<=10;i++) cout << coef[i] << endl;
}
ll sum[205][405],rui[205][405];
int main(){
	make();
	make2();
	
	cin >> n;
	rep(i,n) cin >> a[i] >> b[i];
	rep(i,n) { za.pb(a[i]); za.pb(b[i]); }
	SORT(za); ERASE(za);
	int L = POSL(za,a[0]), R = POSL(za,b[0]);
	for(int i=L;i<R;i++){
		ll up = za[i+1]-za[i];
		up = up * modpow(za[R]-za[L],mod-2) % mod;
		
		dp[0][i][1] = up;
	}
	for(int j=0;j<za.size();j++){
		for(int k=1;k<205;k++){
			sum[0][j] += dp[0][j][k]*coef[k]%mod;
		}
		sum[0][j] %= mod;
		rui[0][j] += sum[0][j];
		if(j) rui[0][j] += rui[0][j-1];
		rui[0][j] %= mod;
	}
	for(int i=1;i<n;i++){
		int L = POSL(za,a[i]);
		int R = POSL(za,b[i]);
		ll rev = modpow(b[i]-a[i],mod-2);
		for(int j=L;j<R;j++){
			ll up = za[j+1]-za[j];
			up = up*rev%mod;
			for(int k=1;k<=i+1;k++){
				//go to same
				if(k > 1){
					dp[i][j][k] += dp[i-1][j][k-1]*up%mod;
				}
				//go to dif
				if(k == 1){
    				if(i%2 == 1){
    					ll x = (j==0?0:rui[i-1][j-1]);
    					dp[i][j][k] += x%mod*up%mod;
    				}
    				else{
    					ll x = rui[i-1][za.size()-1];
    					x -= rui[i-1][j];
    					dp[i][j][k] += x%mod*up%mod;
    				}
				}
				if(dp[i][j][k] >= mod) dp[i][j][k] -= mod;
				if(dp[i][j][k] < 0) dp[i][j][k] += mod;
			}
		}
		for(int j=0;j<za.size();j++){
			for(int k=1;k<205;k++){
				sum[i][j] += dp[i][j][k]*coef[k]%mod;
			}
			sum[i][j] %= mod;
			rui[i][j] += sum[i][j];
			if(j) rui[i][j] += rui[i][j-1];
			rui[i][j] %= mod;
		}
	}
	ll ans = 0;
	for(int j=0;j<za.size();j++){
		for(int k=1;k<205;k++){
			ans += dp[n-1][j][k] * coef[k] % mod;
		}
	}
	cout << (ans%mod+mod)%mod << endl;
}
0