Codeforces Round #822 (Div. 2)
Problem F. Zeros and Ones
解法
定义：\(f(x)\)为在\(S\)串中位置为\(x\)的值。显然\(f(x)\in 0,1\)
有一重要性质：若\(f(x)\)为1，那么二进制拆分下的\(x\)的1个个数一定为奇数
注意：这里的x是从0开始的，即：样例是从0开始的
证明：
我们设\(k\)为满足\(k<=x\)且\(k\)为2次幂的最大值。每个数\(x\)都可以看成是一种递推过程，每次消除这个数最大位上的1。
若消除了奇数次，由于我们已知\(f(0)=0\),而0异或奇数次1为1，于是\(f(x)\)为1；反之为0；
证毕
我们设\(T\)为总代价，很显然答案就等于：
\(T=\sum_{i=0}^{m-1}f(i)⊕ f(i+n)\)
式子又可进一步化简为:\(T=\sum_{i=0}^{m-1}f(i⊕(i+n))\)
原因：
若\(f(i)⊕f(i+n)\)为1，即：一个数二进制分解后有奇数个1，另一个数二进制分解后有偶数个1.那么它们的异或后一定也是为奇数个1，于是答案不变；
若\(f(i)⊕f(i+n)\)为0，则同理异或后一定为0，于是答案不变
综上所述，其化简后为等价式子
那么，我们知道了这个式子又该去怎么计算呢？
不妨构造一个矩阵\(M\),其规模大小为\(2^i*2^i\),初始\(M=0\),
定义：在矩阵中第\(r\)行第\(c\)列的数值为：\(M_r,_c=f(r)⊕f(c)\)
于是式子就变成了在这个矩阵中，从\((0,n)\)开始往右下角走\(m\)步的总和，即长度为\(m\)的对角线之和
给出一种构造\(M\)矩阵的方式：
\(M_i=\)
\[\left[ \begin{matrix} M_{i-1} & \overline{M_{i-1}} \\ \overline{M_{i-1}} & M_{i-1} \end{matrix} \right] \]下划线表示为全部取反过后的值。例如:\(i=2\)时，其\(M\)矩阵为：
\[\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{matrix} \]原因：取反的原因是因为其扩大之后相当于二进制上多了一位(\(f(i)\)或\(f(i+n)\))，多了一个1就自然要取反
右下角不取反是因为它是取反再取反，抵消掉了，并不是没有取反
同时，我们再定义矩阵\(C_i\),其定义为以\(2^i*2^i\)为一个单元格，类似于颜色反转之类的。例如，当\(C_i\)中的\(i\)为\(0,1,2\)时，其如下图：
C0:
.*.*.*.*
*.*.*.*.
.*.*.*.*
*.*.*.*.
.*.*.*.*
*.*.*.*.
.*.*.*.*
*.*.*.*.
C1:
..**..**
..**..**
**..**..
**..**..
..**..**
..**..**
**..**..
**..**..
C2:
....****
....****
....****
....****
****....
****....
****....
****....
'*'=1,'.'=0
有公式:\(M_{n+1}=\sum_{i=0}^{n}C_n⊕\)
证明：
观察可知，当\(i⊕(i+n)\)中第k位为1时（拥有第0位）。那么对应的\(C_i\)的对应位置\((i,i+n)\)也为1(这主要是源于二进制，由于\(C_i\)满足二进制的分解)
m（对角线长度）是非常大的，但是我们的\(C_i\)却和二进制有着不可分割的关系，那么我们有没有什么办法使得m缩小呢？
我们可以使用分治的思想，具体实现步骤如下：
若\(m\)%2为1，那么我们可以直接算出一个值，使得m减1
若\(m\)%2为0：
当\(n\)%2为0时，我们将\(C0\)删除，同时剩下的\(C\)均缩小2倍。即\(C_1->C_0,C_2->C_1...\)以此类推。
既然我们的矩阵缩小了，那么答案也要相应变换。由于这时m为偶数，其除以二后仍然为偶数，位置也为偶数，顺便统计一下1的个数，于是\(ans=solve(n/2,m/2)*2\),
当\(n\)%2为1时，我们仍然将\(C\)缩小两倍。但是由于n不是一个偶数的原因，原先的对角线会变成两条：\(solve(n/2,m/2)和solve(n/2+1,m/2)\)
但是，它的答案统计是统计0的个数，这是因为你将\(C_0\)删除后，对于偶数并没有影响，毕竟是0；但对于奇数，是为1的。若你这时统计了1的个数，就会因为少算了\(C_0\)而导致答案错误，刚好相反！
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,m;
map<pair<int,int>,int>q;
int count(int x){
int res=0;
while(x){
res++;
x=(x&(x-1));
}
return res;
}
int solve(int x,int y){
if(y==0)return 0;
if(y==1)return count(x)&1;
if(y%2==1){
int val=solve(x,y-1);
int t=count((y-1)^(x+y-1))&1;
return val+t;
}
if(q[{x,y}])return q[{x,y}];
int s1,s0;//1系数 0系数
int val1,val0;
if(x%2==0){
s1=2,s0=0;
val1=solve(x/2,y/2);
val0=y/2-val1;
}
else{
s1=0,s0=1;
val1=solve(x/2,y/2)+solve(x/2+1,y/2);
val0=y-val1;
}
int ans=s1*val1+s0*val0;
q[{x,y}]=ans;
return ans;
}
signed main(){
cin>>t;
while(t--){
scanf("%lld%lld",&n,&m);
printf("%lld\n",solve(n,m));
}
return 0;
}