CodeTON Round 3 (C.差分维护，D.容斥原理)

2022 年 11 月 7 日
笔记
菜鸡的算法路

C. Complementary XOR

题目大意：

给你两个01串ab，问你是否可以通过一下两种操作在不超过n+5次的前提下将两个串都变为0，同时需要输出可以的操作方案

选择一个区间[l,r]
将串a的[l,r]翻转(0 $\rightarrow$ 1,1 $\rightarrow$0)，同时将b的[1,l)和（r,n]区间翻转

解题思路：

通过写两组样例，我们可以尝试这种思路，因为我们需要输出可以的操作方案，我们很难去考虑同时操作a,b两个串的操作，所以我们尝试只考虑a串。将a串的全部0变成1，观察b串经过这种操作后的结果。
我们可以发现，如果a串全为1，那b串此时有三种可能：

全为0
全为1
即含1，又含0

我们发现状况1可以通过对a进行一次[1,n]操作使a，b都为0
状况2可以通过对a进行一次[1,1],[2,n]操作使a,b都为0（观察最后一个样例）
但是状况3我们没有任何办法使得a，b都为0

自此整个题目分析完毕，我们只需要记录让a全部为1的操作对b的影响，最后看b串是否属于情况1,2即可

我们观察操作对b的影响是对[1,l)和（r,n]整个的影响，所以可以理解为对[1,l)和（r,n]操作次数都+1，因为翻转2次等于没翻转，（只有翻转奇数次才会真的翻转），因为是对整个区间+1，所以就可以考虑用差分维护（O(1)）

操作影响如下，假如选择的区间为[i,i],对b的影响就是b[1] += 1;b[i]-=1;b[i+1] += 1;

代码实现：

# include<iostream>
# include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 2e5 + 10, inf = 1e9 + 7;
int b[N];
int a[N];
void solve() {
	int n;
	cin>>n;
	for(int i = 1;i <= n+1;++i) b[i] = a[i] = 0;
	string s1,s2;
	cin>>s1>>s2;
	s1 = "?"+s1;
	s2 = "?"+s2;
	bool ok = true;
	vector<pair<int,int>> ans;
	for(int i = 1;i <= n;++i)//看看两个串是不是本身就为全0
        {
		if(s1[i]!= '0'||s2[i] != '0') {
			ok = false;
			break;
		}
	}
	if(ok){
		cout<<"YES"<<endl;
		cout<<0<<endl;
		return;
	}
	for(int i = 1;i <= n;++i){
		if(s1[i] == '0'){
			ans.push_back({i,i});
			b[1] += 1;//差分维护对b的影响
			b[i]-=1;
			b[i+1] += 1;
		}
	}
	for(int i = 1;i <= n;++i){
		a[i] = a[i-1]+b[i];//前缀和计算对每个位置的影响
	}
	for(int i = 1;i <= n;++i){
		if(a[i]&1){//如果操作次数为奇数则进行变化
			if(s2[i] == '0') s2[i] = '1';
			else s2[i] = '0';
		}
	}
	for(int i = 1;i <= n;++i){
		if(s2[i] != s2[1])//非（全0或者全1）
                {
			cout<<"NO"<<endl;
			return;
		}
	}
	if(s2[1] == '0'){
		ans.push_back({1,n});
	}
	else{
		ans.push_back({1,1});
		ans.push_back({2,n});
	}
	cout<<"YES"<<endl;
	cout<<ans.size()<<endl;
	for(auto [x,y]:ans){
		cout<<x<<" "<<y<<endl;
	}
	
	
	
}
int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;
	cin >> tt;
	while (tt--)solve();


	return 0;
}

D. Count GCD

题目大意：

对于给定n,m，给你一个含n个数的数组，数组中每个数的取值范围在[1,m]

问能构造多少组数组b满足一下条件：

b[i] $\in$[1,m]
gcd(b[1],b[2],…,b[i]) = a[i]

解题思路：

