Codeforces Round 1070 (Div. 2) A~D F

最近手感差的很，A能WA两发写20min，D调不出来，不过看别人的AC代码dp思路跟自己也不太一样…还是自己太菜了，加训div2了。

A. Operations with Inversions

Given an arraya1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​. In one operation, you can choose a pair of indicesi,ji, ji,jsuch that1≤i<j≤n1 \le i < j \le n1≤i<j≤n,ai>aja_i > a_jai​>aj​, and remove the element at indexjjjfrom the array. After that, the size of the array will decrease by111, and the relative order of the elements will not change.

Determine the maximum number of operations that can be performed on the array if they are applied optimally.

真是糖丸了，第一遍读错题了，后来发现思路错了，应该直接O(n2)O(n^2)O(n2)扫的。

voidsolve(){intn;cin>>n;vector<int>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];intans=0;vector<int>st(n+1);for(inti=1;i<=n;i++){for(intj=i+1;j<=n;j++){if(a[i]>a[j]){st[j]=1;}}}cout<<accumulate(range(st),0LL)<<endl;}

B. Optimal Shifts

You are given a binary strings1s2…sns_1s_2 \ldots s_ns1​s2​…sn​, containing at least one 1. You want to obtain a binary string of the same length, consisting only of 1s. To do this, you can perform the following operation any number of times:

Choose a numberddd(1≤d≤n1 \le d \le n1≤d≤n) and consider the stringtttas a cyclic right shift of the stringsssbyddd, or, more formally,t=sn−d+1…sns1…sn−dt = s_{n - d + 1} \ldots s_{n}s_{1} \ldots s_{n - d}t=sn−d+1​…sn​s1​…sn−d​. After that, for alljjjfor whichtj=1t_j = 1tj​=1, performsj:=1s_j := 1sj​:=1. The described operation costsdddcoins, wheredddis the chosen shift amount.

Note that the positionsjjjin the stringsss, where initiallysj=1s_j=1sj​=1, remain equal to111even iftj=0t_j=0tj​=0.

You need to determine the minimum number of coins that can be spent so that the stringsssconsists only of 1s after all operations.

看成一个环（首位相接），直接找相邻两个 1 中间有多少个 0;
也唐了，第一遍双指针没有更新 i 的位置，TLE了…

voidsolve(){intn;string s;cin>>n>>s;inti=0;intcnt1=0,cnt2=0;while(s[i]=='0'&&i<n)cnt1++,i++;i=n-1;while(s[i]=='0'&&i>=0)cnt2++,i--;intans=cnt1+cnt2;for(inti=0;i<n;i++){if(s[i]=='0'){intj=i+1;while(j<n&&s[j]=='0')j++;j--;ans=max(ans,j-i+1);i=j;}}cout<<ans<<endl;}

C. Odd Process

You havennncoins with denominationsa1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​and a natural numberkkk. You also have a bag, which is initially empty, where you can place coins. You need to perform exactlykkkactions. In each action, you take one coin from those you have left and put it in your bag. After that, you can no longer take that coin.

At the same time, you have a cat that loves even numbers, so every time the sum of the denominations of the coins in your bag becomes even, your cat empties the bag, meaning it takes all the coins to a place known only to it, and the bag is empty again. Note that the bag is emptied every time the sum becomes even during the process of adding coins, not just at the very last moment.

Let your score be the sum of the denominations of the coins in the bag. Your task is to performkkkactions such that your final score is maximized. Find the answer for all1≤k≤n1 \le k \le n1≤k≤n.

简单来讲，得发现：

首先选一个奇数，接着一直选偶数，这样才能保证最后的结果最优。
但是如果偶数个数加上奇数的 1，也就是 num_even + 1 > k，则还需要一些别的操作来抵消多余的 k，可以发现需要的抵消奇数个数等于，(k - num_even - 1 + 1) / 2 * 2，然后就是再判断一堆边界问题，有点小麻烦。。

