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 # include 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; vectorint,int>> ans; for(int i = 1;i <= n;++i)//看看两个串是不是本身就为全0 { if(s1[i]!= '0'||s2[i] != '0') { ok = false; break; } } if(ok){ cout<<"YES"< cout<<0< 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"< return; } } if(s2[1] == '0'){ ans.push_back({1,n}); } else{ ans.push_back({1,1}); ans.push_back({2,n}); } cout<<"YES"< cout<size()< for(auto [x,y]:ans){ cout<" "< } } 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<
然后考虑每一位的贡献是怎么样的形式
我们写两组数据大概可以的到一下的思路：
因为是前缀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 # include 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<//二进制模拟第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<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; }