1012

签到

1005

WD签到

1001

LYF签到推式子（找规律）+套公式

1008

LYF 读入输出有点麻烦其他还好？的dp

1011

题意：给两个数列A,B(n<=2^18)，定义$C_k=max{ A_i B_j },i\ bitand\ j\ge k$求C数列。

解：

首先可以想到如果能求出i&j=k情况下，定义为D数列,做后缀max即可得出C数列。但这也不好做。考虑求i&j$\in$k情况下的数列E。可以发现，E的每一项都大于等于D但小于等于C。感受一下可以得到，对E求后缀max的结果就是C。

那么如何求E呢？$E_k=max { A_i B_j },i\ bitand\ j \in k$

显然，$E_k=max { A_i }\cdot max { B_j }$，类似状压DP转移即可。（还需要注意处理负数的情况）

补1004

题意：给定数列c，n100000。有q100000个询问，问c[l]到c[r]之间有多少个不同的c，使得c xor a<=b

解：

LYF赛场上由于小地方写挂而没有ac，思路是正确的。

首先了解到上一场中1010的莫队做法，若将c xor a<=b改为a<=c<=b是可以在根号时间内做出的（这个询问我称之为老询问）。条件改为c xor a<=b（新询问），是可以转化为多次老询问的。根据xor的特性，我们可以方便地从高位向低位递归c各二进制位的01情况，在每一层中至少有一棵子树是全部满足或全部不满足的。对于全部满足的情况，即可转化为老询问。故每次新询问最多进行log次老询问即可求出答案。总体而言，新询问也经常只需要不到log次老询问。所以复杂度是小于$O(n^\frac{3}{2}\lg n)$的。由于时限2s且评测机很快，可过。

补1002

树剖

补1010

题意：给定奇质数P及小于它的正整数a，求数列$b_x\equiv ax \pmod P,x\le P-1$中的逆序对的奇偶性。

正解：

首先显然可以发现b数列是一个排列。然后就做不下去了…原来是道数学推导题目…
$$
将排列记作\pi，排列逆序数为n(\pi)，定义sgn(\pi)为(-1)^{n(\pi)}，则求逆序数奇偶性可转化为求sgn(\pi)的正负性\\
sgn(\pi)=\frac{\prod _ { i\lt j\le P-1 } c_i-c_j}{\prod _ { i\lt j\le P-1 } i-j}=\prod _ { i\lt j\le P-1 }\frac{c_i-c_j}{i-j}\equiv \prod _ { i\lt j\le P-1 }\frac{ai-aj}{i-j} \equiv \prod _ { i\lt j\le P-1 } a \equiv a^{\frac{P(P-1)}{2}}\equiv a^{\frac{P-1}{2}} \pmod{P}
$$
于是转化成傻逼题

这tm是不是数竞题？

打表：

赛场上把每个p对应的a的奇偶情况打成了01三角矩阵样子的表，完全没有规律

如果尝试每一行输出p a 01 或许是能发现规律的

补1007

线段树维护矩阵