Home » 国际竞赛 » Details

USACO 2021 December Contest, Platinum Problem 3. HILO

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午12:33

USACO 2021 December Contest, Platinum Problem 3. HILO

Bessie knows a number $x + 0.5$ where $x$ is some integer between $0$ to $N,$ inclusive ( $1 \leq N \leq 5000$ ).

Elsie is trying to guess this number. She can ask questions of the form "is $i$ high or low?" for some integer $i$ between $1$ and $N,$ inclusive. Bessie responds by saying "HI!" if $i$ is greater than $x + 0.5$ , or "LO!" if $i$ is less than $x + 0.5$ .

Elsie comes up with the following strategy for guessing Bessie's number. Before making any guesses, she creates a list of $N$ numbers, where every number from $1$ to $N$ occurs exactly once (in other words, the list is a permutation of size $N$ .) Then, she goes through the list, guessing numbers that appear in the list in order. However, Elsie skips any unnecessary guesses. That is, if Elsie is about to guess some number $i$ and Elsie previously guessed some $j < i$ such that Bessie responded with "HI!," Elsie will not guess $i$ and will move on to the next number in the list. Similarly, if she is about to guess some number $i$ and she previously guessed some $j > i$ such that Bessie responded with "LO!," Elsie will not guess $i$ and will move on to the next number in the list. It can be proven that using this strategy, Elsie always uniquely determines $x$ regardless of the permutation she creates.

If we concatenate all of Bessie's responses of either "HI" or "LO" into a single string $S,$ the number of times Bessie says "HILO" is the number of length $4$ substrings of $S$ that are equal to "HILO."

Bessie knows that Elsie will use this strategy and has already chosen the value of $x$ , but she does not know what permutation Elsie will use. Your goal is to compute the sum of the number of times Bessie says "HILO" over all permutations that Elsie could possibly choose, modulo $10^{9} + 7$ .

INPUT FORMAT (input arrives from the terminal / stdin):

The only line of input contains $N$ and $x$ .

OUTPUT FORMAT (print output to the terminal / stdout):

The total number of HILOs modulo $10^{9} + 7$ .

SAMPLE INPUT:

4 2

SAMPLE OUTPUT:

In this test case, Bessie's number is $2.5$ .

For example, if Elsie's permutation is $(4, 1, 3, 2)$ , then Bessie will say "HILOHILO," for a total of two "HILO"s. As another example, if Elsie's permutation is $(3, 1, 2, 4)$ , then Bessie will say "HILOLO," for a total of one "HILO."

SAMPLE INPUT:

60 10

SAMPLE OUTPUT:

508859913

Make sure to output the sum modulo $10^{9} + 7$ .

SCORING:

Test cases 3-10 satisfy $N \leq 50$ .
Test cases 11-18 satisfy $N \leq 500$ .
Test cases 19-26 satisfy no additional constraints.

Problem credits: Richard Qi

USACO 2021 December Contest, Platinum Problem 3. HILO 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Richard Qi, Benjamin Qi)

There are two ways to approach this problem. One uses dynamic programming, while the other uses linearity of expectation.

1. DP Solution

Suppose that we have already constructed some prefix of the permutation, and there are $j$ remaining non-redundant values below Bessie's number and $k$ remaining non-redundant values above Bessie's number (we define non-redundant numbers as numbers that Elsie could guess that would give her more information). Also, consider the two cases where Bessie has most recently said either "HI" or "LO". Let $b = 0$ be the case where Bessie has most recently said "LO" and let $b = 1$ be the case where Bessie has most recently said "HI". Then, the expected number of "HILO"s for the original problem is just the case where $j = x, k = N - x, b = 0$ .

Thus, it is sufficient to count the expected number of "HILO"s for each $j \leq x, k \leq N - x,$ and $b = 0$ or $b = 1$ . Call this quantity $d p [b] [j] [k]$ . Now, note that all redundant values do not affect the expected number of "HILOs", so we ignore all of them. Then, there are $j + k$ possible values for the next number in the permutation, each of which occurs with probability $\frac{1}{j + k}$ .

