cf 167.div2 D.Dima and Two Sequences
1656 ワード
今日のcfは全く状態がなく、A問題は10分で問題の意味が読めます.目測が外れる
この問題の意味はとても簡単で、X昇順に並べてどれだけの情況があることができて、1つの並べ替えの組み合わせの問題
同じxの要素の個数をXiとし,まったく同じ2 Kとする(易知若は全く同じで2個しかないが,試合のときは思わなかった).
ans= ∑Xi!/2^k
階乗で2^kを除くことができるのは,kが最大n/2であり,n!の2の因子は少なくともn/2である
この問題の意味はとても簡単で、X昇順に並べてどれだけの情況があることができて、1つの並べ替えの組み合わせの問題
同じxの要素の個数をXiとし,まったく同じ2 Kとする(易知若は全く同じで2個しかないが,試合のときは思わなかった).
ans= ∑Xi!/2^k
階乗で2^kを除くことができるのは,kが最大n/2であり,n!の2の因子は少なくともn/2である
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include
#include
#include
#include
#include
#define INF 1E9
using namespace std;
struct node
{
int x,y;
};
bool cmp(node a,node b)
{
if(a.x!=b.x)return a.x>=1;tt--;}// 2^k
ans=(ans*t);
if(ans>m)ans%=m;
}
return ans;
}
int main()
{
int n,t;
scanf("%d",&n);
n*=2;
int i,j,k;
for(i=k=1;i<=n;i++,k++)
{
scanf("%d",&t);
org[i].x=t;
org[i].y=k;
if(k==n/2)k=0;
}
int m;
scanf("%d",&m);
sort(org+1,org+n+1,cmp);
long long ans=1;
int tt=0;
for(i=1;i<=n;i++)
{
t=1;
j=1;
while(i<=n&&org[i].x==org[i+1].x)
{
if(org[i].y==org[i+1].y)j++;
else
{
if(j>1)tt++;
j=1;
}
i++;t++;
}
if(j>1)tt++;
if(t>1)
{
ans=(ans*(fac(t,m,tt)));
if(ans>=m)ans%=m;
}
}
printf("%I64d
",ans);
}