526互联

AtCoder Regular Contest 167

发布时间 2023-10-18 13:08:19作者: 空気力学の詩

Preface

补一下上周日的ARC，因为当天白天和队友一起VP了一场所以就没有精力再打一场了

这场经典C计数不会D这种贪心乱搞反而是一眼秒了，后面的EF过的太少就没看

A - Toasts for Breakfast Party

用一个类似于蛇形的放法就好了，比如对于\(n=9,m=5\)，放法为：

5 6 7 8 9
4 3 2 1

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,m,a[N],b[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (sort(a+1,a+n+1,greater <int>()),j=1,i=m;i>=1;--i) b[i]=a[j++];
	for (i=1;i<=m&&j<=n;++i) b[i]+=a[j++]; LL ans=0;
	for (i=1;i<=m;++i) ans+=1LL*b[i]*b[i];
	return printf("%lld",ans),0;
}

B - Product of Divisors

首先将\(A\)质因数分解，设\(A=p_1^{c_1}\times p_2^{c_2}\times \cdots\times p_k^{c_k}\)

考虑质因子\(p_1\)对答案的贡献，\(A^B\)中\(p_1\)的次数为\(\prod_{i=2}^k (c_i\times B+1)\times (0+1+2+\cdots+c_1\times B)\)

除去原来\(A\)中\(p_1\)的次数\(c_1\)后得到答案为\(\frac{B}{2}\times \prod_{i=1}^k (c_i\times B+1)\)，不难发现对于所有的质因数得到的都是这个结果

但我们还要注意到这个式子中除以\(2\)的部分不一定能整除，因此我们需要讨论一下：

  • 当\(B\)为偶数时，直接计算即可
  • 当\(B\)为奇数时，若存在某个\(c_i\)为奇数，那么亦直接计算即可
  • 当\(B\)为奇数时，且所有\(c_i\)均为偶数时，将分子部分减\(1\)后再除以\(2\)才是答案（因为要下取整）
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,mod=998244353,inv2=(mod+1)/2;
int A,B,ans;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; scanf("%lld%lld",&A,&B); bool has_odd=0; ans=B%mod;
	for (i=2;i*i<=A;++i) if (A%i==0)
	{
		int c=0; while (A%i==0) A/=i,++c;
		ans=ans*(B%mod*c%mod+1)%mod;
		if (c&1) has_odd=1;
	}
	if (A>1) ans=ans*(B%mod+1)%mod,has_odd=1;
	if (B%2==0||has_odd) (ans*=inv2)%=mod;
	else ans=(ans-1+mod)*inv2%mod;
	return printf("%lld",ans),0;
}

C - MST on Line++

龟龟经典一上计数就做不来，纯躺好等着队友C了属于是

考虑将点权从小到大排序，不难发现我们不关心每个点的具体权值，只要算出最后排名为\(i\)的点贡献的次数即可

考虑用克鲁斯卡尔算法求MST的过程，我们总是尽可能的用权值小的边来连接独立的连通块

因此不妨这样考虑，设\(f_i\)表示只用前\(i\)个点时图中最多能选出的不成环的边数，则答案为：

\[\sum_{i=2}^n (f_i-f_{i-1})\times a_i \]

因此现在问题转化为求\(f_i\)，考虑先枚举确定一个\(i\)，那么排名前\(i\)小的点对应的下标则构成一个集合\(S\)

要计算\(S\)中的点最多能连出多少边，我们可以先将\(S\)中的元素升序排列

此时不难发现对于一对相邻的元素\(S_i,S_{i+1}\)，若\(S_{i+1}-S_i\le k\)，则这两点之间就可以连边，不难发现这样可以得到不成环且最多的连边数量

考虑怎么统计合法的\(S\)的数量，不妨先考虑第一个元素和第二个元素之间的贡献

我们把问题抽象为，给定一个长度为\(i\)的序列，序列中的元素升序排列且值域均为\([1,n]\)，且满足第二个元素与第一个元素之差为\(k\)，求最后合法的序列数量