We will first consider the case where $b = 0$ . Suppose that the next value in the permutation is less than $x + 0.5,$ of which there are $j$ possibilities. Denote these values as $v_{0}, v_{1}, v_{2}, \dots v_{j - 1}$ such that $x + 0.5 > v_{0} > v_{1} > v_{2} \dots > v_{j - 1}$ .

Suppose the next value in the permutation is $v_{j_{2}}$ for some $0 \leq j_{2} < j$ . Then, Bessie says "LO" (because $v_{j_{2}} < x + 0.5$ ) and there are $j_{2}$ remaining nonredundant values below Bessie's number. The $k$ initial nonredundant values above Bessie's number are still nonredundant, so the expected number of HILOs in the remaining sequence of values is $d p [0] [j_{2}] [k]$ .

Similarly, if we consider the values greater than $x + 0.5,$ which we label $x + 0.5 < u_{0} < u_{1} < u_{2} \dots < u_{k - 1},$ if we choose one of these values $u_{k_{2}}$ , Bessie says "HI" and there are $k_{2}$ remaining nonredundant values above Bessie's number, so the expected number of HILOs in the remaining sequence of values is $d p [1] [j] [k_{2}]$ .

So, we have the recurrence $d p [0] [j] [k] = \frac{\sum_{j_{2} < j} d p [0] [j_{2}] [k] + \sum_{k_{2} < k} d p [1] [j] [k_{2}]}{j + k}$ .

For computing $d p [1] [j] [k],$ we can apply the same technique. However, since Bessie has just said "HI", if we now choose a value $v_{j_{2}} < x + 0.5,$ Bessie will then say "LO" and the number of "HILO"s increases by one. We choose a value less than $x + 0.5$ with probability $\frac{j}{j + k},$ so the expected number of "HILO"s increases by $\frac{j}{j + k} .$

So, we have the recurrence $d p [1] [j] [k] = \frac{\sum_{j_{2} < j} d p [0] [j_{2}] [k] + \sum_{k_{2} < k} d p [1] [j] [k_{2}]}{j + k} + \frac{j}{j + k} .$

Now, we can compute every value of $d p [b] [j] [k]$ by iterating over all $j_{2} < j, k_{2} < k$ and using the above recurrences. Since there are $N^{2}$ dp states and we sum over $N$ smaller states, this leads to a time complexity of $O (N^{3}),$ which is enough for the first two subtasks.

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class ExpectedHILOCubic {
    public static final long MOD = 1000000007;
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int x = Integer.parseInt(tokenizer.nextToken());
        int y = n - x;
        long[] inverse = new long[n + 1];
        for (int k = 1; k <= n; k++) {
            inverse[k] = inverse(k);
        }
        long[][][] dp = new long[2][x + 1][y + 1];
        for (int j = 0; j <= x; j++) {
            for (int k = 0; k <= y; k++) {
                for (int j2 = 0; j2 < j; j2++) {
                    dp[0][j][k] += dp[0][j2][k];
                }
                for (int k2 = 0; k2 < k; k2++) {
                    dp[0][j][k] += dp[1][j][k2];
                }
                dp[0][j][k] %= MOD;
                dp[0][j][k] *= inverse[j + k];
                dp[0][j][k] %= MOD;
                dp[1][j][k] = (dp[0][j][k] + (inverse[j + k] * ((long) j))) % MOD;
            }
        }
        long answer = dp[0][x][y];
        for (long k = 1; k <= n; k++) {
            answer *= k;
            answer %= MOD;
        }
        System.out.println(answer);
    }
 
    public static long inverse(long x) {
        long s = x;
        long res = 1;
        long exponent = MOD - 2;
        while (exponent != 0L) {
            if ((exponent & 1L) == 1L) {
                res *= s;
                res %= MOD;
            }
            exponent /= 2L;
            s *= s;
            s %= MOD;
        }
        return res;
    }
}

