4 条题解
-
3$$求无法拼凑方案数：tot=Σ_{i=1}^{n}Σ_{j=i+1}^{n}Σ_{k=j+1}^{n}[a_{i}+a_{j}≤a_{k}]$$$$构造多项式：A(x)=Σ_{i=0}^{m}cnt_{i}x^{i}其中m为最长的木棍长度，cnt_{i}为长度为i的木棍数量$$
#include<bits/stdc++.h> using namespace std; #define int long long #define complex complex<double> #define pi acos(-1.0) #define N 400010 #define mod 998244353 int qpow(int a,int b){ int res=1; for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod; return res; } complex A[N]; int n,m,r[N]; void change(complex A[],int n){ for(int i=0;i<n;i++)if(i<r[i])swap(A[i],A[r[i]]); } void fft(complex A[],int n,int op){ change(A,n); for(int m=2;m<=n;m<<=1){ complex w1({cos(2*pi/m),sin(2*pi/m)*op}); for(int i=0;i<n;i+=m){ complex wk({1,0}); for(int j=0;j<m/2;j++){ complex x=A[i+j],y=A[i+j+m/2]*wk; A[i+j]=x+y,A[i+j+m/2]=x-y; wk*=w1; } } } if(op==-1){ for(int i=0;i<n;i++)A[i]/=n; } } int cnt[N],a[N],way[N],sum[N]; void solve(){ cin>>n;int nn=n; int mx=0; memset(cnt,0,sizeof(cnt)); for(int i=0;i<N;i++)A[i]={0,0}; for(int i=1;i<=n;i++)cin>>a[i],mx=max(mx,a[i]),cnt[a[i]]++; n=mx+1; for(int i=0;i<n;i++)A[i]={cnt[i],0}; for(m=2*n-1,n=1;n<=m;n<<=1); for(int i=0;i<n;i++)r[i]=r[i/2]/2+(i&1)*n/2; fft(A,n,1); for(int i=0;i<n;i++)A[i]=A[i]*A[i]; fft(A,n,-1); memset(sum,0,sizeof(sum)); for(int i=0;i<2*mx+1;i++){ way[i]=((int)(A[i].real()+0.5)-(i%2==0&&i/2<mx+1)*cnt[i/2])/2; } sum[0]=way[0];for(int i=1;i<2*mx+1;i++)sum[i]=sum[i-1]+way[i]; n=nn; int tot=0; for(int i=1;i<=n;i++)tot+=sum[a[i]]; int Cn3=n*(n-1)%mod*(n-2)%mod*qpow(6,mod-2)%mod; int ans=((Cn3-tot)%mod+mod)%mod*qpow(Cn3,mod-2)%mod; cout<<ans<<'\n'; } signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int _;cin>>_; while(_--){ solve(); } return 0; } -
3
#include<bits/stdc++.h> using namespace std; #define int long long #define fu(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) const int N=5e5+10,P=998244353; int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;} int A[N],B[N],C[N]; int cnt[N],a[N],sum_pairs[N]; void ntt(int s[],int n,int x) { if(n==1)return; int s1[n/2],s2[n/2]; fu(i,0,n/2-1)s1[i]=s[i*2],s2[i]=s[i*2+1]; ntt(s1,n/2,x*x%P);ntt(s2,n/2,x*x%P); for(int i=0,xi=1;i<n/2;i++,xi=xi*x%P) { s[i]=(s1[i]+s2[i]*xi)%P; s[i+n/2]=((s1[i]-s2[i]*xi)%P+P)%P; } } void calc(int s1[],int len1,int s2[],int len2,int s[]) { int D=1;while(D<len1+len2-1)D<<=1; int invD=qpow(D,P-2),x=qpow(3,(P-1)/D); ntt(s1,D,x);ntt(s2,D,x); fu(i,0,D-1)s[i]=s1[i]*s2[i]%P; int inv1=qpow(x,P-2); ntt(s,D,inv1); fu(i,0,D-1)s[i]=s[i]*invD%P; } void solve() { int n;cin>>n; fu(i,0,N-1)cnt[i]=0; fu(i,0,N-1)A[i]=B[i]=C[i]=sum_pairs[i]=0; int max_val=0; fu(i,0,n-1) { cin>>a[i]; cnt[a[i]]++; max_val=max(max_val,a[i]); } fu(i,1,max_val)A[i]=cnt[i]; fu(i,0,max_val)B[i]=cnt[i]; calc(A,max_val+1,B,max_val+1,C); int max_sum=2*max_val; fu(i,0,max_sum)sum_pairs[i]=C[i]; fu(i,0,n-1)sum_pairs[2*a[i]]=(sum_pairs[2*a[i]]-1+P)%P; fu(i,0,max_sum)sum_pairs[i]=sum_pairs[i]*qpow(2,P-2)%P; fu(i,1,max_sum)sum_pairs[i]=(sum_pairs[i]+sum_pairs[i-1])%P; int invalid=0; fu(i,0,n-1)if(a[i]<=max_sum)invalid=(invalid+sum_pairs[a[i]])%P; int total=n%P*((n-1)%P)%P*((n-2)%P)%P*qpow(6,P-2)%P; int valid=(total-invalid+P)%P; int ans=valid*qpow(total,P-2)%P; cout<<ans<<endl; } signed main() { int t;cin>>t; while(t--)solve(); return 0; } -
0
taojinghua LV 9 @ 2026-2-26 10:34:10
#include<bits/stdc++.h> using namespace std; #define ll long long const ll N=5e5+10,P=998244353; ll qpow(ll a,ll b) { ll res=1; for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P; return res; } ll a[N],b[N],c[N],cnt[N],p[N],A[N],t,n; void NTT(ll a[],ll n,ll x) { if(n==1)return; ll a1[n/2],a2[n/2]; for(ll i=0;i<n/2;i++)a1[i]=a[i*2],a2[i]=a[i*2+1]; NTT(a1,n/2,x*x%P);NTT(a2,n/2,x*x%P); for(ll i=0,xi=1;i<n/2;i++,xi=xi*x%P) { a[i]=(a1[i]+a2[i]*xi)%P; a[i+n/2]=((a1[i]-a2[i]*xi)%P+P)%P; } } void calc(ll a[],ll l1,ll b[],ll l2,ll c[]) { ll id=1<<(ll)log2(l1+l2-1)+1; ll x=qpow(3,(P-1)/id); NTT(a,id,x);NTT(b,id,x); for(ll i=0;i<id;i++)c[i]=a[i]*b[i]%P; NTT(c,id,qpow(x,P-2)); for(ll i=0;i<id;i++)c[i]=c[i]*qpow(id,P-2)%P; } int main() { scanf("%lld",&t); while(t--) { scanf("%lld",&n); for(ll i=0;i<N;i++)a[i]=b[i]=c[i]=cnt[i]=p[i]=0; ll ma=0; for(ll i=0;i<n;i++) { scanf("%lld",&A[i]); cnt[A[i]]++;ma=max(ma,A[i]); } for(ll i=1;i<=ma;i++)a[i]=cnt[i]; for(ll i=0;i<=ma;i++)b[i]=cnt[i]; calc(a,ma+1,b,ma+1,c); ll ma2=ma*2; for(ll i=0;i<=ma2;i++)p[i]=c[i]; for(ll i=0;i<n;i++)p[2*A[i]]=(p[2*A[i]]-1+P)%P; for(ll i=0;i<=ma2;i++)p[i]=p[i]*qpow(2,P-2)%P; for(ll i=1;i<=ma2;i++)p[i]=(p[i]+p[i-1])%P; ll v=0; for(ll i=0;i<n;i++)if(A[i]<=ma2)v=(v+p[A[i]])%P; ll sum=n%P*((n-1)%P)%P*((n-2)%P)%P*qpow(6,P-2)%P; ll va=(sum-v+P)%P; printf("%lld\n",va*qpow(sum,P-2)%P); } return 0; } -
-1
duanjiahui2024
LV 10
@ 2026-2-26 9:54:16
#include<bits/stdc++.h> using namespace std; #define int long long const int N=100005,P=998244353,L=262144; const double PI=acos(-1.0); int qpow(int a,int b){int r=1;for(;b;b>>=1,a=a*a%P)if(b&1)r=r*a%P;return r;} struct C{double x,y;C(double _x=0,double _y=0):x(_x),y(_y){}C operator+(const C& b)const{return C(x+b.x,y+b.y);}C operator-(const C& b)const{return C(x-b.x,y-b.y);}C operator*(const C& b)const{return C(x*b.x-y*b.y,x*b.y+y*b.x);}}; int r[L],c[N],a[N],s[L+5];C A[L]; void i(){for(int i=0;i<L;i++)r[i]=(r[i>>1]>>1)|((i&1)<<17);} void f(C* a,int on){for(int i=0;i<L;i++)if(i<r[i])swap(a[i],a[r[i]]);for(int h=2;h<=L;h<<=1){C wn(cos(2*PI/h),sin(2*PI/h*on));for(int j=0;j<L;j+=h){C w(1,0);for(int k=j;k<j+h/2;k++){C u=a[k],t=w*a[k+h/2];a[k]=u+t;a[k+h/2]=u-t;w=w*wn;}}}if(on==-1)for(int i=0;i<L;i++)a[i].x/=L;} void solve(){int n,m=0;scanf("%lld",&n);memset(c,0,sizeof c);memset(s,0,sizeof s);for(int i=0;i<L;i++)A[i]=C(0,0);for(int i=0;i<n;i++){scanf("%lld",&a[i]);c[a[i]]++;m=max(m,a[i]);}for(int i=1;i<=m;i++)if(c[i])A[i]=C(c[i],0);f(A,1);for(int i=0;i<L;i++)A[i]=A[i]*A[i];f(A,-1);for(int i=0;i<L;i++)s[i]=(int)(A[i].x+0.5);for(int i=0;i<n;i++)s[2*a[i]]--;for(int i=0;i<L;i++)s[i]/=2;for(int i=1;i<L;i++)s[i]+=s[i-1];int inv=0;for(int i=0;i<n;i++)if(a[i]<L)inv+=s[a[i]];int t=n*(n-1)*(n-2)/6;printf("%lld\n",(t-inv)%P*qpow(t%P,P-2)%P);} signed main(){i();int t;scanf("%lld",&t);while(t--)solve();return 0;}
Yangzhichao
LV 10
@ 2026-2-26 11:03:09
- 1
