题解

一道水题。。。
分别考虑当前点自己翻和不翻的情况。
一波组合数。
注意线性求完逆元后记得求前缀啊…(调了半个小时才发现没求前缀(捂脸

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
const int N=1e5+10,mod=998244353;
typedef long long ll;
int n,Q,a[N],b[N],rk[N];
int ls[N][2],mr[N][2],si;
ll r[N],inv[N],ans;inline int rd()
{register char ch=getchar();register int x=0,f=1;while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}return x*f;
}inline bool cmp(const int&x,const int&y){return a[x]<a[y];}
inline ll C(int n,int m){return r[n]*inv[m]%mod*inv[n-m]%mod;}int main(){register int i,j,pos,k,inc;n=rd();Q=rd();r[1]=1;r[0]=1;inv[1]=1;inv[0]=1;for(i=2;i<=n;++i)r[i]=1ll*r[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;for(i=2;i<=n;++i) inv[i]=inv[i]*inv[i-1]%mod; ///记得求前缀和啊，不要线性推完逆元就跑了QWQ for(i=1;i<=n;++i){a[i]=rd();b[i]=i;}sort(b+1,b+n+1,cmp);for(pos=0,k=0,i=2;i<=n;++i){for(;a[b[pos+1]]*2<a[b[i]] && pos<i-1;++pos);for(;a[b[k+1]]<a[b[i]] && k<i-1;++k);ls[b[i]][0]=pos;ls[b[i]][1]=k-pos;}for(pos=n+1,k=n+1,i=n-1;i>=1;--i){for(;a[b[pos-1]]>=a[b[i]]*2 && pos>i+1;--pos);for(;a[b[k-1]]>a[b[i]] && k>i+1;--k);mr[b[i]][0]=pos-k;mr[b[i]][1]=n-pos+1;}for(i=1;i<=n;++i){if(a[i]==0){printf("%lld\n",C(n,Q));continue;}ans=0;si=n-(ls[i][0]+ls[i][1]+mr[i][0]+mr[i][1]);k=ls[i][0]+si+mr[i][1]+mr[i][0]-1;if(Q<=k) ans+=C(k,Q);k=si+mr[i][0];if(Q>=k && Q-k<=n-k) ans=(ans+C(n-k,Q-k))%mod;printf("%lld\n",ans);}
}