To speed this up, note that the bottleneck of the runtime comes from computing the terms like $\sum_{j_{2} < j} d p [0] [j_{2}] [k] .$ Now, suppose we are computing the value $d p [0] [j] [k]$ and want to find the value $\sum_{j_{2} < j} d p [0] [j_{2}] [k]$ without using a loop. To do this, note that we have already computed the value of $d p [0] [j - 1] [k],$ which required the value of $\sum_{j_{2} < j - 1} d p [0] [j_{2}] [k] .$ Since we have already computed $\sum_{j_{2} < j - 1} d p [0] [j_{2}] [k],$ we can use the fact that $\sum_{j_{2} < j} d p [0] [j_{2}] [k] = d p [0] [j - 1] [k] + \sum_{j_{2} < j - 1} d p [0] [j_{2}] [k],$ which takes $O (1)$ time instead of $O (N)$ time to compute.

Since we can now compute the $N^{2}$ terms of the DP in $O (1)$ time each, our overall time complexity is now $O (N^{2}) .$

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class ExpectedHILO {
    public static final long MOD = 1000000007;
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int x = Integer.parseInt(tokenizer.nextToken());
        int y = n - x;
        long[] inverse = new long[n + 1];
        for (int k = 1; k <= n; k++) {
            inverse[k] = inverse(k);
        }
        long[][][] dp = new long[2][x + 1][y + 1];
        long[] sums1 = new long[x + 1];
        long[] sums2 = new long[y + 1];
        for (int j = 0; j <= x; j++) {
            for (int k = 0; k <= y; k++) {
                dp[0][j][k] = (inverse[j + k] * (sums1[j] + sums2[k])) % MOD;
                dp[1][j][k] = (inverse[j + k] * (sums1[j] + sums2[k] + ((long) j))) % MOD;
                sums1[j] += dp[1][j][k];
                sums1[j] %= MOD;
                sums2[k] += dp[0][j][k];
                sums2[k] %= MOD;
            }
        }
        long answer = dp[0][x][y];
        for (long k = 1; k <= n; k++) {
            answer *= k;
            answer %= MOD;
        }
        System.out.println(answer);
    }
 
    public static long inverse(long x) {
        long s = x;
        long res = 1;
        long exponent = MOD - 2;
        while (exponent != 0L) {
            if ((exponent & 1L) == 1L) {
                res *= s;
                res %= MOD;
            }
            exponent /= 2L;
            s *= s;
            s %= MOD;
        }
        return res;
    }
}

2. Linearity of Expectation Solution

We will distinguish between two types of HILOs and count both of them. Recall the definition of the string $S$ in the problem statement. Consider a "HILO," which occurs at position $i$ in string $S$ . We call this "HILO" "special" if there is no "LO" before position $i$ ; otherwise, we call it a "normal" HILO. For a normal HILO, denote the rightmost "LO" before position $i$ as the "corresponding" LO to this normal HILO.

First, we will count the number of "normal" HILOs.

Instead of summing the number of HILOs over all permutations, we will count the number of permutations over every possible HILO.

Formally, for all $a, b, c, p_{a}, p_{b}, p_{c}$ such that $1 \leq a, b, c, p_{a}, p_{b}, p_{c} \leq N$ and $c < a < b,$ we will count the number of permutations such that the following conditions hold:

1. The $a$ th value in the permutation is $p_{a},$ the $b$ th value in the permutation is $p_{b}$ , and the $c$ th value in the permutation is $p_{c}$ .

2. Bessie says "HI" at position $a$ , "LO" at position $b$ , and "LO" at position $c .$

3. The "HI" at position $a$ and the "LO" at position $b$ together form a "HILO" with corresponding LO at position $c$ .

To enforce these conditions, it is necessary and sufficient that the following conditions hold:

4. $p_{c} < p_{b} < x + 0.5 < p_{a}$

5. For all values $v$ in the permutation before $b$ (other than $p_{a}$ and $p_{c}$ ), either $p_{a} < v$ or $v < p_{c} .$

Condition $4$ ensures that the values are in the right order, while condition $5$ ensures that the "HI" at position $a$ and the "LO" at position $b$ together form a "HILO" with corresponding LO at position $c$ .

