输出负数求助
查看原帖
输出负数求助
856004
Grammar_hbw楼主2025/1/6 22:04

WA 20,错误信息很多都是输出了负数,但是我都开long long了

#include <bits/stdc++.h>
using namespace std;
const int N=100007,mod=998244353;
long long inv[N],fact[N],finv[N],ans[N],n,k;
struct node{
	int pos,val;
	bool operator<(const node o)const{return val<o.val;}
} a[N];
inline long long c(long long a,long long b){
	if(a<0) return 0;
	if(b<0) return 0;
	if(a>b) return 0;
	return 1ll*fact[b]*finv[a]%mod*finv[b-a]%mod;
}
inline long long cnt(int l,int r){
	if(l>r) return 0;
	return upper_bound(a+1,a+n+1,node{0,r})-lower_bound(a+1,a+n+1,node{0,l});
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	inv[1]=1;
	for(int i=2;i<=n;i++) inv[i]=1ll*(mod-1)*inv[mod%i]%mod*(mod/i)%mod;
	fact[0]=finv[0]=1;
	for(int i=1;i<=n;i++) fact[i]=1ll*fact[i-1]*i%mod;
	for(int i=1;i<=n;i++) finv[i]=1ll*finv[i-1]*inv[i]%mod;
	for(int i=1;i<=n;i++) a[i].pos=i,cin>>a[i].val;
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(!a[i].val) {ans[a[i].pos]=c(k,n);continue;}
		if((ans[a[i].pos]+=c(k,n-cnt((a[i].val+1)>>1,a[i].val-1)-1))>=mod) ans[i]-=mod;
		if((ans[a[i].pos]+=c(k-cnt(a[i].val,(a[i].val<<1)-1),n-cnt(a[i].val,(a[i].val<<1)-1)))>=mod) ans[i]-=mod;
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
}
2025/1/6 22:04
加载中...