求助,本地通过样例#7,#9,在洛谷上WA
查看原帖
求助,本地通过样例#7,#9,在洛谷上WA
1103464
ming2023楼主2024/10/11 16:58

RT,分析半天感觉并没有涉及win&linux差异的问题,跪求指点

#include<bits/stdc++.h>
using namespace std;

const long long N=10005;
const long long mod=998244353;

long long storing[N];
long long jc[N];

long long quickPow(long long a,long long b)
{
	long long result=1;
	
	while(b)
	{
		if(b&1) result=result*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	
	return result;
}

long long inv(long long x)
{
	return quickPow(x,mod-2);
}

long long C(long long a,long long b)
{
	return ((jc[a]*inv(jc[b])%mod)*inv(jc[a-b]))%mod;
}

int main()
{
	memset(storing,0,sizeof(storing));
	memset(jc,0,sizeof(jc));
	
	jc[0]=1;
	for(long long i=1;i<N-10;i++) jc[i]=jc[i-1]*i%mod;

	long long n;cin>>n;
	for(long long i=1;i<=n;i++) cin>>storing[i];
	
	for(long long i=1;i<=n;i++)
	{
		bool lExist=0;
		bool rExist=0;
		long long l=0,r=0;
		
		for(long long j=i-1;j>=1;j--)
		{
			if(storing[j]>storing[i]) 
			{
				lExist=1;
				l=j;
				break;
			}
		}
		for(long long j=i+1;j<=n;j++)
		{
			if(storing[j]>storing[i]) 
			{
				rExist=1;
				r=j;
				break;
			}
		}
		
		
		long long result=0;
		if(lExist==0 && rExist==0)
		{
			cout<<n-1<<' ';
			continue;
		}
		else if(lExist==0)//la
		{
			for(long long j=1;j<n;j++)
			{
				long long la=C(n-r+i-1,j-r+i)*inv(C(n-1,j))%mod;

				result=(result+(mod+1-la))%mod;
			}
		}
		else if(rExist==0)
		{
			for(long long j=1;j<=n-1;j++)
			{
				long long ra=C(n-i+l-1,j-i+l)*inv(C(n-1,j))%mod;
				result=(result+(mod+1-ra))%mod;
			}
		}
		else
		{
			for(long long j=1;j<n;j++)
			{
				long long la=C(n-r+i-1,j-r+i)*inv(C(n-1,j))%mod;
				long long ra=C(n-i+l-1,j-i+l)*inv(C(n-1,j))%mod;
				long long both=C(n-r+l-1,j-r+l)*inv(C(n-1,j))%mod;
				
				result=(result+(mod*2+1-la-ra+both))%mod;
			}
		}
		cout<<result<<' ';
	}
}
2024/10/11 16:58
加载中...