各位春节快乐！
注： 原出题人未知。如有版权问题请私信我，我会撤下这篇文章。
神仙题，第一步就较难想出。
首先，对于任意状态 S = { a 1 , a 2 , ⋯ , a n } S = \{a_1, a_2, \cdots, a_n\} S={a1,a2,⋯,an}，定义函数 F ( S ) = ∑ i = 1 n ( 1 p a i − 1 p ) F(S) = \sum_{i = 1}^{n} (\frac{1}{p^{a_i}} - \frac{1}{p}) F(S)=∑i=1n(pai1−p1)。
定理. 终止态 T = { ∑ i = 1 n a i } T = \{ \sum_{i=1}^{n} a_i\} T={∑i=1nai} 对应函数值最大的状态。
证明. 考虑合并 a i , a j a_i, a_j ai,aj 时的贡献： κ = ( 1 p a i + a j − 1 p ) − ( 1 p a j − 1 p ) − ( 1 p a i − 1 p ) \kappa = (\frac{1}{p^{a_i + a_j}} - \frac{1}{p}) - (\frac{1}{p^{a_j}} - \frac{1}{p}) - (\frac{1}{p^{a_i}} - \frac{1}{p}) κ=(pai+aj1−p1)−(paj1−p1)−(pai1−p1)。易知 κ > 0 \kappa > 0 κ>0。证毕。
考虑计算一次战争后， F ( S ) F(S) F(S) 的期望变化值 E Δ F E_{\Delta F} EΔF。令某轮战争的参战者为 a 1 , a 2 a_1, a_2 a1,a2，令 s ( x ) = ( 1 p x − 1 p ) s(x) = (\frac{1}{p^{x}} - \frac{1}{p}) s(x)=(px1−p1)，有：
E Δ F = p × [ s ( a 1 + 1 ) − s ( a 1 ) − s ( a 2 ) ] + p × [ s ( a 2 + 1 ) − s ( a 2 ) − s ( a 1 ) ] + ( 1 − 2 p ) × [ − s ( a 1 ) − s ( a 2 ) ] = p ( 1 p a 1 + 1 − 1 p ) + p ( 1 p a 2 + 1 − 1 p ) − ( 1 p a 1 − 1 p ) − ( 1 p a 2 − 1 p ) = 2 p − 2 \begin{aligned} E_{\Delta F} & = p \times [s(a_1+1) - s(a_1) - s(a_2)] + p \times [s(a_2+1) - s(a_2) - s(a_1)] + (1 - 2p) \times [- s(a_1) - s(a_2)] \\ & = p(\frac{1}{p^{a_1+1}} - \frac{1}{p}) + p(\frac{1}{p^{a_2+1}} - \frac{1}{p}) - (\frac{1}{p^{a_1}} - \frac{1}{p}) - (\frac{1}{p^{a_2}} - \frac{1}{p}) \\ & = \frac{2}{p} - 2\end{aligned} EΔF=p×[s(a1+1)−s(a1)−s(a2)]+p×[s(a2+1)−s(a2)−s(a1)]+(1−2p)×[−s(a1)−s(a2)]=p(pa1+11−p1)+p(pa2+11−p1)−(pa11−p1)−(pa21−p1)=p2−2
注意到 E Δ F E_{\Delta F} EΔF 与 a 1 , a 2 a_1, a_2 a1,a2 无关！记状态 S S S 的所有后继状态集合为 U U U，明显有：
F ( S ) + E Δ F = ∑ u ∈ U F ( u ) ∣ U ∣ = average S → u F ( u ) F(S) + E_{\Delta F} = \dfrac{\sum_{u \in U} F(u)}{|U|} = \operatorname{average}_{S \rightarrow u} F(u) F(S)+EΔF=∣U∣∑u∈UF(u)=averageS→uF(u)
设状态 S S S 到达终态 T T T 的期望步数为 E ( S ) E(S) E(S)，有：
E ( S ) = { 0 ( S = T ) 1 + average S → U E ( U ) ( S ≠ T ) E(S) = \begin{cases} 0 \quad (S=T) \\ 1 + \operatorname{average}_{S \rightarrow U} E(U) \quad (S \neq T) \end{cases} E(S)={0(S=T)1+averageS→UE(U)(S=T)
由定义，对于任意状态 S S S，应有 E ( S ) × E Δ F = F ( T ) − F ( S ) E(S) \times E_{\Delta F} = F(T) - F(S) E(S)×EΔF=F(T)−F(S)。
验证其合法性：
(1) S = T S=T S=T 时，显然成立。
(2) S ≠ T S \neq T S=T 时，有：
E ( S ) = 1 + average S → U E ( U ) = 1 + average S → U F ( T ) − F ( U ) E Δ F = 1 + F ( T ) E Δ F − 1 E Δ F average S → U F ( U ) = 1 + F ( T ) E Δ F − 1 E Δ F ( F ( S ) + E Δ F ) = F ( T ) − F ( S ) E Δ F \begin{aligned}E(S) & = 1 + \operatorname{average}_{S \rightarrow U} E(U) \\ &= 1 + \operatorname{average}_{S \rightarrow U} \dfrac{F(T)-F(U)}{E_{\Delta F}} \\ &= 1 + \dfrac{F(T)}{E_{\Delta F}} - \dfrac{1}{E_{\Delta F}}\operatorname{average}_{S \rightarrow U} F(U) \\ &= 1 + \dfrac{F(T)}{E_{\Delta F}} - \dfrac{1}{E_{\Delta F}}(F(S) + E_{\Delta F}) \\ &= \dfrac{F(T) - F(S)}{E_{\Delta F}} \end{aligned} E(S)=1+averageS→UE(U)=1+averageS→UEΔFF(T)−F(U)=1+EΔFF(T)−EΔF1averageS→UF(U)=1+EΔFF(T)−EΔF1(F(S)+EΔF)=EΔFF(T)−F(S)
合法性验证完毕。
故 E ( S ) = F ( T ) − F ( S ) E Δ F E(S) = \dfrac{F(T) - F(S)}{E_{\Delta F}} E(S)=EΔFF(T)−F(S)。使用「光速幂」（基于值域处理的快速幂）计算即可。
时间复杂度 O ( n ) \mathcal{O}(n) O(n)。
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define LD long double
#define _rep(i, x, y) for(int i = x; i <= y; i++)
#define _per(i, x, y) for(int i = x; i >= y; i--)
template <typename T>
inline void read(T &x) {
x = 0; T f = (T) 1; char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -f;
for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template <typename T>
inline void write(T x) {
if(x < 0) x = -x, putchar('-');
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T>
inline void writesp(T x, char sp = '\n') {
write(x); putchar(sp);
}
const int maxM = 1e5 + 10, P = 1e9 + 7, BASE = (1 << 15) + 1;
int T, n, s, t, m;
ULL x, y, z, b_1, b_2;
int sma[BASE], lar[BASE];
int pow_mod(int a, int b, int p = P) {
int sum = 1;
while(b) {
if(b & 1) sum = 1ll * sum * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return sum;
}
#define Power(x) 1ll * lar[x >> 15] * sma[x & 32767] % P
int main() {
freopen("warfare.in", "r", stdin);
freopen("warfare.out", "w", stdout);
read(T); read(n); read(s); read(t);
int PInv = 1ll * t * pow_mod(s, P - 2) % P;
int DeltaE = (2ll * PInv % P - 2 + P) % P;
int DEInv = pow_mod(DeltaE, P - 2);
sma[0] = lar[0] = 1; int BLK = (1 << 15);
_rep(i, 1, BLK) sma[i] = 1ll * sma[i - 1] * PInv % P;
_rep(i, 1, BLK) lar[i] = 1ll * lar[i - 1] * sma[BLK] % P;
if(!T) {
LL w, sum = 0, ans = 0, k;
_rep(i, 1, n) {
read(w); sum = (sum + w) % (P - 1); w %= P - 1;
ans = (ans - Power(w) + P) % P;
}
ans = (ans + Power(sum)) % P;
ans = (ans + 1ll * (n - 1) * PInv % P) % P;
ans = ans * DEInv % P;
writesp(ans, '\n');
} else {
read(m); read(x); read(y); read(z); read(b_1); read(b_2);
int q = 1, newq;
LL l, r;
LL w, sum = 0, ans = 0, k;
_rep(i, 1, m) {
read(newq); read(l); read(r); LL a;
_rep(Pos, q, newq) {
if(Pos == 1) a = b_1 % (r - l + 1) + l;
else if(Pos == 2) a = b_2 % (r - l + 1) + l;
else {
LL t = b_1; b_1 = b_2;
b_2 = (x * b_1 + y * t + z);
a = b_2 % (r - l + 1) + l;
}
sum = (sum + a) % (P - 1); a %= (P - 1);
ans = (ans - Power(a) + P) % P;
}
q = newq + 1;
}
ans = (ans + Power(sum)) % P;
ans = (ans + 1ll * (n - 1) * PInv % P) % P;
ans = ans * DEInv % P;
writesp(ans, '\n');
}
return 0;
}