A-签到题

注意到， $lcm(a_{i},a_{i+1})=\frac{a_{i}\cdot a_{i+1}}{gcd(a_{i},a_{i+1})}\le a_{i}\cdot a_{i+1}$ ，故 $S\ge 0$ 。

对任意的 $i(1\le i \le n)$ ，令 $a_{i}=i$ ，则 $gcd(a_{i},a_{i+1})=1$ ，此时 $S=0$ 。

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)printf("%d ",i);
	return 0;
}

B-Bob的蛋糕店

设Alice拿走的蛋糕分别是第 $i_{1},...,i_{k}$ 个，根据质心公式有 $\frac{\sum_{j=1}^{n}j\cdot m_{j}}{\sum_{j=1}^{n}m_{j}}=\frac{\sum_{j=1}^{k}i_{j}\cdot m_{i_{j}}}{\sum_{j=1}^{k}m_{i_{j}}}$ ,直接模拟即可。

复杂度为 $O(\binom{n}{k})$ 。

注意：为了避免精度问题，判断 $\frac{\sum_{j=1}^{n}j\cdot m_{j}}{\sum_{j=1}^{n}m_{j}}=\frac{\sum_{j=1}^{k}i_{j}\cdot m_{i_{j}}}{\sum_{j=1}^{k}m_{i_{j}}}$ 时，交叉相乘再相减等于零即可。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[25],A,B,fl,q[25];
void dfs(int deep,int x){
	if(deep==k+1){
		int sum=0;
		for(int i=1;i<=k;i++)
			sum+=B*a[q[i]]*q[i]-A*a[q[i]];
		if(sum==0)fl=1;
		return ;
	}
	for(int i=x;i<=n+deep-k;i++){
		q[deep]=i;
        dfs(deep+1,i+1);
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i],A+=a[i]*i,B+=a[i];
	dfs(1,1);
    if(fl)cout<<"Yes";
    else cout<<"No";
	return 0;
}

C-修复排列

题目核心需求

给定两个排列 $p$ （初始排列）和 $d$ （修复用排列），每次破坏会将 $id[1..i]$ 位置的 $p$ 变为 $0$ 。需通过 “用 $d[j]$ 替换 $p[j]$ ” 的操作，将 $p$ 恢复为 $1 - n$ 的排列，求第 $i$ 次破坏后最少的操作次数（每次答案独立计算）。

核心思路

要恢复排列，关键是解决 “修复值重复” 问题：破坏位置 $id[1..i]$ 必须修复（ $0$ 不能在排列中），修复值为 $d[id[k]]$ ；

但 $d[id[k]]$ 可能在原 $p$ 的未破坏位置存在（比如 $d[id[1]]=2$ ，原 $p[2]=2$ 未破坏，会重复）；

需追踪这种 “重复冲突链”：修复一个位置后，若其修复值在原 $p$ 中对应位置未处理，需继续修复该位置，直到无新冲突。

代码通过以下工具实现该逻辑：

$mp[x]$ ：记录值 $x$ 在原排列 $p$ 中的下标（因 $p$ 是排列，每个 $x$ 唯一对应一个下标）；

$set<int> st$ ：记录 “必须修复的值”（每个值对应唯一位置， $st$ 的大小即为最少操作次数，避免重复处理冲突链）。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fixed(x) fixed<<setprecision(x)
const int N=2e5+5;
int main(){
   int n;cin>>n;
   vector<int>p(n+1),id(n+1),d(n+1);
   for(int i=1;i<=n;i++)cin>>p[i];
   for(int i=1;i<=n;i++)cin>>id[i];
   for(int i=1;i<=n;i++)cin>>d[i];
   map<int,int>mp;
   for(int i=1;i<=n;i++)mp[p[i]]=i;
   set<int>st;
   for(int i=1;i<=n;i++){
   	int x=d[id[i]];
   	while(st.find(x)==st.end()){
   		st.insert(x);
   		x=d[mp[x]];
   	}
   	cout<<st.size()<<' ';
   }
   return 0;
}

D-图G

根据 $gcd$ 的性质，当且仅当 $b_{i}\cdot b_{j}|a_{i},b_{i}\cdot b_{j}|a_{j}$ 时，点 $i$ 和点 $j$ 连有一条边。

即： $b_{j}|\frac{a_{i}}{b_{i}},b_{i}|\frac{a_{j}}{b_{j}}$ 。

设 $f[x][y]$ 表示任意的 $i<j$ ，满足 $b_{i}=x,b_{j}=y,b_{j}|\frac{a_{i}}{b_{i}}$ 的个数，当 $x|\frac{a_{j}}{b_{j}}$ 时，跟点 $j$ 连有边的点 $i$ 有 $f[x][b_{j}]$ 个。

