题目大意：给出 \(x,y,z(0 \leq x,y,z \leq 10^9)\) 以及 \(n\) 个三元组 \((a,b,c)(0 \leq a,b,c < 2^k,,1 \leq k \leq 17)\) ， \(a,b,c,x,y,z\) 都是整数，第i个三元组 \((a_i, b_i, c_i)\) 对应着一个含有 \(x\) 个 \(a_i\) ， \(y\) 个 \(b_i\) ， \(z\) 个 \(c_i\) 的数组。现在要从每个数组中取出一个数，求取出所有数的异或值为 \(0…2^k-1\) 中的每一个数的方案数。 题解：初看题目应该能想到FWHT，但是FWHT显然不能直接做，需要优化。 考虑第 \(i\) 个数组的生成函数 \(F_i\) ，有\[ [x^{a_i}]F_i = x, [x^{b_i}]F_i = y, [x^{c_i}]F_i = z\] 答案即为所有…
Codeforces
[ Codeforces Round #518 ] [ CF 1067D ] Computer Game
题目大意：有\(n\)个副本，副本可以升级，每个副本有三个值\( a_i , b_i , p_i \)，其中\(a_i\)表示该副本在升级前通关的奖励，\(b_i\)表示该副本在升级后通关的奖励，\(p_i\)表示通关该副本的概率。玩家总共可以挑战\(t\)次副本，当玩家挑战某一副本成功后，它可以选择任意一个副本升级（当次不享受升级优惠），求能获得奖励的最大期望。数据范围：\( 1 \leq n \leq 10^5 , 1 \leq t \leq 10^10 , 1 \leq a_i < b_i \leq 10^8 , 0 < p_i < 1\) notice：这篇题解是错的，待修改 题解：如果某一次挑战副本成功了，接下来一定是选择\(b_i \cdot p_i\)最大的那个升级，并一直挑战那个副本。而在此之前，我们肯定只会选择一个最佳的副本一直挑战。如果升级前挑战的副本为i，升级后挑战的副本为j，那么有\[ ans = \sum_{k=1}^{t}{(1-p_i)^{k-1} ( a_i + (n-k)p_j \cdot b_j )} \] 设\( p = p_i , q = 1…