Now, it remains to count the number of permutations such that conditions $4$ and $5$ hold. There are $N - p_{a} + p_{c} - 1$ possibilities for the remaining values in the permutation before position $b,$ and there are $b - 3$ values that need to be chosen, for a total of $\frac{(N - p_{a} + p_{c} - 1)!}{(N - p_{a} + p_{c} - 1 - (b - 3))!}$ ways to choose these values. After these values have been chosen, the remaining values in the permutation after position $b$ can be ordered arbitrarily, of which there are $N - b$ left, for a total of $(N - b)!$ ways.

So, the desired sum is $\sum_{a, b, c, p_{a}, p_{b}, p_{c} ∣ 1 \leq c < a < b \leq N, 1 \leq p_{c} < p_{b} < x + 0.5 < p_{a} \leq N} \frac{(N - p_{a} + p_{c} - 1)! (N - b)!}{(N - p_{a} + p_{c} - b + 2)!}$ . If we sum this naively, we get a $O (N^{6})$ solution, which is enough for $10$ test cases.

Note that $p_{b}, a, c$ do not appear in the summand, so we can easily rewrite the sum as $\sum_{b, p_{c}, p_{a} ∣ 1 \leq b \leq N, p_{c} < x + 0.5 < p_{a}} \frac{(N - p_{a} + p_{c} - 1)! (N - b)!}{(N - p_{a} + p_{c} - b + 2)!} \cdot (x - p_{c}) \cdot (\binom{b - 1}{2}) .$ If we sum this naively, we get a $O (N^{3})$ solution, which is enough for $18$ test cases.

Now, to optimize this further, suppose $b, p_{c}$ are fixed values. Then, the above summand can be expressed in the form $\sum_{p_{a} = x + 1}^{n} C_{1} \frac{(C_{2} - p_{a})!}{(C_{3} - p_{a})!}$ , which is also of the form $\sum_{p_{a} = C_{4}}^{C_{5}} C_{6} (\binom{C_{7} + p_{a}}{C_{8}})$ for constants $C_{i}$ in terms of $b, p_{c} .$ Using the Hockey Stick Identity, we have that $\sum_{p_{a} = C_{4}}^{C_{5}} C_{6} (\binom{C_{7} + p_{a}}{C_{8}}) = C_{6} (\binom{C_{7} + C_{5} + 1}{C_{8} + 1}) - C_{6} (\binom{C_{7} + C_{4}}{C_{8} + 1}),$ which can be computed in $O (1)$ time for fixed $b, p_{c} .$

Alternatively, we can iterate over the value of $p_{c} - p_{a},$ which does not require Hockey Stick.

Thus, for each of the $N^{2}$ possible pairs $b, p_{c},$ we can find the value of the summand in $O (1)$ time, for a total of $O (N^{2})$ time.

Counting special HILOs can be done similarly, but we only need to iterate over values of $a, b, p_{a}, p_{b},$ and it turns out that only $p_{a}$ and $b$ appear in the summand, so the sum can easily be optimized to $O (N^{2})$ without using Hockey Stick. Using an application of Hockey Stick, we can reduce counting special HILOs to an $O (N)$ calculation, but this is not necessary to solve the problem.

Richard's $N^{6}$ code:

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;

const int MOD = 1e9+7;

/**
 * Description: Modular arithmetic.
 * Source: KACTL
 * Verification: https://open.kattis.com/problems/modulararithmetic
 * Usage: mi a = MOD+5; cout << (int)inv(a); // 400000003
 */
 
