$\text{Description}$
给定 $T,P,Q$ 和大小为 $n$ 的集合 $A$ 与大小为 $m$ 的集合 $B$，求：
$T\le 10^{18},P,Q,n,m\le 10^6$
$\text{Solution}$
不妨设 $P<Q$。
记 $L=\operatorname{lcm}(P,Q)$，则两个余数有最小正周期 $L$。
对于本题，可以将 $T$ 缩到 $L$ 级别，即我们可以分解为 $[0,L-1]$ 和 $[0,T\bmod{L}]$ 两个子问题。
我们需要一个线性解，可以考虑枚举 $A$ 中的数，然后求出其可以对应的 $B$ 中的数的个数。
观察 $[0,L-1]$ 中的整数可以对应的 $B$ 的个数，首先可以考虑将 $[0,L-1]$ 按其对 $P$ 取模的值分成 $P$ 个递增的序列，然后考虑第 $i$ 个序列的第 $j$ 个数，其对应的原值是 $jP+i$，则其对应的对 $Q$ 取模的值为 $(i+Pj)\bmod{Q}$，容易发现这个东西是循环的，我们将这样的一个循环节称作轨道（自己 yy 的）。
那么每个序列都会属于一个轨道，特别地，若 $P,Q$ 互质，则只存在一个轨道。
注意到无论是 $[0,L-1]$ 还是 $[0,T\bmod{L}]$，我们要求的都是轨道内的一个区间内属于 $B$ 的数的个数，对于一个数 $x$，其权值设为 $[x\in B]$，则我们只需预处理一个轨道的权值和与其权值前缀和，就可以迅速求出环上任意区间的权值和了。
由于所有轨道的数的个数和为 $Q$，故时间复杂度为 $O(P+Q)$。
细节较多，建议参考以下代码。
$\text{Code}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<bits/stdc++.h>
#define REG register
using namespace std;
typedef long long ll;
const int N=1000005;
inline void read(int& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
inline void read(ll& x){
static char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
int n,m;
ll P,Q,T,L;
int A[N],tmp,IB[N],IA[N],Rk[N];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
vector<ll> PWS[N];
ll Ask(int p,int l,int r){return l<=r?PWS[p][r]-PWS[p][l-1]:PWS[p][r]+PWS[p][PWS[p].size()-1]-PWS[p][l-1];}
inline void Init(){
read(P),read(Q),read(n),read(m),read(T);L=lcm(P,Q);
if(P>Q){
swap(n,m),swap(P,Q);
for(REG int i=1;i<=m;++i) read(tmp),IB[tmp]=1;
for(REG int i=1;i<=n;++i) read(A[i]);
}
else{
for(REG int i=1;i<=n;++i) read(A[i]);
for(REG int i=1;i<=m;++i) read(tmp),IB[tmp]=1;
}
for(REG int i=0;i<P;++i){
if(Rk[i]) continue;
PWS[i].push_back(0);
int Now=i;
while(!Rk[Now]) PWS[i].push_back(PWS[i][PWS[i].size()-1]+IB[Now]),IA[Now]=i,Rk[Now]=PWS[i].size()-1,Now=(Now+P)%Q;
}
}
inline void Work(){
Init();
ll Per=T/L,Sur=T%L-1;
ll Ans1=0,Ans2=0;
for(REG int i=1;i<=n;++i) Ans1+=PWS[IA[A[i]]][PWS[IA[A[i]]].size()-1];
for(REG int i=1;i<=n;++i) Ans2+=A[i]<=Sur?Ask(IA[A[i]],Rk[A[i]%Q],Rk[(A[i]%Q+(Sur-A[i])/P*P%Q)%Q]):0ll;
printf("%lld\n",Per*Ans1+Ans2);
}
int main(){Work();}
|
