Description
n
≤
4
e
7
,
a
i
≤
1
e
18
n\le4e7,a_i\le1e18
n≤4e7,ai≤1e18
Solution
神仙函数（构造）题。首先这种题目可以归为一类：中间的步骤完全随机，求起始状态到终止状态的期望步数。相应的也有一般的解法，构造一个势能函数，使它的增量是一个定值，终止状态唯一对应函数的一个最值，那么设终止状态
T
T
T，起始状态
S
S
S，状态
s
s
s势能函数
F
(
s
)
F(s)
F(s)，增量
Δ
\Delta
Δ，那么期望步数
E
(
S
)
=
F
(
T
)
−
F
(
S
)
Δ
E(S)=\frac{F(T)-F(S)}{\Delta}
E(S)=ΔF(T)−F(S)。通过构造，这题的函数设为
F
(
S
)
=
∑
(
1
p
a
i
−
1
p
)
,
S
=
[
a
1
,
a
2
,
a
3
.
.
.
]
F(S)=\sum(\frac{1}{p^{a_i}}-\frac{1}{p}),S=[a_1,a_2,a_3...]
F(S)=∑(pai1−p1),S=[a1,a2,a3...]，可以求出转移的
Δ
\Delta
Δ与选择的两个国家无关，为
(
2
p
−
2
)
(\frac{2}{p}-2)
(p2−2)。有点卡常.
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
#define ull unsigned long long
#define mo 1000000007
#define maxm 100005
using namespace std
;
int T
,n
,i
,j
,k
;
ll p
,s
,t
,a
,ans
,ans0
,invp
,sum
,q
[maxm
],l
[maxm
],r
[maxm
];
ull m
,x
,y
,z
,b1
,b2
,b3
;
ll
ksm(ll x
,ll y
){
ll s
=1;
for(;y
;y
/=2,x
=x
*x
%mo
) if (y
&1)
s
=s
*x
%mo
;
return s
;
}
void read(ll
&x
){
x
=0; char ch
=getchar();
for(;ch
<'0'||ch
>'9';ch
=getchar());
for(;ch
>='0'&&ch
<='9';ch
=getchar()) x
=x
*10+ch
-'0';
}
ll f1
[maxm
],f2
[maxm
],B
;
void prepare(){
B
=sqrt(mo
)+1,f1
[0]=1,f2
[0]=1;
for(int i
=1;i
<=B
;i
++) f1
[i
]=f1
[i
-1]*invp
%mo
;
for(int i
=1;i
<=B
;i
++) f2
[i
]=f2
[i
-1]*f1
[B
]%mo
;
}
int main(){
scanf("%d%d%lld%lld",&T
,&n
,&s
,&t
),p
=ksm(t
,mo
-2)*s
%mo
;
invp
=ksm(p
,mo
-2);
prepare();
if (T
==0) for(i
=1;i
<=n
;i
++) {
read(a
);
a
%=mo
-1;
ans
+=f1
[a
%B
]*f2
[a
/B
]%mo
-invp
;
sum
+=a
;
}else {
scanf("%llu%llu%llu%llu%llu%llu",&m
,&x
,&y
,&z
,&b1
,&b2
);
for(i
=1;i
<=m
;i
++) read(q
[i
]),read(l
[i
]),read(r
[i
]);
for(i
=1;i
<=m
;i
++){
ll L
=l
[i
],R
=r
[i
];
for(j
=q
[i
-1]+1;j
<=q
[i
];j
++){
if (j
==1) a
=b1
%(R
-L
+1)+L
; else
if (j
==2) a
=b2
%(R
-L
+1)+L
; else
b3
=b2
*x
+b1
*y
+z
,a
=b3
%(R
-L
+1)+L
,b1
=b2
,b2
=b3
;
a
%=mo
-1;
ans
+=f1
[a
%B
]*f2
[a
/B
]%mo
-invp
;
sum
+=a
;
}
}
}
printf("%lld\n",((ksm(invp
,sum
)-invp
-ans
)%mo
*ksm(2*invp
-2,mo
-2)%mo
+mo
)%mo
);
}
