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输入 #13输出 #16说明/提示评测用例规模与约定对于30%30\%30%的评测用例n≤10n \leq 10n≤10对于所有评测用例1≤n≤1061 \leq n \leq 10^61≤n≤106。C实现#includebits/stdc.husingnamespacestd;#defineintlonglongconstintmod998244353,N1e75;intn,k,m,s,r;boolisp[N];intqpow(inta,inte){intres1;while(e){if(e1)resres*a%mod;aa*a%mod,e1;}returnres;}voidsolve(){cinn;for(inti2;in;i)isp[i]true;for(inti2;i*in;i){if(!isp[i])continue;for(intji*i;jn;ji)isp[j]false;}for(inti2;in;i)if(isp[i])k;mn-k;for(inti1;in;i)if(isp[i])s(s(m-i(r))*r(i-r)*(k1-r))%mod;intft1;for(inti2;in;i)ftft*i%mod;intp1m*(m-1)%mod*qpow(4,mod-2)%mod,p2s*qpow(k1,mod-2)%mod;intansft*((p1p2)%mod)%mod;coutans\n;}signedmain(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);solve();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容