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