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;
}
标签：
留言评论