Roundgod is obsessive about linear algebra. Let A={0,1}, everyday she will generate a binary vector randomly in An. Now she wonders the probability of generating n linearly independent vectors in the next n days modulo 109+7. Formally, it can be proved that the answer has the form of QP, where P and Q are coprime and Q is not a multiple of 109+7. The answer modulo 109+7 thus means P⋅Q−1(mod109+7), where Q−1 is the multiplicative inverse of 109+7.
Wcy thinks the problem too easy. Let the answer of n be fn, she wants to know f1⊕f2⊕...⊕fn, where ⊕ denotes bitwise exclusive or operation.
Note that when adding up two vectors, the components are modulo 2.
输入描述
The input contains multiple test cases. The first line of input contains one integer T(1⩽T⩽1000), denoting the number of test cases.
In the following T lines, each line contains an integer n(1⩽n⩽2×107) describing one test case.
输出描述
For each test case, output one integer indicating the answer.
示例1
输入
1 2 3 4
3 1 2 3
输出
1 2 3
500000004 194473671 861464136
说明
f(1)=21f(2)=83f(3)=6421
分析
首先说明,向量各个维度的坐标都是在模 2 意义下的,基于此可以有如下性质。对于两个向量 a 和 b,a+b=a−b=b−a,这三者可视为同一向量。对于一个向量 x,∀k∈N,若 k 为偶数,那么 kx=0;若 k 为奇数,那么 kx=x。基于以上,两个向量 a 和 b 的线性组合只有 a,b,a+b,0 这四个向量。 fn 表示随机生成 n 个线性无关的 n 维向量的概率。由于要使 n 个 n 维向量组成的向量组线性无关,因此考虑添加第 i 个 n 维向量 x 时,x 必须不属于前 i−1 个线性无关的向量构成的向量空间。接下来尝试枚举 i 来寻找规律。
当 i=2,已有的线性无关向量组为 a;同 a 组成线性相关向量组的向量有 0,a。当 i=3,已有的线性无关向量组为 a,b,那么同 a,b 构成线性相关向量组的向量有 0,a,b,a+b。当 i=4,已有的线性无关向量组为 a,b,c,那么同 a,b,c 构成线性相关向量组的向量有 0,a,b,c,a+b,a+c,b+c,a+b+c。基于以上,假设已经存在 i−1 个线性无关的向量 α1,α2,⋯,αi−1,如果再添加一个向量 x,使得 α1,α2,⋯,αi−1,x 线性相关,那么 x 的取值有 j=0∑i−1(ji−1)=2i−1 种;该式意味着每次在 i−1 个向量中取 j 个向量 αi1,αi2,⋯,αij,令 x=αi1+αi2+⋯+αij。
第 i 个向量是 n 维向量,必然有 2n 种可能;但是由于已经存在 i−1 个线性无关的向量,因此其中 2i−1 种取值必然会与前 i−1 个向量组成线性相关的向量组,只有 2n−2i−1 种取值是合法的。因此,第 i 个向量与前 i−1 个线性无关的向量组成线性无关组的概率为 2n2n−2i−1。故当 n⩾2 时,n 个 n 维向量组成线性无关组的概率 fn=21i=2∏n2n2n−2i−1=i=1∏n2n2n−2i−1;显然,当 n=1 时符合上式,故 fn=i=1∏n2n2n−2i−1。
可见,fn=2n2(2n−1)(2n−2)⋯(2n−2n−1),而 fn−1=2(n−1)2(2n−1−1)(2n−1−2)⋯(2n−1−2n−2)。因此有 2n−1fn−1=2(n−1)2(2n−2)⋯(2n−2n−1),故 2n−1fn−1fn=22n−12n−1。最终得到 fn=(1−2n1)fn−1,已知 f1=21。预处理 2 的幂的逆元后,即可 O(n) 得到 fn 的值,再处理 fn 的异或前缀和,每次查询 O(1) 输出答案。
Roundgod has an n×m matrix A=(aij). One day while she’s doing her physics homework, she wonders is it possible to define the physical quantity for matrices.
As we all know, the pressure p satisfies a formula p=SF, where F is the compressive force and S is the base area.
To describe it in maths, Roundgod puts forward that the compressive force of a matrix equals the sum of all its entries, while the base area of a matrix equals the sum of the entries in its last row. Then she can calculate the pressure for a matrix with the same formula.
Your goal is to find the submatrix of AA with maximum pressure.
A submatrix is obtained by taking nonempty subsets of its rows and columns. Formally, given a nonempty subsequence S of {1,2,…,n} and a nonempty subsequence T of {1,2,…,m}, then $\begin{pmatrix} a_{S_1, T_1} & a_{S_1, T_2} & \cdots & a_{S_1, T_{|T|}} \\ a_{S_2, T_1} & a_{S_2, T_2} & \cdots & a_{S_2, T_{|T|}} \\\vdots & \vdots & \ddots & \vdots \\ a_{S_{|S|}, T_1} & a_{S_{|S|}, T_2}&\cdots & a_{S_{|S|}, T_{|T|}} \end{pmatrix}$ is a submatrix of A.
输入描述
There are multiple test cases. The first line of input contains an integer T(T⩽100), indicating the number of test cases. For each test case:
The first line contains two integers n,m(1⩽n,m⩽200), the number of rows and columns of the matrix, respectively.
Each of the next n lines contains m integers, specifying the matrix (1⩽aij⩽5×104).
输出描述
For each test case, print the maximum pressure within an absolute or relative error of no more than 10−8 in one line.
示例1
输入
1 2 3 4 5
1 3 3 1 3 5 6 8 9 2 7 4
输出
1
4.50000000
说明
$\begin{pmatrix}1 & 5\\6 & 9 \\2 & 4\end{pmatrix}$ is one of submatrices of $A$ with maximum pressure $\frac{1+5+6+9+2+4}{2+4}=\frac{27}{6}=4.5$.
Roundgod is given n,k, construct a permutation P of 1∼n satisfying that for all integers i in [1,n], there exists a contiguous subarray in P of length i whose sum is k modulo n. If there are multiple solutions, print any of them. If there is no solution, print “-1” in one line.
输入描述
The first line contains two integers n, k(1⩽n⩽5000,0⩽k<n).
输出描述
Print n integers, the answer permutation in one line if such permutation exists, or print “-1” in one line if no solution exists.
示例1
输入
1
2 1
输出
1
1 2
说明
The sum of subintervals [1],[1,2] both satisfy ≡1(mod2), and their lengths are 1,2 respectively.
示例2
输入
1
3 1
输出
1
-1
分析
∀i∈[1,n],P 存在子列满足,子列各个元素的和与 k 模 n 同余;当 i=n 时,子列的和为 i=1∑nPi=i=1∑ni=2n(n+1),故 2n(n+1)≡k(modn)。
当 n 为奇数,若 k=0,则有解;令 P=[n,1,n−1,2,n−2,⋯] 即可。
当 n 为偶数,若 k=2n,则有解;令 P=[n,2n,1,n−1,2,n−2,⋯] 即可。
Roundgod is obsessive about numbers. Let S(x) be the sum of the digits of x in decimal notation, (A,B) is a harmony pair if and only if S(A)>S(B). Roundgod is given N, and she wants to count the number of harmony pairs (A,B) modulo 109+7 satisfying 0⩽A⩽B⩽N.
输入描述
The only line of input contains one integer N(1⩽N⩽10100).
输出描述
Output one integer indicating the answer.
示例1
输入
1
100
输出
1
967
比较套路的数位 DP 问题。 N 的数位长度为 len,同时构造 A,B 的第 1,2,⋯,len 位(数位自左向右,左边的数位小),采用记忆化搜索的形式。limit1 表示对 B 的限制,限制 B⩽N;limit2 表示对 A 的限制,限制 A⩽B。定义 f(p,q,r,s) 表示 A,B 有 p 位,S(A)−S(B)=q,limit1=r 且 limit2=s 时,构造 A,B 的方案数。由于 S(A)−S(B) 有可能为负数,所以需要加上 1000 的偏移量。
A sequence is called k-bag, if and only if it is put in order by some (maybe one) permutations of 1 to k. For example, [1,2,3,2,1,3,3,2,1] is a valid 3-bag sequence.
Roundgod is not satisfied with kk-bag, so she put forward part-kk-bag, which is a contiguous subsequence of k-bag.
Wcy wants to know if the sequence of length n is a part-k-bag sequence.
输入描述
The first line contains one integer T(1⩽T⩽20), denoting the number of test cases. Then TT test cases follow.
The first line of each test case contains two integers n,k(1⩽n⩽5×105,1⩽k⩽109).
The second line of each test case contains n integers indicate the sequence.
It is guaranteed that ∑n⩽2×106, the values of the sequence are between 1 and 109.
输出描述
One line of each test case, if the sequence is a part-k-bag sequence, print “YES”, otherwise print “NO”.
示例1
输入
1 2 3
1 8 3 2 3 2 1 3 3 2 1
输出
1
YES
分析
设给出的序列为 a。
首先,若 ∃ai∈[1,k],那么给出的 a 必然不是 part-k-bag,可以直接输出 “NO”。接下来的讨论皆基于 ∀ai,ai∈[1,k] 的情况。
若 a 各个元素互不相同,那么 a 可能恰好是 1∼k 的全排列,也可能是一个 1∼k 的全排列的一个子序列;根据 k-bag 的定义,此时的 a 必然是个 part-k-bag。
若 ∃ai=aj,那么情况就类似样例 [2,3,2,1,3,3,2,1]。a 的头和尾是 1∼k 的全排列的一部分,而中部是多个 1∼k 的全排列。显然,对于 ai 和 aj,若 ai=aj,那么两者必然不会在同一个排列中。令 d 为满足 i<d 且 ai=ad 的最小整数。那么 a 头部的结尾位置最大为 d−1,否则 a 的头部包含两个相同的数,不满足排列的定义。从 1 到 d−1 枚举 a 的头部结尾,每次检验接下来的序列是否能构成多个 1∼k 的全排列即可,当然,检验时,a 的尾部是很好识别的。为了做到 O(n) 的时间复杂度,可以采用双指针。定义两个指针 l,r,l 表示当前 a 头部结尾的位置。最初 l=1,r 从 2 开始,不停地向后找 k 的全排列,因此可r 理解为当前尚未检验过的序列的开头。维护 cntx 表示 x 在当前考察序列(当前考察序列指 al+1∼ar−1 这部分序列)内出现的次数;a 的中部会有多个全排列,用 ID 表示当前正在检验的全排列的编号,从 1 开始记录。假设已经检验完 ID−1 个全排列,当前正在检验第 ID 个全排列,由于 r 表示还未检验到的序列开头,那么当且仅当 cntar=ID−1 时,前面有 ID−1 个全排列;否则,说明当前的 l 作为头部的结尾不能使 a 成为 part-k-bag,应当继续枚举 l。若 l 一直枚举到 d 还未找到 a 成为 part-k-bag 的方案,那么 a 就不是 part-k-bag。
注意要用 \text{unordered_set} 和 \text{unordered_map},set 和 map 则容易超时。