发现如果没有差的限制的话这个问题的答案就是\(C_n^i\)，而现在有了这个限制相当于就是把第二个数和第一个数合并，因此方案数为\(C_{n-k}^{i-1}\)

同时我们发现对于第\(i\)个元素和第\(i+1\)个元素间的差为\(k\)的答案均是上面的式子，而我们最后要求的是\(\le k\)的限制，因此可以写出贡献的表达式

\[(i-1)\times \sum_{j=1}^k C_{n-j}^{i-1} \]

但同时我们还要推一下对于给定的\(S\)集合它对应的排列的个数，这个很容易发现就是\(i!\times (n-i)!\)，因此最后有：

\[f_i=i!\times (n-i)!\times (i-1)\times \sum_{j=1}^k C_{n-j}^{i-1} \]

不难发现暴力计算这个式子的复杂度为\(O(nk)\)，符合题目要求

PS：当然可以把后面的组合数用公式化简得到一个\(O(n)\)计算答案的式子，但不是本题想考察的地方因此就不care了

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=5005,mod=998244353;
int n,k,a[N],fact[N],ifac[N],f[N],ans;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
	if (n<0||m<0||n<m) return 0;
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (sort(a+1,a+n+1),init(n),i=1;i<=n;++i)
	{
		int ret=0; for (j=1;j<=k;++j) (ret+=C(n-j,i-1))%=mod;
		f[i]=1LL*fact[i]*fact[n-i]%mod*(i-1)%mod*ret%mod;
	}
	for (i=1;i<=n;++i) (ans+=1LL*(f[i]-f[i-1]+mod)*a[i]%mod)%=mod;
	return printf("%d",ans),0;
}

D - Good Permutation

做这场之前看了下榜发现比赛时D过的比C多，所以补题的时候先写了D，不得不说确实如此

这题思路很顺畅，先找出原排列的所有置换环，不难发现题目的要求就是让所有所有元素在一个置换环内，而一次交换操作实际上就是合并两个置换环

考虑如何实现字典序最小这一限制，经典的做法就是从前往后扫，贪心地确定每一位能取的最小值

我们这里的解决方法也是类似，每次考虑求出在当前位置\(i\)后面且和当前位置上的数不在一个置换环中最小的那个数\(j\)

如果\(j<i\)的话则把这两个数交换一定是最优的，否则就忽略掉等后面的数来完成合并操作

但这样只能处理一部分情况，对于形如\(2,1,4,3\)这样的情况是无法处理的，因此还需要完成合并的要求

由于经过了之前的过程我们发现对于同一个集合的数通过交换无法使得答案变优，因此在只能变劣的情况下我们贪心地从后往前处理即可

如果当前数和它后面的所有数不在一个集合内，就把这个数和后面所有数中最小的那个交换即可

用并查集维护集合关系即可，总复杂度\(O(n\times \alpha(n))\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,p[N],pos[N],fa[N],vis[N];
int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d",&p[i]),pos[p[i]]=i,fa[i]=i,vis[i]=0;
		for (i=1;i<=n;++i) if (!vis[i])
		for (vis[j]=1,j=p[i];j!=i;j=p[j]) vis[j]=1,fa[getfa(p[j])]=getfa(p[i]);
		for (i=1;i<=n;++i) vis[i]=0;
		for (i=j=1;i<=n;++i)
		{
			while (j<=p[i]&&getfa(j)==getfa(p[i])) ++j;
			if (j>p[i]) continue; fa[getfa(j)]=getfa(p[i]);
			pos[p[i]]=pos[j]; swap(p[i],p[pos[j]]); pos[j]=i;
		}
		int mi=p[n]; for (i=n-1;i>=1;--i)
		{
			bool flag=p[i]<mi; int tmp=p[i];
			if (getfa(p[i])!=getfa(mi)) 
			fa[getfa(mi)]=getfa(p[i]),pos[p[i]]=pos[mi],swap(p[i],p[pos[mi]]),pos[mi]=i;
			if (flag) mi=tmp;
		}
		for (i=1;i<=n;++i) printf("%d%c",p[i]," \n"[i==n]);
	}
	return 0;
}

Postscript

数数苦手表示Atcoder越做越煎熬了……