HackerRank Ad Infinitum - Math Programming Contest May'14 5問目
problem statement(コンテストページ)
problem statement
$L_k, R_k, \;\; k=1,2,3,4$ が与えられた時,以下の条件1~2.を満たす整数の $4$ つ組 $(X_1,X_2,X_3,X_4)$ が何個存在するかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.
条件2が無ければ掛け算するだけで簡単に計算できる.
また,条件1を満たし,かつ,$X_1 = X_2$の時なども,同様に簡単に計算できる.
なので,包除原理を用いる.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define M 1000000007
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
int L[4], R[4];
int num[4];
ll solve(){
int i, j, k;
int l[4], r[4], ok[4] = {};
ll res = 1;
rep(i,4) l[i] = L[i], r[i] = R[i];
rep(k,4) rep(i,4) rep(j,4) if(num[i]==num[j]){
l[i] = l[j] = max(l[i],l[j]);
r[i] = r[j] = min(r[i],r[j]);
}
rep(i,4) if(l[i] > r[i]) return 0;
rep(i,4) if(!ok[num[i]]){
res = (res * (r[i]-l[i]+1)) % M;
ok[num[i]] = 1;
}
return res;
}
int main(){
int T;
int i, j, k, mask;
ll res, tmp;
reader(&T);
while(T--){
rep(i,4) reader(L+i,R+i);
res = 0;
rep(mask,1<<4){
rep(i,4) num[i] = i;
k = 1;
rep(i,4) if(mask & 1<<i) k *= -1;
rep(j,4) rep(i,4) if(mask & 1<<i){
num[i] = num[(i+1)%4] = min(num[i], num[(i+1)%4]);
}
res += k * solve();
}
res %= M;
if(res < 0) res += M;
writer((int)res, '\n');
}
return 0;
}
Current time: 2024年03月29日10時10分35秒
Last modified: 2014年09月23日00時02分57秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_infinitum-may14
トップページに戻る
Logged in as: unknown user (not login)