struct mi {
 	int v; explicit operator int() const { return v; } 
	mi():v(0) {}
	mi(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
};
mi& operator+=(mi& a, mi b) { 
	if ((a.v += b.v) >= MOD) a.v -= MOD; 
	return a; }
mi& operator-=(mi& a, mi b) { 
	if ((a.v -= b.v) < 0) a.v += MOD; 
	return a; }
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((ll)a.v*b.v); }
mi& operator*=(mi& a, mi b) { return a = a*b; }
mi pow(mi a, ll p) { assert(p >= 0); // won't work for negative p
	return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
mi inv(mi a) { assert(a.v != 0); return pow(a,MOD-2); }
mi operator/(mi a, mi b) { return a*inv(b); }
bool operator==(mi a, mi b) { return a.v == b.v; }
 
using vmi = vector<mi>;
/**
 * Description: pre-compute factorial mod inverses,
 	* assumes $MOD$ is prime and $SZ < MOD$.
 * Time: O(SZ)
 * Source: KACTL
 * Verification: https://dmoj.ca/problem/tle17c4p5
 */
 
vmi invs, fac, ifac;
void genFac(int SZ) {
	invs.resize(SZ), fac.resize(SZ), ifac.resize(SZ); 
	invs[1] = fac[0] = ifac[0] = 1; 
	for(int i = 2; i < SZ; i++) invs[i] = mi(-(ll)MOD/i*(int)invs[MOD%i]);
	for(int i = 1; i < SZ; i++) fac[i] = fac[i-1]*i, ifac[i] = ifac[i-1]*invs[i];
}
mi comb(int a, int b) {
	if (a < b || b < 0) return 0;
	return fac[a]*ifac[b]*ifac[a-b]; }
 
 
mi FAC(int a){
	if(a < 0) return mi(0);
	return fac[a];
}
 
mi IFAC(int a){
	if(a < 0) return mi(0);
	return ifac[a];
}
 
int main() {
	genFac(20005);
	int N, X; cin >> N >> X;
	mi ans = mi(0);
	for(int c = 1; c <= N; c++){
		for(int a = c+1; a <= N; a++){
			for(int b = a+1; b <= N; b++){
				for(int p_c = 1; p_c <= N; p_c++){
					for(int p_b = p_c+1; p_b <= N; p_b++){
						if(p_b > X) continue;
						for(int p_a = X+1; p_a <= N; p_a++){
							ans+=FAC(N-p_a+p_c-1)*FAC(N-b)*IFAC(N-p_a+p_c-1-b+3);
						}
					}
				}
			}
		}
	}
	
	for(int a = 1; a <= N; a++){
		for(int b = a+1; b <= N; b++){
			for(int p_b = 1; p_b <= X; p_b++){
				for(int p_a = X+1; p_a <= N; p_a++){
					ans+=FAC(N-p_a)*FAC(N-b)*IFAC(N-p_a-b+2);
				}
			}
		}
	}
 
	cout << ans.v << "\n";
}

Richard's $N^{2}$ code:

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;

const int MOD = 1e9+7;

/**
 * Description: Modular arithmetic.
 * Source: KACTL
 * Verification: https://open.kattis.com/problems/modulararithmetic
 * Usage: mi a = MOD+5; cout << (int)inv(a); // 400000003
 */
 
struct mi { // WARNING: needs some adjustment to work with FFT
 	int v; explicit operator int() const { return v; } 
	mi():v(0) {}
	mi(ll _v):v(int(_v%MOD)) { v += (v<0)*MOD; }
};
mi& operator+=(mi& a, mi b) { 
	if ((a.v += b.v) >= MOD) a.v -= MOD; 
	return a; }
mi& operator-=(mi& a, mi b) { 
	if ((a.v -= b.v) < 0) a.v += MOD; 
	return a; }
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((ll)a.v*b.v); }
mi& operator*=(mi& a, mi b) { return a = a*b; }
mi pow(mi a, ll p) { assert(p >= 0); // won't work for negative p
	return p==0?1:pow(a*a,p/2)*(p&1?a:1); }
mi inv(mi a) { assert(a.v != 0); return pow(a,MOD-2); }
mi operator/(mi a, mi b) { return a*inv(b); }
bool operator==(mi a, mi b) { return a.v == b.v; }
 
using vmi = vector<mi>;
/**
 * Description: pre-compute factorial mod inverses,
 	* assumes $MOD$ is prime and $SZ < MOD$.
 * Time: O(SZ)
 * Source: KACTL
 * Verification: https://dmoj.ca/problem/tle17c4p5
 */
 
vmi invs, fac, ifac;
void genFac(int SZ) {
	invs.resize(SZ), fac.resize(SZ), ifac.resize(SZ); 
	invs[1] = fac[0] = ifac[0] = 1; 
	for(int i = 2; i < SZ; i++) invs[i] = mi(-(ll)MOD/i*(int)invs[MOD%i]);
	for(int i = 1; i < SZ; i++) fac[i] = fac[i-1]*i, ifac[i] = ifac[i-1]*invs[i];
}
mi comb(int a, int b) {
	if (a < b || b < 0) return 0;
	return fac[a]*ifac[b]*ifac[a-b]; }
 
 
