社区讨论

神秘原因,求问

P14636[NOIP2025] 清仓甩卖参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mina90gn
此快照首次捕获于
2025/12/01 23:07
3 个月前
此快照最后确认于
2025/12/03 22:30
3 个月前
查看原帖
为什么我将数组大小定义成10005会神秘WA,但是将数组大小定义为20005就能AC呢?
未通过代码:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+5,mod=998244353;
int kjsdfl,_,n,m,ans;
int a[N],pw[N],inv[N],pre[N];
int C(int x,int y){return pre[x]*inv[y]%mod*inv[x-y]%mod;}
void work(){
	cin>>n>>m; ans=0; 
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		int k=0; 
		for(int j=i+1;j<=n;j++){
			if(a[i]==a[j] || m-2-n+j<0) continue;
			if(a[j]>=a[i]*2) break;
			while(k<n && a[i]+a[k+1]<a[j]) k++;
			ans=(ans+(1ll*pw[k]*C(n-i-1,m-2-n+j)%mod))%mod;
		}
	}
	cout<<(pw[n]-ans+mod)%mod<<'\n';
}
void init(){
	pw[0]=1; inv[0]=inv[1]=1; pre[0]=pre[1]=1;
	for(int i=1;i<=10000;i++) pw[i]=(pw[i-1]*2)%mod;
	for(int i=2;i<=10000;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod,pre[i]=(pre[i-1]*i)%mod;
	for(int i=1;i<=10000;i++) inv[i]=(inv[i]*inv[i-1])%mod;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	init(); 
	cin>>kjsdfl>>_;
	while(_--) work();
	return 0;
}
通过代码:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+5,mod=998244353;
int kjsdfl,_,n,m,ans;
int a[N],pw[N],inv[N],pre[N];
int C(int x,int y){return pre[x]*inv[y]%mod*inv[x-y]%mod;}
void work(){
	cin>>n>>m; ans=0; 
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		int k=0; 
		for(int j=i+1;j<=n;j++){
			if(a[i]==a[j] || m-2-n+j<0) continue;
			if(a[j]>=a[i]*2) break;
			while(k<n && a[i]+a[k+1]<a[j]) k++;
			ans=(ans+(1ll*pw[k]*C(n-i-1,m-2-n+j)%mod))%mod;
		}
	}
	cout<<(pw[n]-ans+mod)%mod<<'\n';
}
void init(){
	pw[0]=1; inv[0]=inv[1]=1; pre[0]=pre[1]=1;
	for(int i=1;i<=10000;i++) pw[i]=(pw[i-1]*2)%mod;
	for(int i=2;i<=10000;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod,pre[i]=(pre[i-1]*i)%mod;
	for(int i=1;i<=10000;i++) inv[i]=(inv[i]*inv[i-1])%mod;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	init(); 
	cin>>kjsdfl>>_;
	while(_--) work();
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...