Translation Notice
This article was machine-translated using DeepSeek-R1.

Original Version: Authored in Chinese by myself

Accuracy Advisory: Potential discrepancies may exist between translations

Precedence: The Chinese text shall prevail in case of ambiguity

Feedback: Technical suggestions regarding translation quality are welcomed

D - Swap Hats

Problem Statement

There are 3 Takahashis wearing hats colored $S_1$, $S_2$, and $S_3$ respectively.
We want to perform exactly $10^{18}$ swap operations to make $S_i = T_i$.
Each operation is defined as:

Select a pair $(i,j)$ and swap $S_i$ and $S_j$.

Determine if the goal can be achieved.

Input Format

$S_1~S_2~S_3$
$T_1~T_2~T_3$

Output Format

Print Yes if possible; otherwise, print No.

Sample

Sample Input

1
2


R G B
R G B

Sample Output

1

Yes

Analysis

We manually enumerate all cases. The solution outputs Yes when all $S_i=T_i$ or all $S_i\ne T_i$ (requiring even parity after $10^{18}$ swaps), otherwise No.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


#include <cstdio>
using namespace std;

int main()
{
    char a, b, c, d, e, f;
    scanf("%c %c %c %c %c %c", &a, &b, &c, &d, &e, &f);
    puts(((a == d) + (b == e) + (c == f)) == 1? "No": "Yes");
    return 0;
}

E - King Bombee

Problem Statement

Given a simple undirected graph with $N$ vertices and $M$ edges. The $i$-th edge connects vertices $U_i$ and $V_i$.
Count the number of paths from $S$ to $T$ with length $K$ that pass through vertex $X$ an even number of times, modulo $998244353$.

Constraints:
$2\le N\le 2000$
$1\le M\le 2000$
$1\le K\le 2000$
$1\le S,T,X\le N$
$X\ne S,X\ne T$
$1\le U_i < V_i\le N$
All edges are distinct.

Input Format

$N~M~K~S~T~X$
$U_1~V_1$
$\vdots$
$U_M~V_M$

Output Format

Print the count modulo $998244353$.

Sample

Sample Input 1

1
2
3
4
5


4 4 4 1 3 2
1 2
2 3
3 4
1 4

Sample Output 1

1

4

Valid paths:

$1\to2\to1\to2\to3$
$1\to2\to3\to2\to3$
$1\to4\to1\to4\to3$
$1\to4\to3\to4\to3$

Each path visits $X=2$ even times.

Sample Input 2

1
2
3
4
5
6


6 5 10 1 2 3
2 3
2 4
4 6
3 6
1 5

Sample Output 2

1

0

Disconnected graph.

Sample Input 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


10 15 20 4 4 6
2 6
2 7
5 7
4 5
2 4
3 7
1 7
1 4
2 9
5 10
1 3
7 8
7 9
1 6
1 2

Sample Output 3

1

952504739

Result modulo $998244353$.

Analysis

Define $\mathrm{dp}(i,j,k)$ as the number of paths reaching vertex $j$ in $i$ steps with $k$ being the parity (even/odd) of visits to $X$. Transitions occur via adjacency list:

When moving to vertex $v$, if $v=X$, toggle the parity bit.
Use rolling array optimization for space efficiency.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


#include <cstdio>
#include <vector>
#define maxn 2005
#define MOD 998244353
using namespace std;

inline void mod(int& x)
{
    if(x >= MOD) x -= MOD;
}

vector<int> G[maxn];
int dp[2][maxn][2];

int main()
{
    int n, m, k, s, t, x;
    scanf("%d%d%d%d%d%d", &n, &m, &k, &s, &t, &x);
    x --;
    while(m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[--u].push_back(--v);
        G[v].push_back(u);
    }
    dp[0][--s][0] = 1;
    for(int i=1; i<=k; i++)
    {
        bool c = i & 1, p = i & 1 ^ 1;
        for(int v=0; v<n; v++)
        {
            dp[c][v][0] = dp[c][v][1] = 0;
            for(int u: G[v])
                mod(dp[c][v][0] += dp[p][u][u == x]),
                mod(dp[c][v][1] += dp[p][u][u != x]);
        }
    }
    printf("%d\n", dp[k & 1][--t][0]);
    return 0;
}

F - Shortest Good Path

Analysis

Let $\mathrm{dis}[S][j]$ be the shortest length of a good path with respect to bitmask $S$ ending at vertex $j$. Perform BFS where each state $(S, v)$ represents the current bitmask and position. Use bitmask compression for efficiency.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


#include <cstdio>
#include <queue>
#define INF 2147483647
#define maxn 17
using namespace std;

using ULL = unsigned long long;

int dis[1 << maxn][maxn];
vector<int> G[maxn];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while(m--)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[--u].push_back(--v);
        G[v].push_back(u);
    }
    queue<ULL> q;
    for(int i=0; i<n; i++)
        dis[1 << i][i] = 1, q.push(1ULL<<i+32^i);
    while(!q.empty())
    {
        ULL pkg = q.front(); q.pop();
        int st = pkg >> 32ULL, v = pkg & 0x7fffffff;
        int nd = dis[st][v] + 1;
        for(int u: G[v])
        {
            int nst = st ^ (1 << u);
            if(dis[nst][u] == 0)
            {
                dis[nst][u] = nd;
                q.push(ULL(nst) << 32ULL ^ u);
            }
        }
    }
    long long ans = 0LL;
    for(int i=1, lim=1<<n; i<lim; i++)
    {
        int cur = INF;
        for(int j=0; j<n; j++)
            if(dis[i][j] > 0 && dis[i][j] < cur)
                cur = dis[i][j];
        ans += cur;
    }
    printf("%lld\n", ans);
    return 0;
}