# Codeforces 868G – El Toll Caves(Codeforces 868G – El Toll Caves)-其他

## Codeforces 868G – El Toll Caves(Codeforces 868G – El Toll Caves)

Codeforces 题面传送门 & 洛谷题面传送门

solve(N, K, A, B, f1, f2)

const int MOD = 1e9 + 7;
const int INV2 = MOD + 1 >> 1;
int qpow(int x, int e) {
int ret = 1;
for (; e; e >>= 1, x = 1ll * x * x % MOD)
if (e & 1) ret = 1ll * ret * x % MOD;
return ret;
}
struct line {
int k, b;
line() {k = b = 0;}
line(int _k, int _b): k(_k), b(_b) {}
int at(int x) {return (1ll * x * k + b) % MOD;}
line operator + (const line &rhs) {return line((k + rhs.k) % MOD, (b + rhs.b) % MOD);}
line operator - (const line &rhs) {return line((k - rhs.k + MOD) % MOD, (b - rhs.b + MOD) % MOD);}
void print() {printf("y = %dx + %d\n", k, b);}
};
line merge(line F, line G) {//G(F(x))
return line(1ll * F.k * G.k % MOD, (1ll * G.k * F.b + G.b) % MOD);
}
line getinv(line F) {
int iv = qpow(F.k, MOD - 2);
return line(iv, (MOD - 1ll * iv * F.b % MOD) % MOD);
}
line qpow_l(line x, int e) {
line res = line(1, 0);
for (; e; e >>= 1, x = merge(x, x)) if (e & 1) res = merge(res, x);
return res;
}
line getsum(line x, int e) {
if (!e) return line(0, 0);
if (x.k == 1) return line(e, 1ll * e * (e + 1) / 2 % MOD * x.b % MOD);
line pw = qpow_l(x, e + 1) - x;
line res; res.k = 1ll * pw.k * qpow(x.k - 1, MOD - 2) % MOD;
res.b = 1ll * x.b * (res.k - e + MOD) % MOD * qpow(x.k - 1, MOD - 2) % MOD;
return res;
}
int solve(int n, int k, line A, line B, line F1, line F2) {
if (!k) {
int E1 = 1ll * A.b * qpow((1 - A.k + MOD) % MOD, MOD - 2) % MOD;
return F2.at(E1);
}
line f1 = F1 + merge(getsum(A, n / k), F2);
line f2 = F1 + merge(getsum(A, n / k - 1), F2);
line a = merge(getinv(B), qpow_l(getinv(A), n / k - 1));
line b = merge(getinv(B), qpow_l(getinv(A), n / k));
return (solve(k, n % k, a, b, line(f1.k, 0), line(f2.k, 0)) + 1ll * (n % k) * f1.b + 1ll * (k - n % k) * f2.b) % MOD;
}
int main() {
freopen("silicon20.in", "r", stdin);
freopen("silicon20.out", "w", stdout);
int qu; scanf("%d", &qu);
while (qu--) {
int n, k; scanf("%d%d", &n, &k); int d = __gcd(n, k); n /= d; k /= d;
printf("%d\n", 1ll * solve(n, k, line(1, 1), line(INV2, 1), line(1, 0), line(1, 0)) * qpow(n, MOD - 2) % MOD);
}
return 0;
}

————————

Codeforces problem plane portal & amp; Luogu problem plane portal

Immortal question.

First of all, we will select the surveyed caves in the order of \ (1 \ SIM K \), \ (K + 1 \ SIM 2K \), \ (2k + 1 \ SIM 3K \). Obviously, if there is a difference in the number of surveyed caves \ (\ Ge 2 \) at a certain time, it must be bad. Just understand this sensibility.

Then let’s assume that \ (e_i \) is the expected number of days the treasure at \ (I \) is surveyed. Since we survey in the order of \ (1 \ SIM K, K + 1 \ SIM 2K, 2K + 1 \ SIM 3K \), there are \ (E {I + K} = e {I} + 1 (I + K \ Le n) \) and \ (E {I + K-N} = e {I} · \ dfrac {1} 2} + 1 (I + K & gt; n) \), the final answer is \ (\ dfrac 1} {n · \ sum \ limits {I = 1} ^ ne _i \). The complexity of \ (\ mathcal o (n) \) can be achieved by using manual Gaussian elimination, but it is still not enough to solve this problem.

