CF1770D

D. Koxia and Game

By xiaruize

思路

考虑在什么情况下Koxia可以必胜，发现以下几条特征：

• 对于每一次操作，Mahiru都有且只有一个数字可选，即Mahiru选什么完全确定
• 得出这样的结论
  • $a_i=b_i$ 时 , $c_i$ 为任意数都满足条件 , 此时最终选择结果一定为 $a_i$
  • $a_i\neq b_i$ 时， $c_i=a_i$ 或者 $c_i=b_i$ , 此时最终选择结果一定为 $c_i$

得出以上结论后，考虑将原来的数组转化为图，具体操作为在 $a_i$ 与 $b_i$ 之间建边

此时, 这个图不一定联通，考虑对于一个联通块，有如下这些结论:

• 当且仅当联通块是一个基环树(包括自环)时，这个联通块才能转化为可行的 $c_i$
• 如果任意联通块不是基环树，则答案为0
• 按照环分两类: 自环/环
  • 对于自环，答案 $\times n$
  • 对于正常的环, 答案 $\times 2$

具体可以使用并查集维护三个量：点数，边数，是否是自环

统计答案

数据举例

3
1 2 2
1 3 3

对于样例一，建图如下

显然, 点1是自环 2-3形成环

所以答案为 $3 \times 2 =6$

Code