题面
思路
先从特殊性质入手，考虑 \(s=0\) 的情况。
不难发现，路径是已经确定的，那么我们可以考虑手搓几步。
\[0000\longrightarrow0001\longrightarrow0011\longrightarrow0010\longrightarrow0000\longrightarrow0100\longrightarrow0101\cdots \]可以看出似乎是两个二进制位绑定在一起变化的，为了方便，我们不妨将其变作四进制。
\[00 \longrightarrow01\longrightarrow03\longrightarrow02\longrightarrow00 \\ \longrightarrow10\longrightarrow11\longrightarrow13\longrightarrow12\longrightarrow10 \\ \longrightarrow30\longrightarrow31\longrightarrow33\longrightarrow32\longrightarrow30 \\ \longrightarrow20\longrightarrow21\longrightarrow23\longrightarrow22\longrightarrow20 \\ \longrightarrow00\longrightarrow100\longrightarrow101\longrightarrow\cdots\\ \]规律已经很显然了，每一个四进制位都在做 \(0\rightarrow1\rightarrow3\rightarrow2\rightarrow0\)的重复运动。
接下来，我们考虑第二个特殊性质：如何得出第一次到达某个点的步数？（仍然假设从 \(0\) 开始）
不难发现，我们可以单独计算每一个四进制位对于结果的贡献。
假如说当前位是第 \(k\) 位（从 \(1\) 开始编号），值为 \(a\)，用 \(f(a)\) 表示 \(a\) 值出现的序号（根据重复运动的先后顺序），那么这一位的贡献 \(x\) 为：
\[x=f(a)\cdot\sum_{i=0}^{k-1}4^i \]整个数的步数就是每一位的贡献之和。上述公式容易理解，不做具体解释。
接下来，我们考虑多次到达的情况。
从本质来说，只有 \(0\) 能够被到达多次，而其他数字都只能到达一次。所以，重复到达的次数，必然是由这个数中的 \(0\) 决定的。
每一次重复，当且仅当这一位完成了一次循环，也就是从 \(0\) 到 \(0\) 的过程，并且此时其他位都没有发生改变。我们注意到当这一位回到 \(0\) 时，所有比它低的位上都只能是 \(0\)，因为当它刚好变回 \(0\)，比它低的位就全为 \(0\)，而它如果再走一步，就必须变化比它高的一位，这与此时其他位都没有发生改变的要求不符。
所以，重复到达的次数，与这个数末尾连续的 \(0\) 个数有关。因为每一位 \(0\) 都可以贡献一次重复，那么最大经过次数就是 \(z+1\)，其中 \(z\) 表示末尾连续 \(0\) 个数。注意到，\(0\) 是没有次数上限的。
下面考虑总步数，我们可以分成第一次到达的步数以及重复的步数。第一次到达的步数就是 \(k=1\)，那么考虑重复所需要的步数。
事实上，一次重复就是一次循环，每一位 \(0\) 都能贡献一次重复，并且是从低位到高位贡献。并且我们知道每一位进行一次循环的步数，那么我们就可以知道重复 \(k\) 次一共需要的步数。公式化地表示为：
\[X=\sum_{i=1}^{k-1}4^i \]至此，我们已经解决了特殊性质 \(s=0\) 的情况。那么我们考虑 \(s\ne 0\) 的情况。
不难发现，从 \(s\) 走到 \(t\) 等价于从 \(0\) 走到 \(s\oplus t\)。然后就没有然后了。
设 \(len_4\) 表示对应数的四进制位数，\(x_i(S)\)表示 \(S\) 在四进制下的第 \(i\) 位（从 \(1\) 开始编号），答案即为：
\[Ans=\sum_{i=1}^{len_4(s\oplus t)}(f(x_i(s\oplus t))\cdot \sum_{j=0}^{k-1}4^j)+\sum_{i=1}^{k-1}4^i \]实现
并没有什么需要特别讲的细节问题。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll mod=1e9+7;
const ll inv3=333333336;
string s,t;int k;
int xo[N],so[N>>1];
ll ans;
int tim[4]={0,1,3,2};
ll qpow(ll a,int b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
ll sk(ll k){
return (qpow(4,k+1)-1+mod)%mod*inv3%mod;
}
void solve(){
ans=0;
cin>>s>>t>>k;
reverse(s.begin(),s.end());
reverse(t.begin(),t.end());
int n=max(s.size(),t.size());
for(int i=0;i<n;i++){
if(i>=s.size())xo[i]=t[i]-'0';
else if(i>=t.size())xo[i]=s[i]-'0';
else xo[i]=(s[i]-'0')^(t[i]-'0');
so[i>>1]=0;
}
int m=-1,zr=-1;
for(int i=0;i<n;i++){
if(i&1)(so[i>>1]|=(xo[i]<<1));
else (so[i>>1]|=xo[i]);
if(so[i>>1]>0){
m=(i>>1);
if(zr==-1)zr=(i>>1);
}
}
m++;
if(m==0){
cout<<sk(k-1)-1<<"\n";
return;
}
if(k>zr+1){
cout<<-1<<"\n";
return;
}
for(int i=0;i<m;i++){
ans=(ans+sk(i)*tim[so[i]]%mod)%mod;
}
ans=(ans+sk(k-1)-1+mod)%mod;
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--)solve();
return 0;
}