作者：CurryWOE
链接：https://zhuanlan.zhihu.com/p/667857302
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 3;
const int mod = 1e9 + 7;
const int inv3 = 333333336;
string s, t;
int k;
ll p[N];
long long fp(long long base,long long exponent)
{
    long long result=1;
    for(;exponent>0;exponent>>=1)
    {
        if(exponent&1)
            result=result*base%mod;
        base=base*base%mod;
    }
    return result;
}
int solve()//已将S调整为S异或T，且长度调整为偶数
{
    if (s.size() == 2 && s == "00")
        return (fp(4,k-1)-1+mod)%mod*4ll%mod*inv3%mod;
    int cnt=0;
    while(cnt<s.size() && s[cnt]=='0')
        ++cnt;
    if(cnt<k*2-2)
        return -1;
    ll ans = 0;
    for (int i = 1; i < s.size(); i += 2)
    {
        ll t;
        if (s[i - 1] == '0' && s[i] == '0')
            t = 0;
        else if (s[i - 1] == '1' && s[i] == '0')
            t = 1;
        else if (s[i - 1] == '1' && s[i] == '1')
            t = 2;
        else
            t = 3;
        ans += p[i / 2] * t % mod;
        if (ans >= mod)
            ans -= mod;
    }
    return (ans+(fp(4,k-1)-1+mod)%mod*4ll%mod*inv3%mod)%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    p[0] = 1;
    for (int i = 1; i < N; ++i)
        p[i] = (p[i - 1] * 4 + 1) % mod;
    int T;
    cin >> T;
    for (int kase = 1; kase <= T; ++kase)
    {
        cin >> s >> t >> k;
        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());
        while (s.size() < t.size())
            s += "0";
        while (t.size() < s.size())
            t += "0";
        for (int i = 0; i < s.size(); ++i)
            s[i] = (s[i] == t[i] ? '0' : '1');
        while (s.size() > 1 && s.back() == '0')
            s.pop_back();
        if (s.size() % 2 == 1)
            s += "0";
        cout << solve() << "\n";
    }
    return 0;
}

answer.code:4:1: error: extended character 。 is not valid in an identifier
    4 | 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
      | ^
answer.code:4:1: error: extended character 。 is not valid in an identifier
answer.code:1:1: error: ‘作者：CurryWOE’ does not name a type
    1 | 作者：CurryWOE
      | ^~~~~~~~~~~~~~
In file included from /usr/include/c++/13/iosfwd:42,
                 from /usr/include/c++/13/ios:40,
                 from /usr/include/c++/13/ostream:40,
                 from /usr/include/c++/13/iostream:41,
                 from answer.code:6:
/usr/include/c++/13/bits/postypes.h:68:11: error: ‘ptrdiff_t’ does not name a type
   68 |   typedef ptrdiff_t     streamsize; // Signed integral type
      |           ^~~~~~~~~
/usr/include/c++/13/bits/postypes.h:41:1: note: ‘ptrdiff_t’ is defined in header ‘<cstddef>’; did you forget to ‘#include <cstddef>’?
   40 | #include <cwchar> // For mbstate_t
  +++ |+#include <cstddef>
   41 | 
In file included from /usr/include/c++/13/bits/exception_ptr.h:38,
                 from /usr/include/c++/13/exception:164,
                 from /usr/include/c++/13/ios:41:
/usr/include/c++/13/new:126:26: error: declaration of ‘operator new’ as non-function
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/13/new:126:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/13/cwchar:44,
                 from /usr/include/c++/13/bits/postypes.h:40:
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:127:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  127 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/13/new:128:26: error: declaration of ‘operator new []’ as non-function
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/13/new:128:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  129 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/13/new:135:29: error: ‘std::size_t’ has not been declared
  135 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                             ^~~
/usr/include/c++/13/new:137:31: error: ‘std::size_t’ has not been declared
  137 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                               ^~~
/usr/include/c++/13/new:140:26: error: declaration of ‘operator new’ as non-function
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/13/new:140:44: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:140:52: error: expected primary-expression before ‘const’
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                    ^~~~~
/usr/include/c++/13/new:142:26: error: declaration of ‘operator new []’ as non-function
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/13/new:142:46: error: ‘size_t’ is not a member of ‘std’; did you mean ‘size_t’?
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/13/include/stddef.h:214:23: note: ‘size_t’ declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/13/new:142:54: error: expected primary-expression before ‘const’
  142 | _GLIBCXX_NODISC...