D - Swap Hats
题目大意
有\(3\)个Takahashi，他们帽子的颜色分别为\(S_1,S_2,S_3\)。
我们现在想通过正好\(10^{18}\)次操作，使得\(S_i=T_i\)。
每次操作如下：
- 选择\((i,j)\)，交换\(S_i\)和\(S_j\)。
试问能否达成目标？
输入格式
\(S_1~S_2~S_3\)
\(T_1~T_2~T_3\)
输出格式
如果能达成目标，输出Yes；否则，输出No。
样例
样例输入
R G B
R G B
样例输出
Yes
分析
本题情况不多，可以手动枚举所有可能的情况，最终发现所有\(S_i=T_i\)或者所有\(S_i\ne T_i\)时输出Yes，否则输出No。
代码
#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
题目大意
给定由\(N\)个点、\(M\)条边组成的简单无向图。第\(i\)条边连接顶点\(U_i\)和\(V_i\)。
求图中从\(S\)到\(T\)、长度为\(K\)且经过顶点\(X\)偶数次的路径的数量，对\(998244353\)取模。
\(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\)
\((U_i,V_i)\ne(U_j,V_j)\)（\(i\ne j\)）
输入格式
\(N~M~K~S~T~X\)
\(U_1~V_1\)
\(\vdots\)
\(U_N~V_N\)
输出格式
输出图中从\(S\)到\(T\)、长度为\(K\)且经过顶点\(X\)偶数次的路径的数量，对\(998244353\)取模。
样例
样例输入1
4 4 4 1 3 2
1 2
2 3
3 4
1 4
样例输出1
4
有\(4\)条符合条件的路径：
- \(1\to2\to1\to2\to3\)
- \(1\to2\to3\to2\to3\)
- \(1\to4\to1\to4\to3\)
- \(1\to4\to3\to4\to3\)
注意\(X=2\)必须出现偶数次。
样例输入2
6 5 10 1 2 3
2 3
2 4
4 6
3 6
1 5
样例输出2
0
这张图没有连通。
样例输入3
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
样例输出3
952504739
注意对\(998244353\)取模。
分析
我们先不考虑\(X\)的限制条件，则可以令\(\mathrm{dp}(i,j)=~\)第\(i\)步走到\(j\)的可能数，则因为点\(j\)可以从\(G_j\)中的任意一点走过来（\(G\)为邻接表存储），所以我们得到
\[\mathrm{dp}(i,j)=\sum_{k=1}^{|G_j|} \mathrm{dp}(i-1,{G_j}_k) \]再考虑\(X\)必须是偶数的情况，令\(\mathrm{dp}(i,j,k)=~\)第\(i\)步走到\(j\)且\(X\)的出现次数除以\(2\)的余数为\(k\)的情况，则每次额外判断\({G_j}_k\)是否等于\(X\)即可。
\(\mathrm{DP}\)状态转移方程详见代码。
代码
注意：代码中运用了滚动表的优化，可以节省空间，当然也可以使用普通写法。
#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
分析
令\(\mathrm{dis}[S][j]=~\)于点\(j\)结束的good path with respest to S的最短长度，跑一遍\(\text{BFS}\)即可。具体实现时可将\(S\)按位压缩为二进制，加快运算速度。
代码
#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;
}