C – Sasha and a Bit of Relax

其实这道题是一道大水题。我们知道成立条件为\(x_l \text{ xor } x_{l+1} \dots x_{mid} = x_{mid+1} \text{ xor } x_{mid+2} \dots x_{r}\)，然而这个运算可以直接移项：因为\(xor\)是自己本身的逆运算。然后为了保证\(r-l+1\)为偶数，我们只需要在 Trie 树末端维护奇偶计数即可。

// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 * 20 + 20000;
int trie[MAX_N][2], tot = 1, sum[MAX_N], n, even[MAX_N], odd[MAX_N];
void insert(int num, int id)
{
    int p = 1;
    for (int i = 30; i >= 0; i--)
    {
        int bit = (num >> i) & 1;
        if (trie[p][bit] == 0)
            trie[p][bit] = ++tot;
        p = trie[p][bit];
    }
    if (id & 1)
        odd[p]++;
    else
        even[p]++;
}
int find(int num)
{
    int p = 1;
    for (int i = 30; i >= 0; i--)
    {
        int bit = (num >> i) & 1;
        if (trie[p][bit] == 0)
            return -1;
        p = trie[p][bit];
    }
    return p;
}
int main()
{
    scanf("%d", &n);
    long long ans = 0;
    insert(0, 0);
    for (int r = 1; r <= n; r++)
    {
        scanf("%d", &sum[r]), sum[r] ^= sum[r - 1];
        int id = find(sum[r]);
        if (id != -1)
            if (r & 1)
                ans += odd[id];
            else
                ans += even[id];
        insert(sum[r], r);
    }
    printf("%lld", ans);
    return 0;
}

D – Sasha and One More Name

这道题思路很清奇。

首先，通过人类智慧得知答案只有\(\text{无解}, 1, 2\)三种，然后分别进行讨论：

1. 如果有某个字母的个数达到了惊人的\(n-1\)或者\(n\)个，那么直接判无解。
2. 之后考虑进行\(O(n)\)枚举断点，左边和右边部分断开之后重新拼接：左部分的左边拼到右部分的右边。这个很容易判。总复杂度为\(O(n^2)\)。
3. 剩下的结果就是\(2\)了。

// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5050;
char str[MAX_N];
long long ans, n, cnt[26];

void goFuck() { printf("Impossible"), exit(0); }

int main()
{
    scanf("%s", str + 1), n = strlen(str + 1);
    char opt = str[1];
    string st = str + 1;
    for (int i = 1; i <= n; i++)
        cnt[str[i] - 'a']++;
    for (int i = 0; i < 26; i++)
        if (cnt[i] == n || cnt[i] == n - 1)
            goFuck();
    for (int i = 1; i < n; i++)
    {
        bool flag = true;
        string sub = st.substr(i) + st.substr(0, i);
        for (int pt = 0; pt < sub.length(); pt++)
            if (sub[pt] != sub[sub.length() - pt - 1])
            {
                flag = false;
                break;
            }
        if (flag && sub != st)
            printf("1"), exit(0);
    }
    printf("2");
    return 0;
}

F – Sasha and Interesting Fact from Graph Theory

这道题很有意思。

先考虑 A、B 在一条链上，我们先来搞这条链的情况：

考虑这条链上点个数（除了 A、B）的取值范围为\( [0, min(n – 2, m – 1)] \)，我们统计答案时枚举\(i\)为链内部的点的个数（除了 A、B）。不考虑边权只考虑点的个数和排列方式，一共有：

\[ \sum_{i = 0}^{min(n – 2, m – 1)} P(n – 2, i) \]

考虑链上边权和恒为\(m\)，维持这一性质之后答案变为：

\[ \sum_{i = 0}^{min(n – 2, m – 1)} P(n – 2, i) {m – 1 \choose i} \]

因为这条链在生成树上，且其他边权可以在\([1, m]\)中任意选择，所以答案就是：

\[ ans = \sum_{i = 0}^{m – 1} P(n – 2, i) * {m – 1 \choose i} * m^{n-2-i} * n^{n – 3 – i}(i+2) \]

其中需要证明生成树个数为\(n^{n – 3 – i}(i+2)\)：

证明  对于这棵树，我们可以把点划分为\(n – i – 2 + 1\)个点集：对于链上的点可以划分为一个大小为\(i + 2\)的点集，剩余每个点自为一个点集。每两个点集连边的方法数为\(|S_1|*|S_2|\)。所以一共为：

\[ \sum_{p 为 Prufer 序列} \prod_i size[i]^{di} = \sum_{p 为 Prufer 序列} \prod_i size[i]^{di – 1} \prod size[i] \]

因为：

\[ n^{n – 2} = \sum_i d_i-1 \]

所以：

\[ n^{n – 3 – i}(i+2) \]

// F.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 2000, mod = 1e9 + 7;
ll level[MAX_N], level_rev[MAX_N], n, m, tmpx, tmpy;

ll quick_pow(ll bas, ll tim)
{
    if (tim < 0)
        return quick_pow(bas, tim + mod - 1);
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}

ll P(ll a, ll b)
{
    return level[a] * level_rev[a - b] % mod;
}

ll comb(ll a, ll b)
{
    return level[a] * level_rev[b] % mod * level_rev[a - b] % mod;
}

int main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &tmpx, &tmpy);
    ll ans = 0;
    // preprocessing;
    level[1] = level_rev[1] = level[0] = level_rev[0] = 1;
    for (int i = 2; i < MAX_N; i++)
        level[i] = level[i - 1] * i % mod;
    level_rev[MAX_N - 1] = quick_pow(level[MAX_N - 1], mod - 2);
    for (int i = MAX_N - 1; i >= 3; i--)
        level_rev[i - 1] = level_rev[i] * i % mod;
    // start to calc!
    for (int i = 0; i <= min(m - 1, n - 2); i++)
        ans = (ans + P(n - 2, i) * comb(m - 1, i) % mod * quick_pow(m, n - 2 - i) % mod * quick_pow(n, n - 3 - i) % mod * (i + 2) % mod) % mod;
    printf("%lld", ans);
    return 0;
}