A – Range Flip Find Route
思博题。考虑最后的路径肯定是多个黑白子路径的拼接，那么路径的代价就是进入黑色子路径的次数，那么我们只需要建图的时候给白色入黑色的边赋 \(1\) 的权即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 110, dx[2] = {0, 1}, dy[2] = {1, 0};
typedef pair<int, int> pii;
int n, m, idx[MAX_N][MAX_N], head[MAX_N * MAX_N], current, dist[MAX_N * MAX_N], start_pos;
char str[MAX_N][MAX_N];
bool vis[MAX_N * MAX_N];
struct edge
{
int to, nxt, weight;
} edges[MAX_N * MAX_N << 3];
void addpath(int src, int dst, int weight)
{
edges[current].to = dst, edges[current].nxt = head[src];
edges[current].weight = weight, head[src] = current++;
}
void shortestPath()
{
memset(dist, 0x3f, sizeof(dist));
priority_queue<pii> pq;
pq.push(make_pair(0, start_pos)), dist[start_pos] = 0;
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if (vis[u])
continue;
vis[u] = true;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (dist[edges[i].to] > dist[u] + edges[i].weight)
dist[edges[i].to] = dist[u] + edges[i].weight, pq.push(make_pair(-dist[edges[i].to], edges[i].to));
}
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", str[i] + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
idx[i][j] = m * (i - 1) + j;
start_pos = n * m + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int d = 0; d < 2; d++)
{
int dstx = i + dx[d], dsty = j + dy[d];
if (str[dstx][dsty] != 0)
if (str[i][j] == '.')
if (str[dstx][dsty] != str[i][j])
addpath(idx[i][j], idx[dstx][dsty], 1);
else
addpath(idx[i][j], idx[dstx][dsty], 0);
else
addpath(idx[i][j], idx[dstx][dsty], 0);
}
addpath(start_pos, idx[1][1], str[1][1] == '#');
shortestPath(), printf("%d\n", dist[idx[n][m]]);
return 0;
}
B – 123 Triangle
算贡献 + 找规律的题。
首先我们可以把输入的 \(1, 2, 3\) 转换成 \(0, 1, 2\)（做差结果不会变）。然后我们先来考虑判断答案的奇偶性，这个子问题的本质其实是若干个 \(0, 1\) 进行异或。这个三角形其实就是 Pascal 三角形，所以贡献就是 \({n – 1 \choose i}\)。所以，可以考虑用 Lucas 算这个组合数的奇偶性，然后放答案里。
如果最后判断出来是奇数，那么显然就是 \(1\)；如果不是奇数，有性质：如果 \(1\) 出现在原序列中，则答案是 \(0\)，否则为 \(2\)。如果原序列中只有 \(0, 2\)，那么这个题完全可以看成 \(0, 1\) 的子问题，然后给答案乘回来一个 \(2\)。
// B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, ai[MAX_N], fac[MAX_N];
char str[MAX_N];
int binomial(int n_, int k_) { return fac[n_] - fac[k_] - fac[n_ - k_]; }
int main()
{
scanf("%d%s", &n, str + 1);
bool flag = false;
for (int i = 1; i <= n; i++)
ai[i] = str[i] - '1', flag |= (ai[i] == 1);
for (int i = 1; i <= n; i++)
{
int acc = i;
while (!(acc & 1))
fac[i]++, acc >>= 1;
fac[i] += fac[i - 1];
}
if (!flag)
for (int i = 1; i <= n; i++)
ai[i] >>= 1;
int ans = 0;
for (int i = 1; i <= n; i++)
if ((ai[i] & 1) && (!binomial(n - 1, i - 1)))
ans ^= 1;
if (!flag)
ans <<= 1;
printf("%d\n", ans);
return 0;
}
C – Giant Graph
这个题是真你妈的屌。
首先肯定知道一点，因为这个指数设置的贼大，所以我们要用位运算贪心的思想，让 \(i + j + k\) 从大到小进行确定，这个图就可以连成一个 DAG 了。我们现在需要找一个独立集出来。
然后这个题开始变骚了，这是个博弈图，最优解的状态点本身就是最大独立集。我们可以考虑算出来这些 SG 函数值，然后算图里的 \(SG(x) \oplus SG(y) \oplus SG(z) = 0\) 的价值。发现 \(SG(x) \leq \sqrt{m}\)，可以考虑直接暴力去算。
// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200, mod = 998244353;
typedef long long ll;
int n, m[3], base, vis[MAX_N], sg[MAX_N];
vector<int> G[MAX_N], sum[3];
int fpow(int bas, int tim)
{
int ret = 1;
while (tim)
{
if (tim & 1)
ret = 1LL * ret * bas % mod;
bas = 1LL * bas * bas % mod;
tim >>= 1;
}
return ret;
}
int main()
{
scanf("%d", &n), base = fpow(ll(1e18) % mod, mod - 2);
for (int rd = 0; rd < 3; rd++)
{
scanf("%d", &m[rd]);
for (int i = 1; i <= n; i++)
G[i].clear();
for (int i = 1, u, v; i <= m[rd]; i++)
{
scanf("%d%d", &u, &v);
if (u > v)
swap(u, v);
G[u].push_back(v);
}
memset(sg, 0, sizeof(sg)), memset(vis, -1, sizeof(vis));
int cbase = fpow(10, 18 * n);
for (int i = n; i >= 1; i--)
{
for (int v : G[i])
vis[sg[v]] = i;
while (vis[sg[i]] == i)
sg[i]++;
while (sum[rd].size() <= sg[i])
sum[rd].push_back(0);
sum[rd][sg[i]] = (0LL + sum[rd][sg[i]] + cbase) % mod, cbase = 1LL * cbase * base % mod;
}
}
int ans = 0;
for (int i = 0, siz1 = sum[0].size(); i < siz1; i++)
for (int j = 0, siz2 = sum[1].size(); j < siz2; j++)
{
int k = i ^ j;
if (k < sum[2].size())
ans = (0LL + ans + 1LL * sum[0][i] * sum[1][j] % mod * sum[2][k] % mod) % mod;
}
printf("%d\n", ans);
return 0;
}
D – Merge Triplets
考虑生成后的序列的性质。原序列 \(A_i = (X_1, X_2, X_3)\)，如果满足 \(X_i > X_{i + 1}\)，那么这两个元素在 \(P\) 序列中铁定连续；当然，如果满足 \(X_1 > X_2, X_1 > X_3 \)，那么也是铁定连续的。那么一个这样的 \(X_i\) 可以作为块起点，把三元组进行细分。那么这些小块其实就是目标序列的一个个子串。
所以如果一个目标排列 \(P\) 要能被计数，当且仅当存在一种分块方式，使得若干个块拼成若干个单元，且每个单元的元素个数为 \(3\)。
如果分块方式确定了，是不是元素就被固定了？显然是这样的。首先块内的大小已经被确定，且每次放置一个块，则这个块的第一个数肯定大于之前的所有块的第一个数。又因为第一个数是块的最大数，那么至少块间的大小关系已经被确认；且，块内的数字也是递减的，所以块内的关系也确定了。这个肯定是个唯一的排列。
所以只需要算分块方案即可。怎样的分块方案合法？要么分 \(3, 2, 1\) 块，但是注意长度为 \(2\) 块数量一定要少于长度为 \(1\) 的块数，这样有完美匹配。设置 \(dp[i][j]\)，\(i\) 为最后位置，\(j\) 为长度为 \(1\) 的块的块数减去长度为 \(2\) 的块的块数，设置方式有点像 CSP-S 2019 D2T1。最后取 \(\geq 0\) 的即可。
// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2020, base = MAX_N;
int n, mod, dp[MAX_N * 3][MAX_N * 4];
int main()
{
scanf("%d%d", &n, &mod), dp[0][base] = 1;
for (int i = 0; i < 3 * n; i++)
for (int j = -n; j <= 3 * n; j++)
{
dp[i + 1][j + 1 + base] = (0LL + dp[i + 1][j + 1 + base] + dp[i][j + base]) % mod;
dp[i + 2][j - 1 + base] = (0LL + dp[i + 2][j - 1 + base] + 1LL * dp[i][j + base] * (i + 1) % mod) % mod;
dp[i + 3][j + base] = (0LL + dp[i + 3][j + base] + 1LL * dp[i][j + base] * (i + 2) % mod * (i + 1) % mod) % mod;
}
int ans = 0;
for (int i = 0; i <= 3 * n; i++)
ans = (0LL + ans + dp[3 * n][i + base]) % mod;
printf("%d\n", ans);
return 0;
}