题目链接

Solution

假设我们当前要算\(x\)的答案，分两种情况讨论：

\(x\)没被翻倍，那么\([a_x/2,a_x]\)这个区间的数不能动，其他的随便选，组合数就好了。
\(x\)翻倍了，那么\([a_x,a_x*2]\)这个区间一定要翻倍，其他的随便选。

实现的时候排序然后指针扫一下就好了。

Code

#include<bits/stdc++.h>

using namespace std;

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define ll long long 

#define pii pair<int,int >

#define vec vector<int >

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) 

const int maxn = 2e5+10;

const int inf = 1e9;

const lf eps = 1e-8;

const int mod = 998244353;

int n,k,ans[maxn],fac[maxn],ifac[maxn],inv[maxn],t[maxn];

struct data{int x,id,ans;}a[maxn];

int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}

int del(int x,int y) {return x-y<0?x-y+mod:x-y;}

int mul(int x,int y) {return 1ll*x*y-1ll*x*y/mod*mod;}

void prepare() {

    inv[0]=inv[1]=ifac[0]=fac[0]=1;

    FOR(i,1,n) fac[i]=mul(fac[i-1],i);

    FOR(i,2,n) inv[i]=mul(mod-mod/i,inv[mod%i]);

    FOR(i,1,n) ifac[i]=mul(ifac[i-1],inv[i]);

}

int c(int x,int y) {

    if(x<y||x<0) return 0;

    return mul(mul(fac[x],ifac[y]),ifac[x-y]);

}

int cmp1(data x,data y) {return x.x<y.x;}

int cmp2(data x,data y) {return x.id<y.id;}

int main() {

    read(n),read(k);FOR(i,1,n) read(a[i].x),a[i].id=i;

    prepare();sort(a+1,a+n+1,cmp1);a[0].x=-1;

    for(int i=1;i<=n;i++) if(a[i].x==a[i-1].x) t[i]=t[i-1];else t[i]=n-i+1;

    int p=0;a[0].x=0;

    for(int i=1;i<=n;i++) {

        while((a[p+1].x<<1)<a[i].x) p++;

        a[i].ans=add(a[i].ans,c(p+t[i]-1,k));

    }p=1;

    for(int i=1;i<=n;i++) {

        while(a[p+1].x<(a[i].x<<1)&&p+1<=n) p++;

        a[i].ans=add(a[i].ans,c(n-(p-i+1),k-(p-i+1)));

    }for(int i=1;i<=n;i++) if(a[i].x==a[i-1].x) a[i].ans=a[i-1].ans;

    sort(a+1,a+n+1,cmp2);

    for(int i=1;i<=n;i++) write(a[i].x==0?c(n,k):a[i].ans);

    return 0;

}

巴特西

[LOJ6432] [PKUSC2018] 真实排名

题目链接

Solution

Code

最新文章

热门文章