基本看到构造多少组b满足以上条件的就可以考虑原数组每一位的贡献了，类似于组合数学是每一位的贡献的积为总的组数
所以总的框架就是

        int ans = 1;
	for(int i = 2;i <= n;++i){
		if(a[i] == a[i-1]){
                        int t = m/a[i];//当前这一位的贡献
			ans = ans*t%mod;//总贡献
		}
		else{
			int t = cal(a[i-1]/a[i],m/a[i]);//当前这一位的贡献
			ans = ans*t%mod;
		}
	}
	cout<<ans<<endl;

然后考虑每一位的贡献是怎么样的形式
我们写两组数据大概可以的到一下的思路：
因为是前缀gcd，所以明显每个数的质因子是不断变小的，然后我们如果要求解b[i]
就有如下思路：gcd(a[i-1],b[i]) = a[i]
那我们要求的其实就是a[i]的倍数，比如a[i-1] = 6,a[i] = 3,那能够满足g(6,b[i]) = 3的只有3的倍数（3,6,9,12,15…..k*3<= m）,但是我们很容易就发现6,12是不能选的gcd(6,6||12) = 6，同理如果m/a[i] (所有的倍数)包含a[i-1]/a[i]的质因子的时候就都不能选

所以，问题可以转化为：从[1，m/a[i]]中选与（a[i-1]/a[i])互质的数有多少个

于是引入容斥原理：

Tot = C$_n$$^1$ – C$_n$$^2$ + C$_n$$^3$…..

用韦恩图表示如下：

所以我们就考虑用总的（m/a[i])-res（所有与a[i-1]/a[i]不互质的数的并集）

之所以取与a[i-1]/a[i]不互质的数的并集是因为它比较好表示，用（m/a[i])/（选中的因子的积)就是不互质数的数量
比如从1,2,3,4,5,6中求与2,3不互质的数
实际上就是6-（2的倍数（{2,4,6} $\rightarrow$6/2 = 3）+3的倍数（{3,6} $\rightarrow$6/3 = 2）-（2*3）的倍数（{6} $\rightarrow$6/6 = 1）） = 6-3-2+1 = 2{1,5}

代码实现：

# include<iostream>
# include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 2e5 + 10, mod = 998244353;
int a[N];
//在[1,top]范围内，找和n互质的数的个数 
int cal(int n,int top){
	vector<pair<int,int>> divisors;//质因子
	for(int i = 2;i*i<=n;++i){
		if(n%i == 0){
			int s  = 0;
			while(n%i == 0) n/=i,s++;
			divisors.push_back({i,s});//i的s次 
		} 
	} 
	if(n>1) divisors.push_back({n,1});
	
	int res = 0,m = divisors.size();
	for(int i = 1;i< (1<<m);++i)//二进制模拟第j个元素选还是不选
      {
		int t = 1,s = 0;
		for(int j = 0;j < m;++j){
			if(i>>j&1){
				if(t*divisors[j].first>top){
					t = -1;
					break;
				}
				t *= divisors[j].first;
				s++;
			}
		}
		if(t != -1)
                {
			if(s%2) res += top/t;//如果选了奇数个元素就是加
			else res -= top/t;//偶数个元素是减
                                          //从容斥原理可以得到
		}
	}
	return top-res;
}

void solve() {
	int n,m;
	cin>>n>>m;
	for(int i = 1;i <= n;++i) cin>>a[i];
	for(int i = 2;i <= n;++i){
		if(a[i-1]%a[i]){
			cout<<0<<endl;
			return;
		}
	}
	int ans = 1;
	for(int i = 2;i <= n;++i){
		if(a[i] == a[i-1]){
			ans = ans*(m/a[i])%mod;
		}
		else{
			int t = cal(a[i-1]/a[i],m/a[i]);
			ans = ans*t%mod;
		}
	}
	cout<<ans<<endl;
	
}
int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;
	cin >> tt;
	while (tt--)solve();


	return 0;
}

Tags: 菜鸡的算法路