Codeforces 167 div2 D Dima and Two Sequences

1332 ワード

ツッコミ:B題はlong long WAを2回書いていないので我慢して、40分でD題を始めましたが、1時間かけてsetとmapを勉強しました.《
Cの傷だけでは起きないでしょう...setとmapの役割を間違えてしまったなんて..
setは同じ要素を保存できませんよね??ではなぜcount()関数を作るのか!!!
30分も调整して出てこなかったs.cont(x)あ!!!突っ込む力がない.
また作者に突っ込む--.pretest 3は100のデータを書き始めました.死ぬでしょう.
 
========================================
 
S(x)を座標がxに等しい点の個数とすると、ans=(S(x 1)!*S(x2)! * ...S(xm)! )%m
問題は2つの点が同じ場合であり,この問題では1つの場合,すなわちAi=Biしか考えられない.
Ai=Bi,交換(Ai,i)(Bi,i)は新たな配列を生じないためans/=2.
k対Ai=Biならans=((S(x 1)!*S(x2)! *.....S(xm)! )/(2^k) )%m
ペア毎にAi=Bi,S(Ai)>=2となるので,2を全て除いて乗算演算に変換して余剰をとることができる.
#include<cstdio>
#include<map>
#define X 100010
using namespace std;
int a[X],b[2*X];
map<int,int>g;
int main(){
	int i,j,n,m,k,x,cnt,top;
	long long as,tmp;
	as=1,top=1,cnt=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		if(!g[x])g[x]=top++;
		b[g[x]]++;
		a[i]=x;
	}
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		if(!g[x])g[x]=top++;
		b[g[x]]++;
		if(a[i]==x)cnt++;
	}
	scanf("%d",&m);
	for(i=1;i<top;i++)
		if(b[i]){
			for(tmp=1;b[i];b[i]--)
				if(b[i]%2==0&&cnt)  tmp=(tmp*b[i]/2)%m,cnt--;				
				else 			    tmp=(tmp*b[i])%m;
			as=(as*tmp)%m;
		}
	printf("%I64d
",as); return 0; }