CVBB ACM Team

分类：数学，二次剩余。

题意：给定 $N,C,k$ 求 $F_0^k+F_{C}^k+F_{2C}^k+\cdots+F_{NC}^k(mod 10^9+9)$，其中 $F$ 为斐波那契数列。$N,C\le10^{18},k\le10^5$

题解：斐波那契数列通项公式 $F_i=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i)$ ，且 $5$ 是 $10^9+9$的二次剩余，因此我们可以预处理出来 $x=\frac{1}{\sqrt{5}},a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2}$，对于所求的式子可以通过二项式展开来求 $$S=x^k\sum_{i=0}^{k}(-1)^{(k-i)}C(k,i)\sum_{j=0}^{N}a^{jci}b^{jc(k-i)}$$ 对于后面的求和显然可以通过等比数列求和公式计算，因此我们只需枚举 $i=0\sim k$ 即可，注意特判公比为 $1$ 的情况。

comment：利用了斐波那契数列的通项公式以及二次剩余，以及特殊情况的考虑。

分类：概率论、期望

题意：给定一棵有根树，每次随机选一个未被删除的点，将以它为根的子树删除。求删除整棵树所用的期望步数。

题解：显然每个点被删只和自己及其祖先有关，那么一个点被选择的概率就是$1/dep_i$，全部加在一起即可

comment：巧妙的期望计算方法，有学到

分类：博弈论。

题意：两人玩游戏。给定一个由数字和至少一个问号组成的序列，每人轮流将一个问号改为一个数字。如果问号数量为奇数则A先手，否则B先手。最终所有问号的被填完后，如果所得数字是$11$的倍数，则本轮游戏得分为该数字，否则得分为该数字的相反数。A希望数字越大越好，B希望数字越小越好，如果他们会按照最优策略进行操作，求最终游戏结果。

题解：

前置芝士：一个数是$11$的倍数等价于奇数位之和减去偶数位之和是$11$的倍数。

可以发现A永远走最后一步，因此我们不妨考虑一个状态是A必胜还是A必败。设此时有$x$个奇数位的问号和$y$个偶数位的问号，奇数位之和减去偶数位之和模$11$为$z$，那么状态$(x,y,z)$是A必胜态等价于$10(y-x) \equiv z \pmod {11}$，证明如下：考虑如果$(x,y,z)$是A必胜态，那么$(x-1,y,z-10),(x+1,y,z+10),(x,y-1,z+10),(x,y+1,z-10)$都是必败态，而当前者是必败态时后者都是必胜态；我们以前者是必胜态为例分析该结论，每次操作最多只能$\pm 9$，不可能实现$\pm 10$，如果自己的回合无法到达必胜态，那么对手就可以通过操作达到必败态（因为$\pm 20$在模$11$下等价于$\pm 9$，一先一后两次操作后，后手一定可以达到这个值）；而最终A胜利状态为$(0,0,0)$，即可推导出结论中的公式。

输赢确定后，考虑双方会如何进行最优操作。必赢的一方要保证每一步操作后都是对手的必败态的前提下使得最终数字的绝对值更大，而必输的一方只用考虑使得最终数字的绝对值更小。如果必胜一方先手，那它第一步有两种选择，在奇数位填或在偶数位填进入对手的必败态，可以直接将两种情况都算一遍最后取绝对值更大的即可，此时填的数字可以通过上述结论算出来，如果是非$0$数，那么要填在奇数位或偶数位的最高位，否则要填在奇数位或偶数位的最低位，这样做显然是最优的。接下来，进入必败方-必胜方-必败方-必胜方的循环，必败方显然要让更高的位填$0$才能使绝对值更小。通过对上述结论可以得到如果必败方在奇数位填$0$，那么必胜方只能在奇数位填$9$或在偶数位填$0$，如果必败方在奇数位填$9$，那么必胜方只能在奇数位填$0$或在偶数位填$9$，奇偶反转过来也是同样成立的。因此通过亿阵博弈思考，得出以下结论：设奇数位置上有$x$个问号，偶数位置上有$y$个问号，那么如果$xy$奇偶性相同，最终双方的策略都是按顺序填$09090909 \cdots$；否则可以在其中一个填$009090909 \cdots$，另一个还是按顺序填$09090909 \cdots$，哪个先填两个$0$可以由必败方决定，因此讨论对应位置的前后即可得到大小关系，选择更小的那一个即可。

值得一提的是，必败方并不是只会一直填$0$，上述先填两个$0$的方案就是通过必败方从后往前填$9$逼迫必胜方填$0$从而达成的。

comment：博弈论套博弈论，太顶了。

2020.07.21 Codeforces Round #658(Div. 1)

无

晚间强制下机，这周摸了

传送门

2020.07.19 Codeforces Round #657 (Div. 2)

2020.07.21 Codeforces Round #656 (Div. 3) Virtual participation

2020.07.21 Codeforces Round #658 (Div. 1)

2020.07.24 Codeforces Round #604 (Div. 1) Virtual participation

写了一波ODT板子。