题目大意:有n个m元组\(v_1, v_2, \cdots, v_n\),第i个m元组\(v_i = a_{i,1}, a_{i,2}, \cdots , a_{i,m}\)。定义\(count(x)\)为这n个m元组中,对所有\(j = 1 \cdots m\)满足\(a_{i,j} \oplus x\)的二进制表示中有奇数个1的m元组的个数。求\(count(x), x = 0 \cdots 2^k – 1\),其中\(1 \leq n \leq 10^5\),\(0 \leq a_{i,j} < 2^k\),\(1 \leq k \leq 20\),\(1 \leq m \leq 10\)。 题解:观察FWHT中的Haramard矩阵,\(H_{ij}=(-1)^{count1(i\ and\ j)}\),其中\(count1(x)\)表示x的二进制表示中1的数量;这和我们题目中要的东西很像。关于这道题目,我们可以发现我们并不需要做什么卷积;也就是说,我们其实并没有在做一个完整的FWHT。做这道题主要用到的是FWHT中的那个Haramard变换矩阵,然后我们有方法在和这个矩阵做矩阵乘法的时候把时间复杂度降到\(O(n\log (n))\),所以做这道题只需要知道\(H_{ij}=(-1)^{count1(i\ and\ j)}\),然后贴个FWHT的板子使做该矩阵乘法的时间复杂度降到\(O(n\log (n))\)就好了(完全不知道WHT是啥的也可以先看一下http://www.zarxdy34.top/?p=203来帮我增加一下访问量)。 为了方便起见,设\(f(x)=(-1)^{count1(x)}\),即x二进制表示下有奇数个1时为-1,偶数个1时为1,\(H_{ij}=f(i \oplus j)\)。由于有如下性质: \[ \begin{aligned} H_{t(x \oplus y)} &=(-1)^{count1(t\…
[ Codeforces Global Round 2 ] [ CF 1119H ] Triple
题目大意:给出 \(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 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…
[ North American Invitational Programming Contest 2018 ] Missing Gnomes
[ North American Invitational Programming Contest 2018 ] Zoning Houses
[ North American Invitational Programming Contest 2018 ] Flashing Fluorescents
题目大意:有n盏灯\( ( 1 \leq n \leq 16 ) \),编号为1到n,每一秒可以按下某一盏灯的开关。如果在某时刻\(t\)按下第\(i\)盏灯的开关,第t+k时刻第i+k盏灯的状态就会被改变。现给出n盏灯的初始状态,求至少要多久灯才会全部变亮。 题解:考虑每个操作对灯状态的影响,用01来表示灯的灭和亮两个状态,可以发现每个操作相当于对灯的某一区间取反。另外答案一定小于等于n。 枚举答案,然后对状态进行一次长度为ans的操作(这里进行的操作实际上是从刚开始就进行的,并不是枚举第ans时刻在哪个位置按下开关),状压DP即可。
North American Invitational Programming Contest 2018
A. Cut It Out! B. Double Clique C. Flashing Fluorescentsv D. Missing Gnomes E. Prefix Free Code F. Probe Droids G. Rainbow Graph H. Recovery I. Red Black Tree J. Winter Festival K. Zoning Houses
[ HDU6319 ] Ascending Rating
题意有点麻烦就懒得说了……简单来说,用单调队列维护出数字被删去的顺序就好了。