AT_arc154_a [ARC154A] Swap Digit原题链接[ARC154A] Swap Digit分析最开始居然没有转成数字真的烫废了正解#includebits/stdc.h#defineintlonglong#definemod998244353usingnamespacestd;constintN200005;intn;string A,B;intpw[N];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;cinA;cinB;for(inti0;in;i){if(A[i]-0B[i]-0){swap(A[i],B[i]);}}// cout A B \n;inta0,b0;pw[0]1;for(inti1;in;i){pw[i]pw[i-1]*10%mod;}for(intj0,in-1;jni0;j,i--){a(a(A[j]-0)*pw[i]%mod)%mod;b(b(B[j]-0)*pw[i]%mod)%mod;}couta*b%mod;}LGP17283 「IXOI R2」Retribution ~ Cycle of Redemption ~原题链接「IXOI R2」Retribution ~ Cycle of Redemption ~分析还是没有什么头绪……感觉就是直接贪就是你要是选了一些然后尽可能避开0 00……以此类推吧……我们从[ 1 , n ] [1,n][1,n]枚举x xx发现答案单调不降。然后拿双指针直接维护mex ⁡ \operatorname{mex}mex即可。正解#includebits/stdc.husingnamespacestd;constintN1000005;intn,q,r;vectorinte[N];intsz[N],mx[N];voiddfs(intu,intfa){sz[u]1;for(autov:e[u]){if(vfa)continue;dfs(v,u);sz[u]sz[v];mx[u]max(mx[u],sz[v]);}}intans[N];signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnqr;for(inti1,u,v;in;i){cinuv;e[u].push_back(v);e[v].push_back(u);}dfs(r,-1);intpos0;for(inti1;in;i){while(posnn-sz[pos]mx[pos]i)pos;ans[i]pos;}for(intcs1,x;csq;cs){cinx;coutans[x]\n;}}AT_arc154_e [ARC154E] Reverse and Inversion原题链接[ARC154E] Reverse and Inversion分析咋全是黑逆序对……别急那反转之后岂不是恰好反过来了我似乎感受到了什么……难道说我的期望之和好像就是这个的权值……这个好像是真的居然是诈骗吗对于单个的f ( p ) ∑ i 1 n ( i 2 − i × p i ) f(p)\sum\limits_{i1}^{n}{(i^2-i\times p_i)}f(p)i1∑n​(i2−i×pi​)这个需要结合这是一个排列来理解。p i p_ipi​位置的期望为n 1 2 \dfrac{n1}{2}2n1​那么直接做完了。正解#includebits/stdc.h#defineintlonglong#definemod998244353usingnamespacestd;constintN200005;intn,m,p[N];intqpow(inta,intb){intres1;while(b){if(b1)resres*a%mod;aa*a%mod;b1;}returnres;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(inti1;in;i){cinp[i];}inttotn*(n1)/2%mod;intinvtotqpow(tot,mod-2);intinv2(mod1)/2;intans0;for(inti1;in;i){intAi*(i-1)/2%mod;intB(n-i)*(n-i1)/2%mod;inttmp(AB)%mod*invtot%mod;ans(ansi*i%mod)%mod;intqqpow(tmp,m);ans(ans-(q*p[i]%mod*i%mod(1-qmod)%mod*p[i]%mod*(n1)%mod*inv2%mod)%modmod)%mod;}coutans*qpow(tot,m)%mod\n;}