Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
An active fish's eaten positions are always one contiguous interval. If it started at and currently owns , its size is .
Mirror the array if needed so Alice starts left of Bob. Before the two chosen fish become adjacent, Alice can only expand inside and Bob can only expand inside .
Before adjacency, the two fishes' random choices are independent. Build one interval DP for Alice and one for Bob: is the probability that this fish has eaten exactly interval using only its own turns.
Turn counts matter. If Bob's interval has length and he is stuck on his turn before contact, Alice has already made one more move than Bob, so Alice's interval length must be and still be separated from Bob.
Do not seed phase two from every adjacent pair of independent intervals. Some of those histories became adjacent earlier and then ate outward. Seed only the first-contact transition: Alice eating the last gap fish to the right, or Bob eating the last gap fish to the left.
Mirror the line if necessary so . This changes left and right, but not the probability Alice wins.
The first invariant is simple and it carries the whole problem: an active fish always owns one contiguous interval. It starts at one position and every successful move eats a current neighbor, so no holes can appear. If the fish originally started at and currently owns , then its current size is
because the original fish was not eaten by itself. Prefix sums of give this in .
Split the game into two phases.
Before Alice's and Bob's fish become adjacent, they do not affect each other. Alice's fish can only eat inside , and Bob's fish can only eat inside . For each fish separately, build an interval DP:
From , check the neutral neighbor on the left and the neutral neighbor on the right, inside that fish's allowed range. If exactly one is edible, move there with probability . If both are edible, each transition gets probability . If neither is edible, this fish would die on its next own turn, so this state has no outgoing transition.
Now handle the one way Alice can win before the fishes meet: Bob is stuck on Bob's turn while Alice is still alive and not adjacent to him. Suppose Bob's interval length is . Bob has made successful moves. Since Alice starts, at Bob's next turn Alice has made successful moves, so Alice's interval length must be . We need Alice's right endpoint to be at most , where is Bob's left endpoint. For each length, keep prefix sums over Alice interval starts, so each such sum is .
The annoying part is entering the adjacent phase. A tempting shortcut is to multiply every adjacent Alice interval by every adjacent Bob interval. That is wrong. Some of those paths became adjacent earlier and then ate outward, so counting them as new contact would replay history. Classic DP footgun.
Instead, seed only first contact. Let be the total number of successful moves already made after the move that creates adjacency. Then
If is odd, Alice just moved. For first contact, her last move must have eaten the final neutral fish between them, so she came from and moved right. Multiply , the probability of choosing that right move from that previous state, and .
If is even and , Bob just moved. For first contact, Bob came from and moved left. Multiply , , and the probability of choosing that left move. If , the fishes are adjacent from the start, so seed directly.
Once they are adjacent, use one joint DP:
Here is the total number of successful moves made, and is Alice's left endpoint. The formulas above determine and , so every boundary is known:
If is even, it is Alice's turn. Her possible successful moves are eating Bob if , and eating the neutral fish at if it exists and is small enough. She chooses uniformly among the available successful moves. Eating Bob adds to the answer; eating outside moves to . If she has no move, she loses.
If is odd, it is Bob's turn. Bob may eat Alice if , or eat the neutral fish at if possible. If Bob has no move, Alice wins and we add the whole state probability. If Bob eats Alice, Alice loses. If Bob eats outside, move to .
Correctness follows from the interval invariant and the phase split. Before contact, the two random processes are independent, so multiplying their interval probabilities is valid. The direct pre-contact win is counted exactly at Bob's first stuck turn, with the only possible matching Alice length. First-contact seeding is exact because the move that removes the last gap fish is unique by turn parity. After contact, the fishes stay adjacent until the game ends, and plus determines the complete state, so the joint DP has all needed information.
There are interval states and adjacent states. Every transition is , so the total complexity is per test case, with memory. Since , this fits comfortably.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MOD = 1000000007;
const int INV2 = 500000004;
int addMod(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int main() {
setIO();
int tc;
cin >> tc;
while (tc--) {
int n, x, y;
cin >> n;
cin >> x >> y;
vector<ll> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
if (x > y) {
vector<ll> na(n + 1), nb(n + 1);
for (int i = 1; i <= n; i++) {
na[i] = a[n + 1 - i];
nb[i] = b[n + 1 - i];
}
a.swap(na);
b.swap(nb);
x = n + 1 - x;
y = n + 1 - y;
}
vector<ll> pref(n + 1);
for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + b[i];
auto sizeOf = [&](int start, int l, int r) -> ll {
return a[start] + pref[r] - pref[l - 1] - b[start];
};
auto moveProb = [&](int start, int L, int R, int l, int r, int side) -> int {
ll cur = sizeOf(start, l, r);
bool left = l > L && cur >= a[l - 1];
bool right = r < R && cur >= a[r + 1];
int cnt = int(left) + int(right);
if (side == -1 && !left) return 0;
if (side == 1 && !right) return 0;
return cnt == 2 ? INV2 : 1;
};
auto buildDP = [&](int start, int L, int R) {
vector<vector<int>> dp(n + 2, vector<int>(n + 2));
dp[start][start] = 1;
for (int len = 1; len <= R - L + 1; len++) {
for (int l = L; l + len - 1 <= R; l++) {
int r = l + len - 1;
if (!(l <= start && start <= r)) continue;
int val = dp[l][r];
if (val == 0) continue;
ll cur = sizeOf(start, l, r);
bool left = l > L && cur >= a[l - 1];
bool right = r < R && cur >= a[r + 1];
int cnt = int(left) + int(right);
if (cnt == 0) continue;
int add = cnt == 2 ? int(1LL * val * INV2 % MOD) : val;
if (left) dp[l - 1][r] = addMod(dp[l - 1][r], add);
if (right) dp[l][r + 1] = addMod(dp[l][r + 1], add);
}
}
return dp;
};
auto dpA = buildDP(x, 1, y - 1);
auto dpB = buildDP(y, x + 1, n);
int ans = 0;
for (int lenB = 1; lenB <= n; lenB++) {
int lenA = lenB + 1;
if (lenA > n) break;
vector<int> prefStart(n + 2);
for (int l = 1; l <= n; l++) {
prefStart[l] = prefStart[l - 1];
int r = l + lenA - 1;
if (r <= n) prefStart[l] = addMod(prefStart[l], dpA[l][r]);
}
int lo = max(x + 1, y - lenB + 1);
int hi = min(y, n - lenB + 1);
for (int lb = lo; lb <= hi; lb++) {
int rb = lb + lenB - 1;
int waysB = dpB[lb][rb];
if (waysB == 0) continue;
ll cur = sizeOf(y, lb, rb);
bool left = lb > x + 1 && cur >= a[lb - 1];
bool right = rb < n && cur >= a[rb + 1];
if (left || right) continue;
int lastStart = lb - lenA - 1;
if (lastStart >= 1) {
ans = (ans + 1LL * waysB * prefStart[lastStart]) % MOD;
}
}
}
vector<vector<int>> phase(n + 2, vector<int>(n + 2));
if (y == x + 1) phase[0][x] = 1;
for (int c = 1; c <= n - 2; c++) {
int lenA = (c + 1) / 2 + 1;
int lenB = c / 2 + 1;
for (int la = 1; la + lenA + lenB - 1 <= n; la++) {
int ra = la + lenA - 1;
int lb = ra + 1;
int rb = lb + lenB - 1;
if (!(la <= x && x <= ra && lb <= y && y <= rb)) continue;
int add = 0;
if (c & 1) {
int before = int(1LL * dpA[la][ra - 1] * dpB[lb][rb] % MOD);
if (before != 0) {
add = int(1LL * before * moveProb(x, 1, y - 1, la, ra - 1, 1) % MOD);
}
} else {
int before = int(1LL * dpA[la][ra] * dpB[lb + 1][rb] % MOD);
if (before != 0) {
add = int(1LL * before * moveProb(y, x + 1, n, lb + 1, rb, -1) % MOD);
}
}
phase[c][la] = addMod(phase[c][la], add);
}
}
for (int c = 0; c <= n - 2; c++) {
int lenA = (c + 1) / 2 + 1;
int lenB = c / 2 + 1;
for (int la = 1; la + lenA + lenB - 1 <= n; la++) {
int val = phase[c][la];
if (val == 0) continue;
int ra = la + lenA - 1;
int lb = ra + 1;
int rb = lb + lenB - 1;
ll sizeA = sizeOf(x, la, ra);
ll sizeB = sizeOf(y, lb, rb);
if (c % 2 == 0) {
bool outside = la > 1 && sizeA >= a[la - 1];
bool kill = sizeA >= sizeB;
int cnt = int(outside) + int(kill);
if (cnt == 0) continue;
int add = cnt == 2 ? int(1LL * val * INV2 % MOD) : val;
if (kill) ans = addMod(ans, add);
if (outside) phase[c + 1][la - 1] = addMod(phase[c + 1][la - 1], add);
} else {
bool outside = rb < n && sizeB >= a[rb + 1];
bool kill = sizeB >= sizeA;
int cnt = int(outside) + int(kill);
if (cnt == 0) {
ans = addMod(ans, val);
continue;
}
int add = cnt == 2 ? int(1LL * val * INV2 % MOD) : val;
if (outside) phase[c + 1][la] = addMod(phase[c + 1][la], add);
}
}
}
cout << ans << '\n';
}
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
const int MOD = 1000000007;
const int INV2 = 500000004;
int addMod(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int main() {
setIO();
int tc;
cin >> tc;
while (tc--) {
int n, x, y;
cin >> n;
cin >> x >> y;
vector<ll> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
if (x > y) {
vector<ll> na(n + 1), nb(n + 1);
for (int i = 1; i <= n; i++) {
na[i] = a[n + 1 - i];
nb[i] = b[n + 1 - i];
}
a.swap(na);
b.swap(nb);
x = n + 1 - x;
y = n + 1 - y;
}
vector<ll> pref(n + 1);
for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + b[i];
auto sizeOf = [&](int start, int l, int r) -> ll {
return a[start] + pref[r] - pref[l - 1] - b[start];
};
auto moveProb = [&](int start, int L, int R, int l, int r, int side) -> int {
ll cur = sizeOf(start, l, r);
bool left = l > L && cur >= a[l - 1];
bool right = r < R && cur >= a[r + 1];
int cnt = int(left) + int(right);
if (side == -1 && !left) return 0;
if (side == 1 && !right) return 0;
return cnt == 2 ? INV2 : 1;
};
auto buildDP = [&](int start, int L, int R) {
vector<vector<int>> dp(n + 2, vector<int>(n + 2));
dp[start][start] = 1;
for (int len = 1; len <= R - L + 1; len++) {
for (int l = L; l + len - 1 <= R; l++) {
int r = l + len - 1;
if (!(l <= start && start <= r)) continue;
int val = dp[l][r];
if (val == 0) continue;
ll cur = sizeOf(start, l, r);
bool left = l > L && cur >= a[l - 1];
bool right = r < R && cur >= a[r + 1];
int cnt = int(left) + int(right);
if (cnt == 0) continue;
int add = cnt == 2 ? int(1LL * val * INV2 % MOD) : val;
if (left) dp[l - 1][r] = addMod(dp[l - 1][r], add);
if (right) dp[l][r + 1] = addMod(dp[l][r + 1], add);
}
}
return dp;
};
auto dpA = buildDP(x, 1, y - 1);
auto dpB = buildDP(y, x + 1, n);
int ans = 0;
for (int lenB = 1; lenB <= n; lenB++) {
int lenA = lenB + 1;
if (lenA > n) break;
vector<int> prefStart(n + 2);
for (int l = 1; l <= n; l++) {
prefStart[l] = prefStart[l - 1];
int r = l + lenA - 1;
if (r <= n) prefStart[l] = addMod(prefStart[l], dpA[l][r]);
}
int lo = max(x + 1, y - lenB + 1);
int hi = min(y, n - lenB + 1);
for (int lb = lo; lb <= hi; lb++) {
int rb = lb + lenB - 1;
int waysB = dpB[lb][rb];
if (waysB == 0) continue;
ll cur = sizeOf(y, lb, rb);
bool left = lb > x + 1 && cur >= a[lb - 1];
bool right = rb < n && cur >= a[rb + 1];
if (left || right) continue;
int lastStart = lb - lenA - 1;
if (lastStart >= 1) {
ans = (ans + 1LL * waysB * prefStart[lastStart]) % MOD;
}
}
}
vector<vector<int>> phase(n + 2, vector<int>(n + 2));
if (y == x + 1) phase[0][x] = 1;
for (int c = 1; c <= n - 2; c++) {
int lenA = (c + 1) / 2 + 1;
int lenB = c / 2 + 1;
for (int la = 1; la + lenA + lenB - 1 <= n; la++) {
int ra = la + lenA - 1;
int lb = ra + 1;
int rb = lb + lenB - 1;
if (!(la <= x && x <= ra && lb <= y && y <= rb)) continue;
int add = 0;
if (c & 1) {
int before = int(1LL * dpA[la][ra - 1] * dpB[lb][rb] % MOD);
if (before != 0) {
add = int(1LL * before * moveProb(x, 1, y - 1, la, ra - 1, 1) % MOD);
}
} else {
int before = int(1LL * dpA[la][ra] * dpB[lb + 1][rb] % MOD);
if (before != 0) {
add = int(1LL * before * moveProb(y, x + 1, n, lb + 1, rb, -1) % MOD);
}
}
phase[c][la] = addMod(phase[c][la], add);
}
}
for (int c = 0; c <= n - 2; c++) {
int lenA = (c + 1) / 2 + 1;
int lenB = c / 2 + 1;
for (int la = 1; la + lenA + lenB - 1 <= n; la++) {
int val = phase[c][la];
if (val == 0) continue;
int ra = la + lenA - 1;
int lb = ra + 1;
int rb = lb + lenB - 1;
ll sizeA = sizeOf(x, la, ra);
ll sizeB = sizeOf(y, lb, rb);
if (c % 2 == 0) {
bool outside = la > 1 && sizeA >= a[la - 1];
bool kill = sizeA >= sizeB;
int cnt = int(outside) + int(kill);
if (cnt == 0) continue;
int add = cnt == 2 ? int(1LL * val * INV2 % MOD) : val;
if (kill) ans = addMod(ans, add);
if (outside) phase[c + 1][la - 1] = addMod(phase[c + 1][la - 1], add);
} else {
bool outside = rb < n && sizeB >= a[rb + 1];
bool kill = sizeB >= sizeA;
int cnt = int(outside) + int(kill);
if (cnt == 0) {
ans = addMod(ans, val);
continue;
}
int add = cnt == 2 ? int(1LL * val * INV2 % MOD) : val;
if (outside) phase[c + 1][la] = addMod(phase[c + 1][la], add);
}
}
}
cout << ans << '\n';
}
}