7.30 mx 模拟赛题解

· · 个人记录

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 ]=\varphi (i)

式子又可以转化为：

\sum_{p\in prime}^{} 2(\sum_{x=1}^{\frac{n}{p}} \varphi (i))-1

最后要求的式子便为：

\sum_{p\in prime}^{} 2(\sum_{x=1}^{\frac{n}{p}} \varphi (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

题意

P8849

思路

若这道题只有操作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;
}

/*

 */