AC修炼计划（AtCoder Regular Contest 167）

传送门：AtCoder Regular Contest 167 - AtCoder

再次感谢樱雪喵大佬的题解，讲的很详细，Orz。

大佬的博客链接如下：Atcoder Regular Contest 167 - 樱雪喵 - 博客园 (cnblogs.com)

第一题很签到，就省略掉了。

第二题其实也不算难，要想清楚因子之间的关系（可是本人没长脑子被卡了俩小时）。通过分解质因数来得出最后的数有多少个因子，然后两两匹配，如果因子个数是奇数，说明存在完全平方数因子的情况，于是单独计算出这样的贡献。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
// void read(__int128 &x)
// {
//     x=0;
//     int f=1;
//     char ch;
//     if((ch=getchar())=='-') 
//     f=-f;
//     else 
//     x=x*10+ch-'0';//     while((ch=getchar())>='0'&&ch<='9')
//         x=x*10+ch-'0';
//     x*=f;
// }
// void print(__int128 x){//     if(x<0){
//         putchar('-');
//         x=-x;
//     }
//     if(x>9)
//         print(x/10);//     putchar(x%10+'0');
// }
int n,m;
int an;
int su[1000005];
bool c[1000005];void suu(int x){for(int i=2;i<=x;i++){if(!c[i])su[++an]=i;for(int j=1;j<=an&&su[j]*i<=x;j++){c[su[j]*i]=1;if(i%su[j]==0)break;}}
}
int kuai(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%N;b>>=1;a=a*a%N;}return ans%N;
}
void icealsoheat(){cin>>n>>m;int bn=n;if(m==0){cout<<0;return;}vector<PII>ve;for(int i=1;i<=an&&su[i]<=sqrt(n);i++){if(n%su[i]==0){ve.push_back({su[i],0});while(n>1&&n%su[i]==0){ve.back().second++;n/=su[i];}}}if(n>1){ve.push_back({n,1});}int sum=1;int cnt=0;for(auto [i,j]:ve){if(m%2==1&&j%2==1)cnt=1;sum=sum*(m%N*j%N+1ll)%N;}int ans=0;// ans=sum*kuai(2ll,N-2)%N*(m%N)%N;// // if(cnt==0)ans=(ans+m/2)%N;// if(cnt==0){//     ans=((ans-1)%N+N)%N;//     ans=ans=(ans+m/2)%N;// }if(cnt==0){sum=((sum-1)%N+N)%N;}ans=sum*kuai(2ll,N-2)%N*(m%N)%N;if(cnt==0)ans=(ans+m/2)%N;cout<<ans;}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();suu(1000000);int _;_=1;// cin>>_;while(_--){icealsoheat();}
}

C - MST on Line++

c，写着题的时候真的很想骂娘。没想到要在限制下标并且在各种顺序的情况下，还得考虑最小生成树的贡献。。。。。。。脑子快炸了，看大佬的代码，好不容易才磕出来。同时也学到了一种新思路。首先，计算这种排列组合题，一般都会想到求出每一个值对答案的贡献，然后相加。在用kruskal算法求最小生成树的时候，我们发现我们只用考虑边全值的大小，对其优先排列。那我们只要求出每一个Ai对应的有几个边的长度就好了。因为我们需要求的是最小值，所以，尽可能的让所有数小才是最优的，按照数值顺序来说，相邻的会尽可能的小。这里看Atcoder Regular Contest 167 - 樱雪喵 - 博客园 (cnblogs.com)

佬的博客吧，解释的特别清楚。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,k;
int an;
int a[500005];
int c[5005][5005];
int f[500005];
int be[500005];
void init(int mx)
{for(int i=0;i<=mx;i++)for(int j=0;j<=i;j++) c[i][j]=j?(c[i-1][j-1]+c[i-1][j])%N:1;
}
void icealsoheat(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);be[0]=1;for(int i=1;i<=n;i++){be[i]=be[i-1]*i%N;}for(int i=1;i<=n;i++){for(int j=1;j<=k;j++){f[i]=(f[i]+(i-1)*c[n-j][i-1]%N)%N;}f[i]=be[i]*be[n-i]%N*f[i]%N;}int ans=0;for(int i=1;i<=n;i++){ans=(ans+((f[i]-f[i-1])%N+N)%N*a[i]%N)%N;}cout<<ans;}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;init(5000);// cin>>_;while(_--){icealsoheat();}
}

D - Good Permutation

这道题最开始我是用优先队列来维护的，因为我们要找在改变次数最小的基础上，要求词序也要最小。我们不妨把所有的序列都涂上各自的颜色，看看有几种颜色，然后每个都取最小的那个，进行不断的替换。但出现了问题。因为存在会误删一些边和点的情况。

后来看了佬的思路，感觉很奇妙，通过并查集来找所有所有的环，然后用set去维护这个环的最小值，如果当前的最小值小于后面环的最小值的话，就替换并且将两个环合并。否则我们不希望字典序变大，尽量不换。但如果这是它所在连通块的最后一个位置，必须要换，那就找后面最小的环值来替换这个值。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int N=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,k;
int an;
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int col,tot,top,num;
// int co[200010];
// int dfn[200010];
// int low[200010];
// int a[200010];
int b[200005];
int pre[200005];
int fa[200005];
int c[200005];
int siz[200005];
int mn[200005];
set<PII>q;
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void icealsoheat(){cin>>n;q.clear();for(int i=1;i<=n;i++){cin>>b[i];pre[b[i]]=i;fa[i]=i;siz[i]=1;mn[i]=i;q.insert({i,i});}auto add=[&](int x,int y)->void{x=find(x);y=find(y);if(x==y)return;q.erase({mn[x],x});q.erase({mn[y],y});fa[x]=y;siz[y]+=siz[x];mn[y]=min(mn[x],mn[y]);q.insert({mn[y],y});};for(int i=1;i<=n;i++){add(i,b[i]);}// for(int i=1;i<=n;i++){// cout<<fa[i]<<"+++\n";// cout<<mn[fa[i]]<<"---\n";//     cout<<pre[b[fa[i]]]<<"\n";// }for(int i=1;i<=n;i++){if(q.size()==1)break;auto it=q.begin();if(find(it->second)==find(i))it++;if(it->first<b[i]||siz[find(i)]==1){int j=pre[it->first];// cout<<i<<":"<<j<<"\n";swap(b[j],b[i]);swap(pre[b[j]],pre[b[i]]);add(i,j);}siz[find(i)]--;}for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<"\n";    
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_=1;cin>>_;while(_--){icealsoheat();}
}