mi FAC(int a){
	if(a < 0) return mi(0);
	return fac[a];
}
 
mi IFAC(int a){
	if(a < 0) return mi(0);
	return ifac[a];
}

int main() {
	genFac(20005);
	int N, X; cin >> N >> X;
	mi ans = mi(0);
	for(int b = 1; b <= N; b++){
		for(int p_c = 1; p_c <= X; p_c++){
			ans+=(comb(N+p_c-X-1, b-2)-comb(p_c-1, b-2))*FAC(b-1)*FAC(N-b)*mi(X-p_c)*invs[2];
		}
	}
	for(int b = 1; b <= N; b++){
		for(int p_a = X+1; p_a <= N; p_a++){
			ans+=mi(X)*FAC(N-p_a)*FAC(N-b)*IFAC(N-p_a-b+2)*mi(b-1);
		}
	}
	cout << ans.v << "\n";
}

We now present an alternative way to optimize counting normal HILOs from $O (N^{3})$ to $O (N)$ . $\sum_{b, p_{c}, p_{a} ∣ 1 \leq b \leq N, p_{c} < x + 0.5 < p_{a}} \frac{(N - p_{a} + p_{c} - 1)! (N - b)!}{(N - p_{a} + p_{c} - b + 2)!} \cdot (x - p_{c}) \cdot (\binom{b - 1}{2})$ .

Let $p_{a} - p_{c} = d_{a c} .$ Then, our sum is equal to $\sum_{d_{a c}} \sum_{b = 1}^{N} \sum_{p_{c}} \frac{(N - d - 1)! (N - b)!}{(N - d - b + 2)!} \cdot (x - p_{c}) \cdot (\binom{b - 1}{2})$ , where $p_{a}, p_{c}$ must satisfy $1 \leq p_{c} < x + 0.5 < p_{a} \leq N .$

Consider the set of all pairs $(p_{a}, p_{c})$ such that the above condition holds for some fixed value of $d_{a c} = p_{a} - p_{c} .$ Let $f (d_{a c})$ be the size of the set, and let $g (d_{a c})$ be the sum over all such pairs of $p_{c} .$ Both of these values can be computed in $O (1)$ for each value of $d_{a c} .$

Then, the sum is equal to $\sum_{d_{a c} = 1}^{N - 1} \sum_{b = 1}^{N} \frac{(N - d_{a c} - 1)! (N - b)!}{(N - d_{a c} - b + 2)!} \cdot (x \cdot f (d_{a c}) - g (d_{a c})) \cdot (\binom{b - 1}{2})$ $= \sum_{d_{a c} = 1}^{N - 1} (x \cdot f (d_{a c}) - g (d_{a c})) (N - d_{a c} - 1)! \sum_{b = 1}^{N} \frac{(N - b)!}{(N - d_{a c} - b + 2)!} \cdot (\binom{b - 1}{2})$

If we ignore the $(\binom{b - 1}{2})$ term in the inner loop, then the inner loop could easily be removed by an application of Hockey Stick (similar to the application mentioned earlier). To do this, note that $(\binom{b - 1}{2}) = C_{1} (N - b + 1) (N - b + 2) + C_{2} (N - b + 1)$ for constants $C_{1}, C_{2}$ , so

$\sum_{b = 1}^{N} \frac{(N - b)!}{(N - d_{a c} - b + 2)!} \cdot (\binom{b - 1}{2}) = C_{1} \sum_{b = 1}^{N} \frac{(N - b + 2)!}{(N - d_{a c} - b + 2)!} + C_{2} \sum_{b = 1}^{N} \frac{(N - b + 1)!}{(N - d_{a c} - b + 2)!}$ .

Now, similar to before, we can apply Hockey Stick to calculate both of these sums in $O (1)$ time.

Thus, we have counted both special and normal HILOs in $O (N)$ time, leading to a $O (N)$ time solution.

----