We consider playing some small cases of \ (n, K \) first to find rules, such as \ (n = 11, k = 4 \), then we classify \ (\ bmod 4 \) into the same group, including \ (e_4 + 1 = e_8 \), \ (e_1 + 2 = e_5 + 1 = e_9 \), \ (e_2 + 2 = e_6 + 1 = e_ {10} \), \ (e_3 + 2 = e_7 + 1 = e_ {11} \), and we express \ (ANS \) as a linear combination of \ (e_1 \ SIM e_4 \), You can get the \ (ansans = \ dfrac{1}{{{{11} · (3e_1 + 3 + 3eu 2 + 3 + 3 + 3eu 3 + 3 + 2e_4 + 1) \) from which we can get the \ (which is the answer that can be obtained by getting the \ (ansans = \ dfrac {1} {} {{11} {{11}} {{{11} · (3eu 1 + U 1 + 1 + 3 + 3 + 3 + 3 + 3eu 3 + 3 + 3 + 3 + e_3 + 3 + 3 + 2 + 2E U 4 + 1 + 1 + 1) \), so we can get the answer by just getting the answer by getting the only by getting the \ (3 \ sum \ sum \ sum \ limits {{{{{I = 1 {I = 1} ^ 3 {^ 3e_i + 2eu I RAC {1} {2} (e_1 + 2) + 1 \), In this way, we establish the identity \ (e_1 = \ dfrac {1} {2} e_4 + \ dfrac {3} {2}, e_2 = \ dfrac {1} {2} e_1 + 2, e_3 = \ dfrac {1} {2} e_2 + 2 \). The problem is transformed into the case of \ (n = 4, k = 3 \).

Inspired by this problem, we consider solving the problem recursively, indicating that the current problem scale \ (n = n, k = k \), \ (a, B, F1, F2 \) is two primary functions, indicating \ (E {I + K} = a (E _i) (I + K \ Le n) \), \ (E {I + K-N} = B (E _i) \), \ (ANS = \ sum \ limits {I = 1} ^ KF1 (E _i) + \ sum \ limits_ {i=k+1}^nf2(E_i)\)。 It can be solved recursively. See the code for the specific implementation.

solve(N, K, A, B, f1, f2)

Time complexity \ (t \ log ^ 2n \), one log is the complexity of Euclidean, and one log is the fast power of composite inverse.

const int MOD = 1e9 + 7;
const int INV2 = MOD + 1 >> 1;
int qpow(int x, int e) {
int ret = 1;
for (; e; e >>= 1, x = 1ll * x * x % MOD)
if (e & 1) ret = 1ll * ret * x % MOD;
return ret;
}
struct line {
int k, b;
line() {k = b = 0;}
line(int _k, int _b): k(_k), b(_b) {}
int at(int x) {return (1ll * x * k + b) % MOD;}
line operator + (const line &rhs) {return line((k + rhs.k) % MOD, (b + rhs.b) % MOD);}
line operator - (const line &rhs) {return line((k - rhs.k + MOD) % MOD, (b - rhs.b + MOD) % MOD);}
void print() {printf("y = %dx + %d\n", k, b);}
};
line merge(line F, line G) {//G(F(x))
return line(1ll * F.k * G.k % MOD, (1ll * G.k * F.b + G.b) % MOD);
}
line getinv(line F) {
int iv = qpow(F.k, MOD - 2);
return line(iv, (MOD - 1ll * iv * F.b % MOD) % MOD);
}
line qpow_l(line x, int e) {
line res = line(1, 0);
for (; e; e >>= 1, x = merge(x, x)) if (e & 1) res = merge(res, x);
return res;
}
line getsum(line x, int e) {
if (!e) return line(0, 0);
if (x.k == 1) return line(e, 1ll * e * (e + 1) / 2 % MOD * x.b % MOD);
line pw = qpow_l(x, e + 1) - x;
line res; res.k = 1ll * pw.k * qpow(x.k - 1, MOD - 2) % MOD;
res.b = 1ll * x.b * (res.k - e + MOD) % MOD * qpow(x.k - 1, MOD - 2) % MOD;
return res;
}
int solve(int n, int k, line A, line B, line F1, line F2) {
if (!k) {
int E1 = 1ll * A.b * qpow((1 - A.k + MOD) % MOD, MOD - 2) % MOD;
return F2.at(E1);
}
line f1 = F1 + merge(getsum(A, n / k), F2);
line f2 = F1 + merge(getsum(A, n / k - 1), F2);
line a = merge(getinv(B), qpow_l(getinv(A), n / k - 1));
line b = merge(getinv(B), qpow_l(getinv(A), n / k));
return (solve(k, n % k, a, b, line(f1.k, 0), line(f2.k, 0)) + 1ll * (n % k) * f1.b + 1ll * (k - n % k) * f2.b) % MOD;
}
int main() {
freopen("silicon20.in", "r", stdin);
freopen("silicon20.out", "w", stdout);
int qu; scanf("%d", &qu);
while (qu--) {
int n, k; scanf("%d%d", &n, &k); int d = __gcd(n, k); n /= d; k /= d;
printf("%d\n", 1ll * solve(n, k, line(1, 1), line(INV2, 1), line(1, 0), line(1, 0)) * qpow(n, MOD - 2) % MOD);
}
return 0;
}