本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-30 16:34:45
A
题意
给定一张 $n$ 个点，$m$ 条边的无向图。
对于每条边，你都要指定一个该边所属的点，且必须为其两个端点之一。
另外还需要满足，每个点最多拥有一个属于它的边。
求方案数，对 $10^9+7$ 取模。
思路
这道题看上去毫无头绪，但是能发现一些规律：
设 $edge$ 为联通块中边的数量，$node$ 为联通块中点的数量，$x_i$ 为第 $i$ 个联通块的方案数。
当 $edge = node - 1$ ，显然这是一棵树，不难发现 $x_i=n$。
当 $edge = node $ ，显然这是一棵基环树，不难发现 $x_i=2$ (自己手玩一下就知道了)。
当 $edge > node $ ，就是一个普通的图，显然无解，即 $x_i=0$。
我们所求的答案为 $\prod_{i=1}^{联通块的数量} x_i$。
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
using namespace std;
#define int long long
#define ll long long
#define Endl cout<<endl;
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define ls(rt) tr[rt].ch[0]
#define rs(rt) tr[rt].ch[1]
const int N=5e5+10;\/\/注意修改
const int mod=1e9+7;
const ll MAX=2e14+5;
const int M=2e7+10;
vector <int> ve[N];
int vis[N],node,edge;
void dfs(int x){
if(x){
node++;
vis[x]=1;
for(int i=0;i<ve[x].size();i++){
edge++;
if(!vis[ve[x][i]]) dfs(ve[x][i]);
}
}
}
signed main(){
int n,m,u,v,res=1,x;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v;
ve[u].push_back(v),ve[v].push_back(u);
}
for(int i=1;i<=n;i++){
edge=0,node=0;
if(!vis[i]){
dfs(i);
edge\/=2;
if(edge<node) x=node;
if(edge==node) x=2;
if(edge>node) x=0;
res*=x,res%=mod;
}
}
cout<<res%mod<<endl;
return 0;
}
B
题意
给定正整数 $n$，求 $1 \le x,y \le n$ 且 $\gcd(x,y)$ 是素数的数对 (x,y) 的数量。
思路
脑抽数论题。
形象化题意： $$\sum_{p\in prime}^{} \sum_{x=1}^{n} \sum_{y=1}^{n} \left [ \gcd(x,y) = p \right ] $$
不难发现，$\gcd(x,y)=p$ 和 $\gcd(\frac{x}{p} ,\frac{y}{p} )=1$ 是等价的。
于是可以将式子转化成
$$\sum_{p\in prime}^{} \sum_{x=1}^{\frac{n}{p}} \sum_{y=1}^{\frac{n}{p}} \left [ \gcd(x ,y )=1 \right ] $$
不难发现，这个式子具有对称性，即很多计算重复了两次，我们可以简化一下式子：
$$\sum_{p\in prime}^{} \sum_{x=1}^{\frac{n}{p}} (2\sum_{y=1}^{x} \left [ \gcd(x ,y )=1 \right ])-1 $$
-1 是因为 $x=y$ 这个情况，这个只应该被计算一次，而我们计算了两次，所以要减去一次。
而这个式子 $\sum_{y=1}^{x} \left [ \gcd(x ,y )=1 \right ]$ 就是欧拉函数。即 $\sum_{y=1}^{x} \left [ \gcd(x ,y )=1 \right ]=\ arphi (i)$
式子又可以转化为： $$\sum_{p\in prime}^{} 2(\sum_{x=1}^{\frac{n}{p}} \ arphi (i))-1 $$
最后要求的式子便为：
$$\sum_{p\in prime}^{} 2(\sum_{x=1}^{\frac{n}{p}} \ arphi (i))-1 $$
其中，欧拉函数可以利用前缀和优化思想 $\Theta(1)$ 直接求出。
而质数可以用欧拉筛线性求出。
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
using namespace std;
#define int long long
#define ll long long
#define Endl cout<<endl;
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define ls(rt) tr[rt].ch[0]
#define rs(rt) tr[rt].ch[1]
const int N=1e7+10;\/\/注意修改
const int mod=1e9+7;
const int M=2e5+10;
int prime[N],st[N],n,cnt=0,phi[N],s[N],ans;
void Pr(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(st[i]==0){
cnt++;
prime[cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
st[prime[j]*i]=1;
if(i%prime[j]==0) {
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
signed main(){
cin>>n;
Pr();
for(int i=1;i<=n;i++) s[i]=s[i-1]+phi[i];
for(int i=1;i<=cnt;i++) ans+=2*s[n\/prime[i]]-1;
cout<<ans;
return 0;
}
\/*
*\/
C
题意
思路
若这道题只有操作3,4 ,相信大家都会用树状数组完成。
而这道题要求逆序对的奇偶性，似乎没有什么数据结构能够维护。
但是我们仔细观察发现：交换任意两个数 $x$，$y$，逆序对奇偶性刚好相反。（这个具体手玩一下就行，需分类讨论，这里不在赘述）。
最难处理的操作是操作1，即区间交换。
$$.......aaadddddbbb.......$$
设 $a$ 序列的长度为 $n1$，$d$ 序列的长度为 $N$，$b$ 序列的长度为 $n2$。
将 $a$ 序列和 $b$ 序列交换，可以先将 $a$ 序列和 $d$ 序列交换，交换的次数为 $n1 \times N$。
交换后的序列为： $$.......dddddaaabbb.......$$
继续将 $a$ 序列和 $b$ 序列交换，交换的次数为 $n1 \times n2$。
交换后的序列为： $$.......dddddbbbaaa.......$$
最后将 $d$ 序列和 $b$ 序列交换，所需的操作次数为 $n2 \times N$。
总操作次数为： $n1 \times N + n1 \times n2 + n2 \times N$。
即：$ N (n1+n2) + n1 \times n2 $。
因为交换任意两个数 $x$，$y$，逆序对奇偶性刚好相反，所以该序列逆序对的奇偶性是基于$ N (n1+n2) + n1 \times n2 $ 之上。
而操作二可以转化为序列 $[l,r]$ 与 $[r+1,k]$ 的交换，不再赘述。
代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
using namespace std;
#define int long long
#define ll long long
#define Endl cout<<endl;
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define ls(rt) tr[rt].ch[0]
#define rs(rt) tr[rt].ch[1]
#define lowbit(x) x&(-x)
const int N=1e7+10;\/\/注意修改
const int mod=1e9+7;
const int Max=2e6+10;
int c[N],a[N];
void add(int x,int k){
for(int i=x;i<=Max;i+=lowbit(i)){
c[i]+=k;
}
}
int search(int x){
int s=0;
for(int i=x;i;i-=lowbit(i)) s+=c[i];
return s;
}
signed main(){
int n,q;
cin>>n>>q;
int f=0;
for(int i=1;i<=n;i++) {
cin>>a[i];
f^=search(Max-2)-search(a[i]);
add(a[i],1);
}
while(q--){
int op,k,l1,r1,l2,r2,n1,n2,N;
cin>>op;
if(op==1){
cin>>l1>>r1>>l2>>r2;
n1=r1-l1+1;
n2=r2-l2+1;
N=l2-r1-1;
f^=N*(n1+n2)+n1*n2;
}
if(op==2){
cin>>l1>>r1>>k;
n1=r1-l1+1;
n2=k-r1;
f^=n1*n2;
}
if(op==3){
int x;
cin>>x;
f^=search(Max-2)-search(x);
add(x,1);
}
if(op==4){
int x;
cin>>x;
f^=search(x);
add(x,1);
}
if(f&1) cout<<"odd"<<endl;
else cout<<"even"<<endl;
}
return 0;
}
\/*
*\/
鲁ICP备2025150228号