As Rowechen Zhong notes here, there is actually a simple formula for the number of HILOs (assuming $0 < x < N$ ):

Answer (N, x) = N! \cdot E [# (H I L O)] = N! \cdot 1 2 \cdot (H x + H N - x - H N + N - x N)

where $H_{i} ≜ \sum_{j = 1}^{i} \frac{1}{j}$ . Code:

...

mi H(int x) {
	mi ans = 0;
	for (int i = 1; i <= x; ++i) ans += invs[i];
	return ans;
}

int main() {
	int N,x; cin >> N >> x;
	if (x == 0) {
		cout << "0\n";
		exit(0);
	}
	genFac(N+1);
	mi expected = (H(x)+H(N-x)-H(N)+(mi)(N-x)*invs.at(N))/2;
	cout << (fac.at(N)*expected).v << "\n";
}

Here is a different way to come up with the above formula for $E [# (H I L O)]$ (as well as $E [# (L O L O)], E [# (L O H I)],$ and $E [# (H I H I)]$ ):

Recall from the work above that

E [# (H I L O)] = E [normal H I L O s] + E [special H I L O s] = E [# (values a < c \leq x < b such that a, b, c form L O H I L O)] + Pr [H I L O without a preceding L O] = E [# (a < c \leq x < b such that a, b, c form L O H I L O)] + N - x N .

Note that our notation here is slightly different than above; here, $a, b, c$ denote values rather than positions. We can actually count the number of normal HILOs directly with a triply nested for loop:

...
 
int main() {
	int N,x; cin >> N >> x;
	if (x == 0) {
		cout << "0\n";
		exit(0);
	}
	genFac(N+1);
	mi expected = (N-x)*invs.at(N); // special HILOs
	for (int a = 1; a <= x; ++a) // normal HILOs
		for (int b = x+1; b <= N; ++b) 
			for (int c = a+1; c <= x; ++c) {
				// probability that we see LO at a, then HI at b, then LO at c
				// only depends on relative ordering of values in a..b
				const int len = b-a+1;
				expected += invs.at(len)*invs.at(len-1)*invs.at(len-2);
			}
	cout << (expected*fac.at(N)).v << "\n";
}

Given the value of $E [# (H I L O)]$ , we can get the expected number of LOHIs:

E [# (L O H I)] = E [# (H I L O)] + Pr [response = L O \dots H I] - Pr [response = H I \dots L O] = E [# (H I L O)] + Pr [p 1 \leq x and x appears before x + 1 in p] - Pr [p 1 > x and x + 1 appears before x in p] = E [# (H I L O)] + x + 1 2 N - N - x + 1 2 N = E [# (H I L O)] + 2 x - N 2 N .

Define a HILOLO triple $(a, b, c)$ to be values satisfying $b < c \leq x < a$ such that $a$ appears before $b$ before $c$ , $b$ and $c$ are two consecutive LOs, and $a$ is the latest HI that appears before $b$ We can get the expected number of LOLOs by adding the number of HILOLOs with the number of LOLOs with no HI preceding it. The code to count the expected number of HILOLOs turns out to be identical to the code used to compute the expected number of LOHILOs above, so:

E [# (L O L O)] = E [# (b < c \leq x < a such that a, b, c form H I L O L O)] + E [(# L O L O s without a preceding H I)] = E [# (a < c \leq x < b such that a, b, c form L O H I L O)] + E [(# L O L O s without a preceding H I)] = E [# (a < c \leq x < b such that a, b, c form L O H I L O)] + (E [# (L O s before first H I)] - Pr [exists L O before first H I]) = E [# (a < c \leq x < b such that a, b, c form L O H I L O)] + \sum i = 1 x (1 N - x + i) - x N = E [# (H I L O)] + H N - H N - x - 1.

The equality $E [# (L O before first H I)] = \sum_{i = 1}^{x} (\frac{1}{N - x + i})$ can be derived by starting with a permutation of the values $x + 1 \dots N$ and then consider adding each of the values $x \dots 1$ to the permutation in that order. $x + 1 - i$ is a LO only if it precedes all of the values $x + 2 - i \dots N$ , which occurs with probability $\frac{1}{N - x + i}$ .