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

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

神仙题。

首先我们每次肯定会按 \(1\sim k\),\(k+1\sim 2k\),\(2k+1\sim 3k\) 的顺序选择勘测的洞穴,显然如果出现两个洞穴在某一时刻被勘测次数差 \(\ge 2\) 那肯定是不优的,这个感性理解一下即可。

那么我们假设 \(E_i\) 为在 \(i\) 处的宝藏被勘测到的期望天数,那么由于我们按 \(1\sim k,k+1\sim 2k,2k+1\sim 3k\) 的顺序勘测,有 \(E_{i+k}=E_{i}+1(i+k\le n)\),以及 \(E_{i+k-n}=E_{i}·\dfrac{1}{2}+1(i+k>n)\),最终答案就是 \(\dfrac{1}{n}·\sum\limits_{i=1}^nE_i\)。使用手动高斯消元可以做到 \(\mathcal O(n)\) 的复杂度,但还是不足以解决这道题。

我们考虑先手玩一些 \(n,k\) 比较小的情况找找规律,譬如 \(n=11,k=4\),那么我们将 \(\bmod 4\) 相同的归为一组,有 \(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}\),我们将 \(ans\) 表示成 \(E_1\sim E_4\) 的线性组合,可以得到 \(ans=\dfrac{1}{11}·(3E_1+3+3E_2+3+3E_3+3+2E_4+1)\),这样我们只要能求出 \(3\sum\limits_{i=1}^3E_i+2E_4\) 即可算出答案,而类似地我们也可以得到恒等式 \(E_1=\dfrac{1}{2}E_8+1=\dfrac{1}{2}(E_4+1)+1\),\(E_2=\dfrac{1}{2}E_9+1=\dfrac{1}{2}(E_1+2)+1\),这样我们建立了恒等式 \(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\)。问题就转化为 \(n=4,k=3\) 的情况。

受到这个问题的启发,我们考虑递归地解决问题, 表示目前问题规模 \(n=N,k=K\),\(A,B,f1,f2\) 为两个一次函数,表示 \(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)\)。递归求解即可,具体实现见代码。

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

时间复杂度 \(T\log^2n\),1 个 log 是欧几里得的复杂度,1 个 log 是复合逆的快速幂。

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;
}