Topcoder-575
少了个特判被 cha 好桑心……
1k 原题什么情况！我勒个去。
Solution
250 pts
结论： \(n\) 为奇数是先手必败。若 \(n = 2^k\) 则 \(k\) 奇先手必败 \(k\) 偶先手必胜，否则先手必胜。
证明的话还是归纳吧。不打表我真就不会做。
果然我被坑能力拔群。轻轻松松被 7k+ 坑 →_→
我提问发自真心。
500 pts
显然，对于一个元素来说，如果它不在一开始的位置，则在其他任何位置的概率是相同的。
于是我们可以递推出 \(k\) 次操作后，每个元素在初始位置的概率。不妨设 \(f_i\) 表示 \(i\) 次操作后的概率，可以得到递推式：
\[f_{i+1} = \frac{n-2}{n} f_i + \frac{2}{n} \frac{1}{n-1} (1-f_i)\]
前一半表示一开始就在这个位置的概率，后一半表示交换回来的概率。
如何计算答案？我们计算每个元素对答案的贡献。枚举每个元素，再枚举最后的位置 \(x\) ，则对答案做出的贡献是在这个位置的概率乘上这个数的值再乘上这个位置被子序列包含的概率。
1000 pts
原题什么的，我就只能说自己做题太少了。没坑好神奇
以下是 xiaodao （蒯）的方法，我觉得非常漂亮。
大家见过的构图大部分是 S -> x -> y -> T 这种图吧。这次的构图是 S -> x -> y -> x -> T 好奇葩。
我们把白点按照列数的奇偶分成两种白点。则黑点每次在两种白点中要各取一个。于是前一个 x 表示的是第一种白点，后一个 x 表示的第二种白点，中间的 y 表示黑点。为了保证一个黑点只会被流一次，我们需要将 y 再拆点，流量上限 1 。
这种建图的关键是每一个 L 形被一条增广路所表示，利用白点列数的奇偶性非常巧妙。写起来非常好写～（有 SAP 模板就是爽）
situation
首先看完 250 ，发现不会做。以前见过一个除法的，特水，分解质因数即可。减法的还真就不知道怎么做。
看了一下样例，感觉没啥思路。而且 \(n\) 的范围是 \(10^{18}\) ，普通分解方式还应付不了，所以不会是质因数分解这方面。决定赶紧写程序打表。表倒是好打，发现奇偶性很有规律的样子，于是把必胜/必败与 \(n\) 的奇偶性无关的提出来，发现一定是 2 的幂。然后就好了。
怒开 500 。看完第一段感觉很开心的样子，想到了 CF 某题，那个题是动态维护每个点最后在某个位置的概率。继续看下去发现有个啥还有个期望子段和，感觉就是这样了。再一想发现没具体给定交换，那么动态维护的矩阵一堆相同的数，不同的数只有 2 个 →_→ ……稍微推了下发现是可行的。怒写代码，430+ 分好爽。
然后开了 1000 pts 的，想了一下觉得没啥好做的，于是就坑了 →_→
Challenge 的时候发现 250 pts 的被 Cha 了，原因是忘记判 1 这个特殊条件了 T_T
幸亏过了 500 pts 否则就爆零了。
最后 #136 ，由于是小号还是可以涨的。只涨了 52 。（下次可以涨红吧？） 不要立 flag ！
others
Petr #1 rejudge #2 meret #3
wuzhengkai #15 。250 居然 FST 真是无语。
ChnLich #18 和我一样第一题被 cha 。
xiaodao #20 rating 和我一样了。上次 Seter 给 xiaodao 跌了蛮多的。
tourist #21 因为 1000 pts FST 了。
7k+ 居然用大号！cha 人 cha 的丧心病狂。#23
scottai #71 过前俩题正常节奏。
liouzhou_101 的 500 pts 只有 200+ 分，所以他俩题加起来没我一题多…… #143
秋锅第一题看错题了光荣爆零。
耀爷一开始说他不想做了，于是硬把他拉过来做……不过考到一半没网了好惨 →_→
nonsense
祝大家 CTSC 好运。
不能太颓废了，得开学习模式了呢。