「PKUSC2018」真实排名（排列组合，数学）

前言

为什么随机跳题会跳到这种题目啊？

Solution

我们发现可以把这个东西分情况讨论：
1.这个点没有加倍

这一段相同的可以看成一个点，然后后面的都可以。
这一段看成一个点，然后前面的不能对他造成影响的都可以。

2.这个点加倍了

这一段相同的看做一个点，然后前面的都可以
这一段相同的看成一个点，然后后面的如果对他的排名有影响，一定要加倍。

剩下的用组合数随便乱算一下就好了。

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
const int N=100010,Mod=998244353;
struct node{int id,val;};
bool cmp(node a,node b){return a.val<b.val;}
node a[N];
int jc[N],jcn[N],inv[N],n,k,ans[N],pre[N],last;
int C(int n,int m){
    if(n<0 || m<0 || n<m)return 0;
    return (ll)jc[n]*jcn[m]%Mod*jcn[n-m]%Mod;
}
void init(){
    jc[0]=jcn[0]=inv[1]=1;
    for(int i=1;i<=n;i++)jc[i]=(ll)jc[i-1]*i%Mod;
    for(int i=2;i<=n;i++)inv[i]=(ll)(Mod-Mod/i)*inv[Mod%i]%Mod;
    for(int i=1;i<=n;i++)jcn[i]=(ll)jcn[i-1]*inv[i]%Mod;
}
int main(){
    n=gi();k=gi();
    for(int i=1;i<=n;i++)a[i].val=gi(),a[i].id=i;
    init();
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(a[last].val!=a[i].val)last=i;
        pre[i]=last;
    }
    for(int i=1;i<=n;i++){
        int tmp=i;
        int now=a[tmp].id,have;i=pre[i];
        have=n-i;
        int l=1,r=i-1,wh=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(a[mid].val*2>=a[i].val){wh=mid;r=mid-1;}
            else l=mid+1;
        }
        have+=i-1;
        if(wh)have-=i-wh;
        ans[now]=C(have,k);
        have=i-1;int K=k-1;
        l=1,r=n;wh=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(a[mid].val<a[i].val*2){wh=mid;l=mid+1;}
            else r=mid-1;
        }
        if(!wh)have+=n-i;
        else{K=K-wh+i;have+=n-wh;}
        ans[now]=(ans[now]+C(have,K))%Mod;
        i=tmp;
    }
    for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
    return 0;
}

巴特西

「PKUSC2018」真实排名（排列组合，数学）

前言

Solution

代码实现

最新文章

热门文章