社区讨论
神秘原因,求问
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 条回复,欢迎继续交流。
正在加载回复...