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を全て除いて乗算演算に変換して余剰をとることができる.
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;
}