这道题目就看官方解答吧
本来这道题目是构造题,但是题目要求计数,计数肯定就很多了,所以我们不能像传统构造题一样,去想如何特殊地构造出一个序列来,这里就要去想满足条件的序列有什么共性,所以我们就假设已经找到了序列\(c\),然后去想想Koxia怎么必胜
于是不难发现引理一(这个可以感性理解一下,如果给了Mahiru两种选择,就有可能破坏产生排列的性质)
但是引理二就不知道怎么发现的了,讲一下这个的理解:
由于这是ICG游戏,所以取逆否命题就好了,我们由于"impossible",所以Mahiru怎么取都不可能取出一个排序(否则的话就"possible"了)
然后这个图论转化记住吧,感觉挺新的
讲一下证明:一条无向边转化为有向边之后,认为终点就是这个组合里面被选择的i.e.,设这条有向边为\((a_i,b_i)\),那么就有\(c_i=b_i\)
然后从充分必要两个方向不难证明(注意\(n\)个点\(n\)条边就是基环树了,后面所说的也不难理解)
其实在构造这个图的时候就会发现是\(n\)个点\(n\)条边,所以脑子里面就要马上反应出这是基环树
标签:题目,构造,基环树,Game,序列,Koxia From: https://www.cnblogs.com/dingxingdi/p/18300452