Codeforces Round 885 (Div. 2) F. Vika and Wiki（数学，倍增）

题目链接：https://codeforces.com/problemset/problem/1848/F

大致题意：

长度为n（n是2的幂次），每轮让a【i】 = a【i】^a【i%n + 1】，（^为异或）问需要操作多少次后可以使得每个数为0；

解题思路：

我们来观察：

第一次相当于：a【i】 = a【i】^ a【i+1】，a【i+1】 = a【i+1】^ a【i+2】

第二次相当于：a【i】 = a【i】^ a【i+2】，a【i+2】 = a【i+2】^a【i+4】

第四次相当于：a【i】 = a【i】 ^a【i+4】，a【i+4】 = a【i+4】 ^a【i+8】

...................

于是我们可以观察到，进行x（x是2的幂次）操作后，相当于a【i】 = a【i】 ^a【i+x】；

所以当进行n次后，结果一定是都为0，故一定是有解的；

那么我们可以通过倍增去解决这个问题了；

时间复杂度：O（nlogn）

代码如下：

#include<bits/stdc++.h>

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int n; std::cin >> n;
    std::vector<int> a(n, 0), b(n, 0);
    for (int i = 0; i < n; ++i)std::cin >> a[i];

    int cnt = 0;
    for (int i = 0; i < n; ++i)cnt += (a[i] == 0);

    if (cnt == n) { std::cout << "0\n"; return 0; }

    int ans = 1;

    int k = log2(n);

    for (int i = k - 1; i >= 0; --i)
    {
        for (int j = 0; j < n; ++j)
            b[j] = (a[j] ^ a[(j + (1ll << i)) % n]);

        cnt = 0;
        for (int j = 0; j < n; ++j)cnt += (b[j] == 0);

        if (cnt < n)ans += (1ll << i), a = b;
    }

    std::cout << ans << "\n";

    return 0;
}

通过异或的结合律，然后推出上面那个结论后，此题当然就迎刃而解啦：）