voidsolve(){intn;cin>>n;vector<int>a(n+1);vector<vector<int>>vec(2,vector<int>(1,0));for(inti=1;i<=n;i++){cin>>a[i];vec[a[i]&1].push_back(a[i]);}autopre=vec;sort(range_(vec[1]));sort(range_(vec[0]));intno=vec[1].size()-1,ne=vec[0].size()-1;for(inti=1;i<=no;i++){pre[1][i]=pre[1][i-1]+vec[1][i];}for(inti=1;i<=ne;i++){pre[0][i]=pre[0][i-1]+vec[0][i];}for(intk=1;k<=n;k++){intans;if(ne+1<k){intnum=((k-ne-1+1)/2)*2;intk_=k-num;// evenif(num==no){ans=0;}else{ans=vec[1].back();inti=max(0LL,k_-1);if(i>ne||k_==0){ans=(k&1)?vec[1].back():0;}else{ans+=pre[0][ne]-pre[0][ne-(i)];}}}else{if(no==0){ans=0;}else{ans=vec[1].back();inti=k-1;ans+=pre[0][ne]-pre[0][ne-(i)];}}cout<<ans<<' ';}cout<<endl;}

D. Fibonacci Paths

You are given adirected graphconsisting ofnnnvertices andmmmedges. Each vertexvvvcorresponds to a positive numberava_vav​. Count the number of distinctsimple paths∗^{\text{∗}}∗consisting of at least two vertices, such that the sequence of numbers written at the vertices along the path forms a generalized Fibonacci sequence.

In this problem, we will consider that the sequence of numbersx0,x1,…,xkx_0, x_1, \ldots, x_kx0​,x1​,…,xk​forms a generalized Fibonacci sequence if:

• x0,x1x_0, x_1x0​,x1​are arbitrary natural numbers.
• xi=xi−2+xi−1x_i = x_{i - 2} + x_{i - 1}xi​=xi−2​+xi−1​for all2≤i≤k2 \le i \le k2≤i≤k.

Note that a generalized Fibonacci sequence consists of at least two numbers.

Since the answer may be large, output it modulo998 244 353998\,244\,353998244353.

∗^{\text{∗}}∗A simple path in a directed graph is a sequence of verticesv1,v2,…,vkv_1, v_2, \ldots, v_kv1​,v2​,…,vk​such that each vertex in the graph appears in the path at most once and there is a directed edge fromviv_ivi​tovi+1v_{i+1}vi+1​for alli<ki < ki<k.

挺好的一道题目，可惜没写出来。

对于图上的DP问题我们往往不知道怎么下手，说白了就是不知道怎么设置初始状态，因为图上往往有环

对于这道题我们其实可以看成一种类似拓扑的结构：
因为斐波那契一定是递增的，所以我们可以从最小的一批元素下手，再从它们进行扩展。

这里借助SPFA来写，记
f[u][val]表示以u为节点，拓展到下一个数列需要val的方案数是多少f[u][val] 表示以u为节点，拓展到下一个数列需要val的方案数是多少f[u][val]表示以u为节点，拓展到下一个数列需要val的方案数是多少

可以有转移
v为u的出点（u→v），当val=a[v]的时候，f[v][a[u]+a[v]]+=f[u][val]v为u的出点（u →v），当val = a[v]的时候，f[v][a[u] + a[v]] += f[u][val]v为u的出点（u→v），当val=a[v]的时候，f[v][a[u]+a[v]]+=f[u][val]

这里用 map<int, int> 来记录值（因为每个值的范围都是 long long，但是数量又很少），同时 建边的逻辑为e[u][val]表示从 u 出边，下一个值为 val 的点的集合。

注意这里不存在一个点只更新一次的情况，所以我们只用一个 st 记录某个状态是否在 heap 中，不在的话就加入，否则不加入。

不能按照 Dijkstra 的逻辑来，不然是错误的。

voidsolve(){intn,m;cin>>n>>m;vector<int>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];priority_queue<PII,vector<PII>,greater<PII>>heap;vector<map<int,vector<int>>>e(n+1);vector<map<int,int>>f(n+1);map<PII,bool>st;for(inti=0;i<m;i++){intu,v;cin>>u>>v;e[u][a[v]].push_back(v);f[v][a[u]+a[v]]++;if(st[make_pair(a[u]+a[v],v)]==0){st[make_pair(a[u]+a[v],v)]=1;heap.push({a[u]+a[v],v});}}intans=0;while(heap.size()){auto[ne,u]=heap.top();heap.pop();for(autov:e[u][ne]){if(st[make_pair(a[u]+a[v],v)]==0){st[make_pair(a[u]+a[v],v)]=1;heap.push({a[u]+a[v],v});}(f[v][a[u]+a[v]]+=f[u][ne])%=mod;}}for(inti=1;i<=n;i++){for(auto[_,c]:f[i]){(ans+=c)%=mod;}}cout<<ans%mod<<endl;}

F. Omega Numbers

For a given numbernnn, consider the functionω(n)\omega(n)ω(n), which is equal to the number of unique prime numbers in the prime factorization of the numbernnn.

For example,ω(12)=ω(22⋅3)=2\omega (12) = \omega (2^2 \cdot 3) = 2ω(12)=ω(22⋅3)=2. Andω(120)=ω(23⋅3⋅5)=3\omega (120) = \omega (2^3 \cdot 3 \cdot 5) = 3ω(120)=ω(23⋅3⋅5)=3.

For an array of natural numbersaaaand a natural numberkkk, we definef⁡(a,k)=∑i<jω(ai⋅aj)k\operatorname{f}(a, k) = \sum_{i < j} \omega(a_i \cdot a_j)^kf(a,k)=∑i<j​ω(ai​⋅aj​)kfor alli<ji < ji<j.

You are given an array of natural numbersaaaof lengthnnnand a natural numberkkk. Calculatef⁡(a,k)\operatorname{f}(a, k)f(a,k)modulo998 244 353998\,244\,353998244353.

很麻烦的一题。

首先要发现一个重要的性质，即ω(x⋅y)=ω(x)+ω(y)−ω(gcd⁡(x,y))\omega(x \cdot y) = \omega(x) + \omega(y) - \omega(\operatorname{gcd}(x,y))ω(x⋅y)=ω(x)+ω(y)−ω(gcd(x,y))

同时，对于[1,2∗105][1, 2*10^5][1,2∗105]这个范围内的整数，所有数字拥有质因子的个数都不会超过 7！

发现上述性质之后，我们可以将问题转化为：
按照 gcd 分类，统计 “恰好 gcd=g 且ω(ai)+ω(aj)=Sω(a_i)+ω(a_j)=Sω(ai​)+ω(aj​)=S” 的对数，然后它们的贡献就是(S−ω(g))k×对数(S−ω(g))^k×对数(S−ω(g))k×对数。

这样按组分开计算的方式会使得复杂度大大降低，可以通过题目的时间限制。

那么怎么分组呢？？

官方题解中给了如下做法：

cnt[x][len]:表示 数组中有多少个数 A，满足：A 能被 x 整除，且 ω(A) = len。

注意：

• len 指的就是 ω(A)（不同质因子个数）。
• cnt[x] 是对“能被 x 整除”的那些数组元素按 ω 值的分布统计。

为什么要这么统计？
因为如果gcd(ai,aj)=ggcd(a_i, a_j) = ggcd(ai​,aj​)=g，那么aia_iai​和aja_jaj​都可以被ggg整除。我们先统计“都能被 g 整除的数”的分布（这就是cnt[g]cnt[g]cnt[g]），再用这些数配对计算候选对数，最后用筛去掉 gcd 更大倍数的部分，得到 “恰好 gcd=g” 的对。

怎么统计呢？
就是直接暴力枚举，按照调和级数和质因子的个数枚举。

dp[g][sumlen]:临时的 dp[g][sumlen] 最终表示恰好 gcd(ai,aj) = g 且 ω(ai)+ω(aj) = sumlen 的 无序对数量（i < j 的对数）。

怎么得到呢？？

先用 cnt[g] 计算“被 g 同时整除的数之间的所有配对数”并按 sumlen = ω(ai)+ω(aj) 累加到 dp[g][sumlen]（这是包含了 gcd 可能为 g 的所有对，也包括 gcd 更大倍数的情况）。

• 如果 len1 != len2，贡献是 cnt[g][len1] * cnt[g][len2]（这些是有序配对数，实际我们只要无序对，所以在代码里枚举 len1 < len2 用乘积）。

• 如果 len1 == len2，贡献是 cnt[g][len] * (cnt[g][len] - 1) / 2（组合数，保证 i<j）。

然后用筛法（从大到小枚举 g）减去 dp[multiple_of_g][sumlen]，把那些 gcd 实际上是 2g, 3g, … 的对去掉，剩下的就是 gcd 恰好 等于 g 的对数。

最后由公式 ω(ai * aj) = sumlen - ω(g)，就可以直接分组算贡献了：

ANS += dp[g][sumlen] * pow(sumlen - ω(g), k);

大致思路如上，下面是代码：

consti64 mod=998244353;intdx[4]={0,1,0,-1},dy[4]={1,0,-1,0};intqpow(inta,intk){a%=mod;i64 res=1%mod;while(k){if(k&1)res=(i64)res*a%mod;a=(i64)a*a%mod;k>>=1;}returnres;}intinv(intx){returnqpow(x,mod-2);}staticconstexprintMAX_N=1e7;std::vector<int>minp,primes;voidsieve(intn){minp.assign(n+1,0);primes.clear();for(inti=2;i<=n;i++){if(minp[i]==0){minp[i]=i;primes.push_back(i);}for(autop:primes){if(i*p>n){break;}minp[i*p]=p;if(p==minp[i]){break;}}}}boolisprime(intn){returnminp[n]==n;}voidsolve(){intn,k,Maxa;cin>>n>>k;vector<int>a(n+1),w(n+1);for(inti=1;i<=n;i++)cin>>a[i];Maxa=*max_element(range_(a));vector<vector<int>>cnt(Maxa+1,vector<int>(10,0));for(inti=1;i<=n;i++){intx=a[i];intc=0;while(x>1){intp=minp[x];w[i]++;while(x%p==0)x/=p;}cnt[a[i]][w[i]]++;}for(intx=1;x<=Maxa;x++){for(inti=2;i*x<=Maxa;i++){for(intlen=0;len<=8;len++){(cnt[x][len]+=cnt[i*x][len])%=mod;}}}vector<vector<int>>f(Maxa+1,vector<int>(17,0));for(intx=1;x<=Maxa;x++){for(intsumlen=1;sumlen<=16;sumlen++){for(intlen1=0;len1<=8;len1++){intlen2=sumlen-len1;if(len2<0||len2>8)continue;if(len1>len2)continue;if(len1==len2){(f[x][sumlen]+=((cnt[x][len1]*(cnt[x][len2]-1)%mod)*inv(2)%mod))%=mod;}else{(f[x][sumlen]+=cnt[x][len1]*cnt[x][len2]%mod)%=mod;}}}}for(intx=Maxa;x>=1;x--){for(inti=2;i*x<=Maxa;i++){for(intlen=0;len<=16;len++){((f[x][len]-=f[x*i][len])+=mod)%=mod;}}}w.clear();for(intg=1;g<=Maxa;g++){intx=g;intcnt=0;while(x>1){intp=minp[x];cnt++;while(x%p==0)x/=p;}w[g]=cnt;}intans=0;for(intx=1;x<=Maxa;x++){for(intlen=1;len<=16;len++){(ans+=((qpow((len-w[x]+mod)%mod,k)%mod)*f[x][len])%mod)%=mod;}}cout<<ans<<endl;}signedmain(){cin.tie(nullptr)->ios::sync_with_stdio(false);intT=1;sieve(2e5+10);cin>>T;while(T--)solve();return0;}