考场上因为读不懂题(再加上菜)就弃了
所以先给一点翻译
non-degenerate
不-除掉|生成的 不退化的
non-degenerate triangle
不退化三角形,就是存在的三角形,满足三边\(a+b\geq c\)
然后题目就涉及到奇奇怪怪的博弈论知识了
不会
但最简单的证明还是看得懂
大佬说目前我的水平想不出来那就不必想出来吧,自己写一遍证明还是很有收获的
一个必胜态一定能够经过一次操作到达必败态,而一个必败态无论怎样操作都只能到达必胜态。
——来自博弈论知识
结论:先手胜当且仅当(a-1)^(b-1)^(c-1)!=0
证明如下
不妨设\(a\le b\le c\)
第一,一个必败态(即(a-1)^(b-1)^(c-1)==0
)无论怎样操作都只能到达必胜态
- 若\(a=1\),则
(b-1)^(c-1)==0
,易知 \(b=c\),显然必败(已经可以停止证明了,因为先手都无法操作)
先手将\(b\)减少,后手将\(c\)减少到相同值即胜利 - 若\(a\neq 1\),则有\(1<a<b<c\),如果将\(a\)减小为\(x\),则一定有
(x-1)^(b-1)^(c-1)!=0
,为必胜态
对\(b\)与\(c\)操作也是这个结果
第二,一个必胜态一定能够经过一次操作到达必败态
设x=(a-1)^(b-1)^(c-1)
,将 \(a-1\) 变为 (a-1)^x
,则 \(a\) 变为 (a-1)^x+1
,那么此时(a-1)^(b-1)^(c-1)==0
,为必败态(对\(b,c\)同理,当然一次只能操作一个数)
那么就需要知道是否能使(a-1)^x+1<a
找到\(x\)的最高位,这个 \(1\) 在 \(a-1,b-1,c-1\) 的对应位上一定出现了奇数次,选择这个位上为 \(1\) 的数进行操作就可以使得这个数减小,因此是可以使(a-1)^x+1<a
的(\(a\)取\(a,b,c\))
证毕
多打几个括号啊
标签:ch,Triangle,必败,Game,必胜,Sept.25,操作,oplus,mod From: https://www.cnblogs.com/antimony-51/p/16750171.html