#P17216. [2025年南开中学集训]最长待机

[2025年南开中学集训]最长待机

最长待机(sleep)

题目描述

给定两个集合 S,TS,T 和一个整数 nn,你需要求出有多少个序列 aa 满足以下条件:

  • 0≤∣a∣≤n0\le |a|\le n。
  • 对于所有 1≤i≤∣a∣1\le i\le |a|,ai∈Sa_i\in S。
  • 对于所有 1≤i≤∣a∣−11\le i\le |a|-1,ai≤ai+1a_i\le a_{i+1}。
  • ⨁i=1∣a∣ai∈T\bigoplus_{i=1}^{|a|}a_i\in T。

其中 ⊕\oplus 表示二进制下按位异或。

TestTest 组询问,每次 S,TS,T 不变,即给定 nn 求出答案对 109+710^9+7 取模后的结果,强制在线。

输入格式

第一行两个整数 ∣S∣,∣T∣|S|,|T|,表示 S,TS,T 的大小。

第二行 ∣S∣|S| 个整数表示 SS。

第三行 ∣T∣|T| 个整数表示 TT。

第四行一个整数 TestTest 表示数据组数。

接下来 TestTest 行,每行三个整数 n′,a,bn',a,b,每次你的 nn 等于 (n′⊕(ans+b)) mod a(n'\oplus(ans+b))\bmod a,其中 ansans 是上一次询问输出的答案,初始为 00,⊕\oplus 表示二进制下按位异或。

输出格式

输出 TestTest 行,每行一个整数表示答案。

样例 1 输入

3 1
1 2 3
0
1
2 100 1

样例 1 输出

5

样例 1 解释

aa 共有 55 种选择:[][],[1,1][1,1],[2,2][2,2],[3,3][3,3],[1,2,3][1,2,3]。

数据范围

对于 100%100\% 的数据,满足 1≤Test≤1051\le Test\le 10^5,0≤Si,Ti<2280\le S_i,T_i<2^{28},1≤∣S∣,∣T∣≤271\le |S|,|T|\le 2^7,1≤n′,a,b≤1081\le n',a,b\le 10^8。不保证 S,TS,T 中元素互不相同。

测试点编号 ∣S∣≤\lvert S\rvert\le ∣T∣≤\lvert T\rvert\le Si,Ti<S_i,T_i< Test≤Test\le a≤a\le 特殊性质
1~4 2020 272^7 2282^{28} 10510^5 10810^8 无
5~6 272^7 2202^{20} 1010
7~10 10510^5 1010
11~18 100100
19 11 2282^{28} 10810^8
20~23 272^7 1010 A
24~27 10510^5
28~29 1010 B
30~33 无
34~40 100100
41~44 262^6 10810^8
45~50 272^7
  • 特殊性质 A:保证 SS 中的元素线性无关,即不存在两个 SS 的不同非空子集 T1,T2T_1,T_2 满足 T1T_1 中所有元素的异或和等于 T2T_2 中所有元素的异或和。
  • 特殊性质 B:保证 TT 中的元素大小不超过 33。