锐客网

  1. 首页 > it技术 > >

stl|loj 6432「PKUSC2018」真实排名

数学STL

http://www.elijahqi.win/archives/3586
题面https://loj.ac/problem/6432
注意排名是和我相同的和比我大的算相同性质
想了很久才会做的细节题 然而自己菜细节想不清最后也没A 成功垫底送温暖 qwq绝望
先排序 只需要二分出 谁×2会≥当前值
我×2会大于等于那个值以及我所处的位置
【stl|loj 6432「PKUSC2018」真实排名】二分出这些位置 接下来只需要枚举每个数 他到底排名是否发生变化
分别枚举组合数即可 这个点翻倍 则比他两倍小的也必须翻倍
如果不翻倍 所有两倍之后大于等于这个数的数也都不能翻倍
对于0的情况 直接输出c(n,k)即可

#include #include #include #define ll long long using namespace std; inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin); if(T==S) return EOF; } return *S++; } inline int read(){ int x=0,f=1; char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f; } const int mod=998244353; const int N=1e5+10; int jc[N],inv[N],n,k,a[N],a1[N]; inline int ksm(ll b,int t){static ll tmp; for (tmp=1; t; b=b*b%mod,t>>=1) if (t&1) tmp=tmp*b%mod; return tmp; } inline int C(int n,int m){ if(n=mod?x+v-mod:x+v; } int main(){ freopen("loj6432.in","r",stdin); n=read(); k=read(); for (int i=1; i<=n; ++i) a[i]=read(),a1[i]=a[i]; sort(a1+1,a1+n+1); jc[0]=1; for (int i=1; i<=n; ++i) jc[i]=(ll)jc[i-1]*i%mod; inv[n]=ksm(jc[n],mod-2); for (int i=n-1; ~i; --i) inv[i]=(ll)inv[i+1]*(i+1)%mod; for (int i=1; i<=n; ++i){ if (!a[i]) {printf("%d\n",C(n,k)); continue; } int l=lower_bound(a1+1,a1+n+1,a[i]+1>>1)-a1,r=lower_bound(a1+1,a1+n+1,a[i]<<1)-a1,md=lower_bound(a1+1,a1+n+1,a[i])-a1; printf("%d\n",inc((ll)C(n-(md-l+1),k),(ll)C(n-(r-md),k-(r-md)))); } return 0; }

    推荐阅读


    上一篇：【操作系统】进程调度算法-FCFS-SJF-RR

    下一篇：stm32f072的spi的设置注意事项。