#P12766. mod 2

    ID: 11952 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500可持久化线段树组合数学数论排序构造2025“钉耙编程”中国大学生算法设计暑期联赛(1)

mod 2

mod 2

Problem Description

对于一个数组 bb,定义: odd(b)odd(b):先筛选出 bb 中出现次数为奇数的元素,再将这些元素按照“出现次数降序,出现次数相同时按元素大小升序排序”的新数组。 even(b)even(b):先筛选出 bb 中出现次数为偶数的元素,再将这些元素按照“出现次数降序,出现次数相同时按元素大小升序排序”的新数组。 比如 b=b=[1, 2, 1],那么 odd(b)odd(b) =   [2];b=b=[3, 3, 2, 2, 1, 2, 1, 2, 4],那么 even(b)even(b) = [2, 1, 3]; 现在给你一个长度为 nn 的数组 aa,有 qq 次询问,每次询问给你四个数 L,R,k,VL, R, k, V。你需要回答:你能构造出多少种长度为 kk,值域为 [1,V][1, V]的数组 bb,使得 odd(a[L,R])=even(b)odd(a[L, R]) = even(b) ?答案对 22 取模。强制在线。

Input

第一行输入一个整数 TT (1≤T≤1051 \le T \le 10^5),表示测试的总数。 对于每个测试样例, 第一行输入一个数 nn,表示数组的长度。接下来一行 nn(1≤n≤1051 \leq n \leq 10^5)个数 a1,a2,⋯ ,ana_1, a_2, \cdots, a_n(1≤ai≤1091 \leq a_i \leq 10^9)。保证样例中 nn 的总和不超过 3×1053 \times 10^5。 接下来一个数 qq (1≤q≤1051 \leq q \leq 10^5),表示询问的次数。保证样例中 qq 的总和不超过 10510^5。 接下来 qq 行,每行四个整数 L,R,k,VL, R, k, V(1≤L≤R≤n1 \leq L \leq R \leq n, 1≤k,V≤10181 \leq k, V \leq 10^{18}),含义如题面所示。强制在线。在第 jj 次询问时,令 preansj=∑i=1j−1ansipreans_j = \sum_{i = 1}^{j - 1}ans_i。你读入的 L′,R′,k′,V′L', R', k', V' 需要异或上 preansjpreans_j 才是真正的 L,R,k,VL, R, k, V。

Output

对于每个样例,每次询问输出一个值,方案数对 22 取模后的结果。

Sample Input

1
5
1 2 3 2 5
2
1 4 4 5
1 3 14 7

Sample Output

0
1

Hint

对于第一个查询,我们得到的 odd(a[1,4])odd(a[1, 4]) = [1, 3]。可能的 bb 为:

  • [1, 1, 3, 3]
  • [1, 3, 1, 3]
  • [1, 3, 3, 1]
  • [3, 1, 1, 3]
  • [3, 1, 3, 1]
  • [3, 3, 1, 1] 一共有 66 种情况。因此输出 00。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛(1)