Codeforces #167 Div1. B. Dima and Two Sequences

さて２問目。ここまでは何とか本番に解けた…。
http://codeforces.com/contest/273/problem/B

問題

N個の数値配列AとBが与えられる。
ここに(A[1],1),(A[2],2),...,(A[N],N)および(B[1],1),(B[2],2),...,(B[N],N)の2N個の座標が与えられる。
この2N個の点を、X座標が減らない順に並べる場合に、その並べ方の総数をMで割った数値を答える。

解答

A[1]～A[N]およびB[1]～B[N]に同じ数値がある場合、X座標が同じ点がいくつかあるので、それらの点の並べ方は任意である。
X座標が同じ点がP個ある場合、その並べ方はP!である。
また、X座標もY座標も同じ点が最大２点ずつある可能性があるが、その場合はその数だけP!を2で割っていけばよい。

下記の解法では、関数numはX座標が同じ点の数Sに対しS!を計算するが、S!を計算する過程でY座標が一致する２点があるたびに2で割っている。

int N;
ll M;
vector<pair<int, int> > K;

ll num(int s,int l) {
	int i,a;
	int ns=0;
	ll pat=1;
	
	FOR(i,l-1) if(K[s+i].second==K[s+i+1].second) ns++;
	for(i=1;i<=l;i++) {
		a=i;
		while(ns && a%2==0) { a>>=1; ns--;}
		pat = (pat * a)%M;
	}
	return pat;
	
}

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	FOR(i,N) K.push_back(make_pair(GETi(),i+1));
	FOR(i,N) K.push_back(make_pair(GETi(),i+1));
	M=GETi();
	sort(K.begin(),K.end());
	
	ll pat=1;
	for(i=0;i<K.size();) {
		x = K[i].first;
		int l=0;
		while(i+l<K.size() && K[i+l].first==x) l++;
		pat = (pat * num(i,l)) % M;
		i+=l;
	}
	
	_P("%d\n",(int)pat);
	return;
}

まとめ

Codeforceっぽい問題。
こういうちょっとひねった数字や図形の作り方を問う問題多いよね。