复杂度为 $O(nB)$ 。

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1005;
int n,a[N],b[N];
ll ans,f[M][M];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=1;i<=n;i++){
		if(a[i]%b[i]==0){
			a[i]/=b[i];
			for(int j=1;j<=1000;j++){
				if(a[i]%j==0){
					ans+=f[j][b[i]];
					f[b[i]][j]++;
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

E-小R的min

根据 $S(x)$ 的定义，易得：对于任意的 $l,r(L \le l \le r \le R)$ ，将 $f(l,r)$ 按升序排序后，当 $x$ 为中位数时， $S(x)$ 最小。记 $len=\frac{(R-L+1)\cdot (R-L+2)}{2}$ ，故求第 $k$ 小的数 $(k=\lfloor \frac{len+1}{2} \rfloor)$ 。

对于每次询问，我们可以考虑二分中位数 $x$ ，找到最小的 $x$ 满足 $k \le \sum_{L\le l \le r\le R} [f(l,r)\le x]$ 。

虽然 $\sum_{L\le l \le r\le R} [f(l,r)\le x]$ 不好计算，但是注意到 $f(l,r)$ 的单调性，我们可以考虑容斥，即： $\sum_{L\le l \le r\le R} [f(l,r)\le x]=\sum_{1\le l \le r\le R} [f(l,r)\le x]+\sum_{L\le l \le r\le n} [f(l,r)\le x]+\sum_{1\le l<L ,R<r \le n} [f(l,r)\le x]-\sum_{1\le l \le r\le n} [f(l,r)\le x]$ .

对于任意的 $l,r(1 \le l \le r \le n)$ ，我们可以先 $O(n^{2})$ 预处理出 $f(l,r)$ .

设 $b[r][x]=\sum_{1\le l \le r}[f(l,r)\le x]$ ，根据 $f(l,r)$ 的单调性， $b[r][x]$ 还表示最大的 $l(l \le r)$ 满足 $f(l,r)\le x$ ，故可以二分 $l$ ，在 $O(\log(n))$ 内计算出 $b[r][x]$ ，而 $\sum_{1\le l \le r\le R} [f(l,r)\le x]=\sum_{1\le r\le R}b[r][x]$ 即 $b[r][x]$ 的前缀和。因为 $x$ 是中位数，而且 $f(l,r)$ 必定是数组 $a$ 中的数，所以只需要预处理数组 $a$ 中的数即可，离散化后总复杂度为 $O(n^{2}\log(n))$ 。

同理，我们也可以预处理 $\sum_{L\le l \le r\le n} [f(l,r)\le x]$ 。

最后，当 $L\le b[R][x]$ 时，对于任意的 $1\le l<L,R<r\le n$ ，有 $f(l,r)\le f(l,R)\le x$ ，故 $\sum_{1\le l<L ,R<r \le n} [f(l,r)\le x]=(L-1)\cdot (n-R)$ ；当 $b[R][x]<L$ 时，对于任意的 $L\le l\le r\le R$ ，有 $x<f(L,R)\le f(L,r)\le f(l,r)$ ，故 $\sum_{L\le l \le r\le R} [f(l,r)\le x]=0$ 。

复杂度为 $O((n^{2}+m)\log(n))$ 。

不过，内测的时候发现常数较小的 $O(nm)$ 做法刚好可以通过，赛时发现许多选手 $O(n^{3})$ 也通过了...

 #include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,a[N],f[N][N],sl[N][N],sr[N][N],b[N][N];
bool check(int l,int r,int x,int k){
	int sum=0;
	if(b[r][x]>=l)sum=sl[r][x]+sr[l][x]+(l-1)*(n-r)-sl[n][x];
	return sum>=k;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		int mi=a[i];
		for(int j=i;j<=n;j++){
			mi=min(mi,a[j]);
			f[i][j]=mi;
		}
	}
	sort(a+1,a+n+1);
	int len=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<=len;i++) {
		for(int j=1;j<=n;j++){
			int l=0,r=j,mid;
			while(l<r){
				mid=(l+r+1)>>1;
				if(f[mid][j]<=a[i])l=mid;
				else r=mid-1;
			}
			sl[j][i]=sl[j-1][i]+l;
			b[j][i]=l;
		}
		for(int j=n;j;j--){
			int l=j,r=n+1,mid;
			while(l<r){
				mid=(l+r)>>1;
				if(f[j][mid]<=a[i])r=mid;
				else l=mid+1;
			}
			sr[j][i]=sr[j+1][i]+n+1-l;
		}
	}
	int L,R,k;
	while(m--){
		scanf("%d%d",&L,&R);
		k=((R-L+1)*(R-L+2)/2+1)/2;
		int l=1,r=len,mid;
		while(l<r){
			mid=(l+r)>>1;
			if(check(L,R,mid,k))r=mid;
			else l=mid+1;
		}
		printf("%d\n",a[l]);
	}
	return 0;
}

F-种树

首先，我们先证明一个结论： $\sum_{k=0}^{\infty} \lfloor \frac{n+2^{k}}{2^{k+1}} \rfloor=n$ 。

设 $n=\sum_{i=0}^{t}a_{i}\cdot 2^{i}$ ，其中 $a_{t}=1,a_{i}\in \{0,1 \}$ 。

$\sum_{k=0}^{\infty} \lfloor \frac{n+2^{k}}{2^{k+1}} \rfloor=\sum_{k=0}^{t} \lfloor \frac{n+2^{k}}{2^{k+1}} \rfloor=\sum_{k=0}^{t} (\lfloor \frac{\sum_{i=0}^{k}a_{i}\cdot 2^{i}+2^{k}}{2^{k+1}} \rfloor+ \lfloor \sum_{i=k+1}^{t}a_{i}\cdot 2^{i-k-1} \rfloor)=\sum_{i=0}^{t}([ a_{i} == 1] +a_{i}\cdot \sum_{k=0}^{i-1}2^{k})=\sum_{i=0}^{t}a_{i}\cdot 2^{i}=n$ 。

即求： $\sum_{i=1}^{n}\sum_{j=1}^{n}i\cdot j [gcd(i,j)==1]$ 。

接着，对该式子进行莫比乌斯反演：

$\sum_{i=1}^{n}\sum_{j=1}^{n}i\cdot j [gcd(i,j)==1]=\sum_{i=1}^{n}\sum_{j=1}^{n}i\cdot j \cdot \sum_{d|gcd(i,j)}\mu(d)=\sum_{d=1}^{n}d^{2}\mu(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor }i\cdot \sum_{j=1}^{\lfloor \frac{n}{d}\rfloor }j=\sum_{d=1}^{n}d^{2}\mu(d)\cdot (\frac{\lfloor \frac{n}{d}\rfloor\cdot(\lfloor \frac{n}{d}\rfloor+1)}{2})^{2}$ 。

最后，我们可以用杜教筛计算出结果：

设 $S(n)=\sum_{d=1}^{n}d^{2}\mu(d),f(n)=n^{2}\mu(n),g(n)=n^{2}$ 。

因为 $\sum_{i=1}^{n}(f*g)(i) =\sum_{i=1}^{n}\sum_{d|i}g(d)f(\frac{i}{d})=\sum_{i=1}^{n}i^{2}[i==1]=1$ ，

所以 $S(n)=1-\sum_{i=2}^{n}i^{2}S(\lfloor \frac{n}{i}\rfloor)$ 。

复杂度为 $O(n^{\frac{2}{3}})$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+80,mod=1e9+7;
const ll inv3=333333336,inv2=500000004;
ll n,mu[N],p[N],M=1e6;
bool flg[N];
ll sum(ll x){
	return x%mod*(x%mod+1)%mod*inv2%mod;
}
ll sum2(ll x){
	x%=mod;
	return x*(x+1)%mod*(x*2%mod+1)%mod*inv2%mod*inv3%mod;
}
void init(){
	int top=0;
	mu[1]=1;
	for(int i=2;i<=M;i++){
		if(!flg[i]){
			p[++top]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=top&&p[j]*i<=M;j++){
			flg[p[j]*i]=true;
			if(i%p[j]==0){
				mu[i*p[j]]=0;
				break;
			}
			mu[i*p[j]]=-mu[i];
		}
	}
	for(ll i=1;i<=M;i++)mu[i]=(mu[i]*i%mod*i%mod+mu[i-1])%mod;
}
map<ll,ll> mp;
ll SF(ll x){
	if(x<=M)return mu[x];
	if(mp[x])return mp[x];
	ll ans=1;
	for(ll l=2,r;l<=x;l=r+1){
		r=x/(x/l);
		ans=(ans-(sum2(r)-sum2(l-1))%mod*SF(x/l)%mod)%mod;
	}
	return mp[x]=(ans+mod)%mod;
}
int main() {
	scanf("%lld",&n);
	M=min(M,n),init();
	ll ans=0;
	for(ll l=1,r;l<=n;l=r+1){
		ll x=n/l,y=sum(x);
		r=n/x;
		ans=(ans+y*y%mod*(SF(r)-SF(l-1))%mod)%mod;
	}
	printf("%lld",(ans+mod)%mod);
	return 0;
}

牛客练习赛148题解