924
cf 167.div2 D.Dima and Two Sequences
今天的cf完全不在狀態，A題10分鍾才讀懂題意。目測要掉rating了
這題題意很簡單，就是按X升序排列會有多少種情況，一個排列組合的問題
設相同x的元素個數為Xi ，完全相同為2K（易知若完全相同有且僅有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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#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<b.x;
return a.y<b.y;
}
node org[200010];
long long fac(int n,int m,int &tt)
{
long long ans=1;
int i,t;
for(i=1;i<=n;i++)
{
t=i;
while(tt&&!(t&1)){t>>=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\n",ans);
}
最後更新：2017-04-04 07:03:48