A
令(dp_i)为({x|x进入后最终能变成0})
初始(dp_{n+1}={0})
- (s_i=0)
(dp_{i}=dp_{i+1}cup dp_{i+1}~xor~a_i) - (s_i=1)
若(a_iin dp_{i+1})，是否操作对答案并不影响，(dp_{i}=dp_{i+1})
若(a_i otin dp_{i+1})，玩家1赢了。因为若过来一个(x)，(dp_{i+1})并不能同时表示出(x)和(xoplus a_i)
B
题目可以描述成最大前缀和-最小前缀和
令(f(M))为最大前缀和为(M)时最小前缀和最大是多少
令(Z)为整个序列的最大前缀和最小是多少，则(ans={M-f(M)|Zle M})
固定(f(M))，有一个显然正确的贪心：先将"?"全变成(-1)，然后再从前到后，对于每个"?"，能变成(+1)就边
我们观察到，当(M)增加(2)时，最多将一个(-1)变成(+1)，(f(M+2)le f(M)+2)
那么(ans=min(Z-f(Z),(Z+1)-f(Z+1)))
C
不失一般性的，可以将题目描述成(Ale B)
考虑判断某序列是否能得到，充要条件为：
- 将序列至少为(A)长度的(0)段染成(1)段后，序列存在至少长度为(B)的(1)段
必要性：若使用过(B)操作，观察最后一次使用(B)操作，之后的(A)操作若破坏了最后一次(B)操作，可以实现还原；若没有使用过(B)操作，则显然
充要性：将序列某个长度为(B)的(1)段固定，其他位置可以任意染色，最后再适当破坏该段
考虑计算不合法方案数，当将(A)段染成(B)后，序列的形状为(0)小于(A)，(1)小于(B)
不重复地，统计序列(0)小于(A)，(1)小于(B)，其中(1)段在保证首尾为(1)的情况下，中间可填(0)
特殊地，开头和结尾的(1)段分别首、尾可以是(0)
D
考虑最优策略：
- 随机选择一个亮起的灯(x)
- 若(p_x=x)，则失败了
- 若(p_x eq x)，若(p_x)暗下去了，则将其点亮；若(p_x)亮了，则操作(p_x)
由于随机性，可以假设每次随机选择的亮起的灯为：([1,A])中最小的
令([1,A])中最小的(p_x=x)的点为(t)。若不存在，令(t=A+1)
那么一个排列合法的充要条件为：
(forall x(A,n])置换环上存在(< t)的数
将序列中(> A)的元素删去，考虑剩下的置换
有一种特殊情况，就是删去前非自环，删去后不为自环
- 令满足环中存在(< t)的位置个数为(i)
- 令(<t)且为自环的个数为(j)
考虑将(> A)的元素插进去，则方案数为
对于置换中不存在(< t)的(A-i)个位置，其应形成若干个从头到尾都亮着的环。所以系数还要乘上((A-i-1)!)
现在具体考虑做法，令(f_{i,j})为([1,A])中满足环中存在(<t)位置的个数为(i)，自环尾(j)：
新建环，选择当前未选择的最小的位置，并加入，然后(i-k-1)个位置与其形成一个环排列