题目大意：有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\…
多校
[ HDU6319 ] Ascending Rating
题意有点麻烦就懒得说了……简单来说，用单调队列维护出数字被删去的顺序就好了。
[ HDU6318 ] Swaps and Inversions
[ HDU6312 ] Game
[ HDU6309 ] Absolute
题目大意：给定n个区间\([l_i , r_i]\)，\(-10^6 \leq l_i \leq r_i \leq 10^6\)且\(l_i , r_i\)都为整数，\(x_i\)为对应范围内的一个随机实数，求\(| \sum{x_i} | \)的期望。\( n \leq 15\)，答案对998244353取模。 题解：和这道题基本上是一样的，容斥方法一样。 分成\(\sum{x_i}\)小于0和大于0两部分来考虑，两部分的做法一样。以小于0的部分为例，首先将范围进行调整，将\(x_i\)的范围调整为\([0,r_i – l_i]\)，那么符合条件的范围即\( \sum{l_i} + \sum{x_i} < 0\)，即\( 0 \leq |\sum{x_i}| < |\sum{l_i}| \)，求此时\( |\sum{l_i}| – |\sum{x_i}|\)的期望。容斥的方法和上面的那个是一样的，不同之处在于这题求的不是概率，还要考虑\(\sum{x_i}\)的期望。这里可以通过积分求出，当\[0 \leq x_i \leq a\] \[0 \leq \sum{x_i} \leq a\]时，该部分\(a – \sum{x_i}\)的期望为\(\frac{a^n}{xpro \cdot n!}\)，其中\(xpro = \prod{(r_i – l_i)}\)。（不是很严谨，意会一下即可）
[ HDU6308 ] Time Zone
[ HDU6305 ] RMQ Similar Sequence
题意：定义一个数列A的\(RMQ(A,l,r)\)为使得\(a_i\)为\(a_l,a_{l+1},a_{l+2}, \cdots ,a_r\)中最大数的最小的i。 对于两个数列A与B，定义它们RMQ相似当且仅当两数列元素个数相等且对于所有的\(1 \leq l \leq r \leq n\)，有\( RMQ(A,l,r)=RMQ(b,l,r)\)。 现在给你一个正整数数列\(\{a_i\}\)，其中\(1 \leq a_i \leq n\)，对于实数数列\(\{b_i\}\)，其中\(b_i\)为\([0…1]\)中随机的一个实数，当数列A与B RMQ相似时，B的权值为\(\sum{b_i}\)，否则为0,求B权值的期望。（答案对\(10^9 + 7\)取模）（\(1 \leq n \leq 10^6\)） 题解：首先要观察两个序列RMQ相似的条件。当数列A是一个1..n的全排列时，两个序列RMQ相似当且仅当B中元素的大小顺序和A相同。此时答案为\(\frac{n}{2} \cdot \frac{1}{n!}\)（其中\(\frac{n}{2}\)表示的是B中元素之和的期望，\(\frac{1}{n!}\)表示的是B中元素大小顺序满足条件的概率）。 问题主要是在于当A中含有相同元素的时候的答案。由于不同的A的全排列所对应的满足条件的B是互不相交的（元素间大小关系不同），所以我们要求出与A RMQ相似的n排列的个数，答案就是这个乘上上面所说的一个排列所对应的答案。接下来找符合条件的全排列（记为C）的个数。 考虑A的一个区间\([l..r]\)，设\(m=RMQ(A,l,r)\)，那么我构造的\(c_m\)一定是C中该区间中的最大值，\(c_m\)的值可以确定下来。可以发现，当取任意的\(l \leq l_0…
[ HDU6304 ] Chiaki Sequence Revisited
题意：有一个数列定义如下：\(a_1 = a_2 = 1, a_n = a_{n-a_{n-1}} + a_{n-1-a_{n-2}} (n \geq 3) \)，求\(\sum_{i=1}^n{a_i}\)。（\( 1 \leq n \leq 10^{18}\)，多组数据，\(T \leq 10^5\)） 题解：先打个表观察一下。数列从1开始如下：1 1 2 2 3 4 4 4 5 6 6 7 8 8 8 8 9 10 10 11 12 12 12 13 14 14…