P12237 [蓝桥杯 2023 国 Java A] 质数排序
题目描述
我们定义质数排序为将一个序列中的所有下标为质数的位置进行升序排序，其它位置上的数不变。
例如，对8,7,6,5,4,3,2,18, 7, 6, 5, 4, 3, 2, 18,7,6,5,4,3,2,1进行质数排序会得到8,2,4,5,6,3,7,18, 2, 4, 5, 6, 3, 7, 18,2,4,5,6,3,7,1。给定nnn，求1∼n1 \sim n1∼n的每个排列进行质数排序后的逆序对的数量的和。由于结果很大，你只需要输出答案对998244353998244353998244353取模的结果即可。
输入格式
输入一行包含一个整数nnn。
输出格式
输出一行包含一个整数表示答案。
输入输出样例 #1
输入 #1
3输出 #1
6说明/提示
评测用例规模与约定
- 对于30%30\%30%的评测用例，n≤10n \leq 10n≤10；
- 对于所有评测用例，1≤n≤1061 \leq n \leq 10^61≤n≤106。
C++实现
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintmod=998244353,N=1e7+5;intn,k,m,s,r;boolisp[N];intqpow(inta,inte){intres=1;while(e){if(e&1)res=res*a%mod;a=a*a%mod,e>>=1;}returnres;}voidsolve(){cin>>n;for(inti=2;i<=n;i++)isp[i]=true;for(inti=2;i*i<=n;i++){if(!isp[i])continue;for(intj=i*i;j<=n;j+=i)isp[j]=false;}for(inti=2;i<=n;i++)if(isp[i])k++;m=n-k;for(inti=1;i<=n;i++)if(isp[i])s=(s+(m-i+(++r))*r+(i-r)*(k+1-r))%mod;intft=1;for(inti=2;i<=n;i++)ft=ft*i%mod;intp1=m*(m-1)%mod*qpow(4,mod-2)%mod,p2=s*qpow(k+1,mod-2)%mod;intans=ft*((p1+p2)%mod)%mod;cout<<ans<<"\n";}signedmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);solve();return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
