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である
/*
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); }