做qq代刷网站,做网站需要投标吗,百度网盘app官网,小程序做一个要多少钱传送门#xff1a;AtCoder Regular Contest 167 - AtCoder
再次感谢樱雪喵大佬的题解#xff0c;讲的很详细#xff0c;Orz。
大佬的博客链接如下#xff1a;Atcoder Regular Contest 167 - 樱雪喵 - 博客园 (cnblogs.com)
第一题很签到#xff0c;就省略掉了。
第二题…传送门AtCoder Regular Contest 167 - AtCoder
再次感谢樱雪喵大佬的题解讲的很详细Orz。
大佬的博客链接如下Atcoder Regular Contest 167 - 樱雪喵 - 博客园 (cnblogs.com)
第一题很签到就省略掉了。
第二题其实也不算难要想清楚因子之间的关系可是本人没长脑子被卡了俩小时。通过分解质因数来得出最后的数有多少个因子然后两两匹配如果因子个数是奇数说明存在完全平方数因子的情况于是单独计算出这样的贡献。
代码如下
#includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;
typedef pairint,int PII;
const int N998244353;
const int MX0x3f3f3f3f3f3f3f3f;
// void read(__int128 x)
// {
// x0;
// int f1;
// char ch;
// if((chgetchar())-)
// f-f;
// else
// xx*10ch-0;// while((chgetchar())0ch9)
// xx*10ch-0;
// x*f;
// }
// void print(__int128 x){// if(x0){
// putchar(-);
// x-x;
// }
// if(x9)
// print(x/10);// putchar(x%100);
// }
int n,m;
int an;
int su[1000005];
bool c[1000005];void suu(int x){for(int i2;ix;i){if(!c[i])su[an]i;for(int j1;jansu[j]*ix;j){c[su[j]*i]1;if(i%su[j]0)break;}}
}
int kuai(int a,int b){int ans1;while(b){if(b1)ansans*a%N;b1;aa*a%N;}return ans%N;
}
void icealsoheat(){cinnm;int bnn;if(m0){cout0;return;}vectorPIIve;for(int i1;iansu[i]sqrt(n);i){if(n%su[i]0){ve.push_back({su[i],0});while(n1n%su[i]0){ve.back().second;n/su[i];}}}if(n1){ve.push_back({n,1});}int sum1;int cnt0;for(auto [i,j]:ve){if(m%21j%21)cnt1;sumsum*(m%N*j%N1ll)%N;}int ans0;// anssum*kuai(2ll,N-2)%N*(m%N)%N;// // if(cnt0)ans(ansm/2)%N;// if(cnt0){// ans((ans-1)%NN)%N;// ansans(ansm/2)%N;// }if(cnt0){sum((sum-1)%NN)%N;}anssum*kuai(2ll,N-2)%N*(m%N)%N;if(cnt0)ans(ansm/2)%N;coutans;}
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)
佬的博客吧解释的特别清楚。
代码如下
#includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;
typedef pairint,int PII;
const int N998244353;
const int MX0x3f3f3f3f3f3f3f3f;
int n,k;
int an;
int a[500005];
int c[5005][5005];
int f[500005];
int be[500005];
void init(int mx)
{for(int i0;imx;i)for(int j0;ji;j) c[i][j]j?(c[i-1][j-1]c[i-1][j])%N:1;
}
void icealsoheat(){cinnk;for(int i1;in;i){cina[i];}sort(a1,a1n);be[0]1;for(int i1;in;i){be[i]be[i-1]*i%N;}for(int i1;in;i){for(int j1;jk;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 ans0;for(int i1;in;i){ans(ans((f[i]-f[i-1])%NN)%N*a[i]%N)%N;}coutans;}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_1;init(5000);// cin_;while(_--){icealsoheat();}
}
D - Good Permutation 这道题最开始我是用优先队列来维护的因为我们要找在改变次数最小的基础上要求词序也要最小。我们不妨把所有的序列都涂上各自的颜色看看有几种颜色然后每个都取最小的那个进行不断的替换。但出现了问题。因为存在会误删一些边和点的情况。
后来看了佬的思路感觉很奇妙通过并查集来找所有所有的环然后用set去维护这个环的最小值如果当前的最小值小于后面环的最小值的话就替换并且将两个环合并。否则我们不希望字典序变大尽量不换。但如果这是它所在连通块的最后一个位置必须要换那就找后面最小的环值来替换这个值。
代码如下
#includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;
typedef pairint,int PII;
const int N998244353;
const int MX0x3f3f3f3f3f3f3f3f;
int n,k;
int an;
#includestdio.h
#includestring.h
#includeiostream
#includealgorithm
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];
setPIIq;
int find(int x){if(fa[x]x)return x;return fa[x]find(fa[x]);
}
void icealsoheat(){cinn;q.clear();for(int i1;in;i){cinb[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{xfind(x);yfind(y);if(xy)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 i1;in;i){add(i,b[i]);}// for(int i1;in;i){// coutfa[i]\n;// coutmn[fa[i]]---\n;// coutpre[b[fa[i]]]\n;// }for(int i1;in;i){if(q.size()1)break;auto itq.begin();if(find(it-second)find(i))it;if(it-firstb[i]||siz[find(i)]1){int jpre[it-first];// couti:j\n;swap(b[j],b[i]);swap(pre[b[j]],pre[b[i]]);add(i,j);}siz[find(i)]--;}for(int i1;in;i)coutb[i] ;cout\n;
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_1;cin_;while(_--){icealsoheat();}
}
