2023ICPC沈阳 M题 Outro: True Love Waits

- 3 mins read

题意

有一张无限大的图，每个整数都对应图上一个点。对两个整数，如果二进制仅有第i位不同，则它们有一条权重为i的边相连。 在图上移动时，规则是从目前所在点，走过权重最小的边到达下一个点，然后把这条边删掉。 输入s,t (二进制表示，长度<=1e6)和k，问若以s为起点，可否第k次到达t点？那时走了几步？ 对1e9+7取模。

分析及实现

手推规律后，发现有循环性。如下图：

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
typedef unsigned long long ull;

const int N = 1e5;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;

int qpow(int x, int k)
{
    int ret = 1;
    x %= MOD;
    while (k)
    {
        if (k & 1)
        {
            ret *= x;
            ret %= MOD;
        }
        x *= x;
        x %= MOD;
        k >>= 1;
    }
    return ret;
}

int inv(int x, int mod)
{
    return qpow(x, mod - 2);
}

map<int, int> mp;

void solve()
{
    string s, t;
    int k;
    cin >> s >> t >> k;
    if (t == s) /////
    {
        int INV = inv(3, MOD);
        int b1 = (1 + INV) % MOD;
        int ans = b1 * qpow(4, k - 1) % MOD;
        ans -= 1;
        ans += MOD;
        ans %= MOD;
        ans -= INV;
        ans += MOD;
        ans %= MOD;
        cout << ans << endl;
        return;
    }

    if (s.length() < t.length())
    {
        swap(s, t);
    }
    int n = s.length();
    int m = t.length();

    for (int i = m - 1; i >= 0; --i)
    {
        int j = i - m + n;
        s[j] = '0' + (s[j] - '0') ^ (t[i] - '0');
    }
    // s
    if (s.length() % 2 != 0)
    {
        s = "0" + s;
    } // 0123
   // cout << "s " << s << endl;
    int fir = 0;
    int base = 1;
    for (int i = s.length() - 1; i > 0; i -= 2)
    {
        int num = (s[i - 1] - '0') * 2 + s[i] - '0';
        if (i == s.length() - 1)
        {
            fir += (mp[num]) * base % MOD;
        }
        else
            fir += (mp[num] - 1) * base % MOD;
        fir %= MOD;
        base = (base * 4 + 1) % MOD;
    }
    fir -= 1;
    fir += MOD;
    fir %= MOD;
  //  cout << "fir " << fir << endl;

    int cnt00 = 0;
    for (int i = s.length() - 1; i > 0; i-=2)
    {
        if (s[i] == '0' && s[i - 1] == '0')
        {
            cnt00++;
        }
        if(s[i]=='1'||s[i-1]=='1')
        {
            break;
        }
    }
    if (1 + cnt00 < k)
    {
        cout << -1 << endl;
        return;
    }

    int INV = inv(3, MOD);
    int b1 = (1 + INV) % MOD;
    int ans = b1 * qpow(4, k - 1) % MOD; // add
    ans -= 1;
    ans += MOD;
    ans %= MOD;
    ans -= INV;
    ans += MOD;
    ans %= MOD;
    ans += fir;
    ans %= MOD;

    cout << ans << endl;
}

signed main()
{
    // cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    mp[0] = 1;
    mp[1] = 2;
    mp[3] = 3;
    mp[2] = 4;

    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; ++i)
    {
        solve();
    }
    return 0;
}
/*

*/

回顾