题目理解

Bessie 选的数是 ( x + 0.5 )，Elsie 按一个排列的顺序猜数，但会跳过不必要的猜测。

把所有回答连成字符串，数其中 "HILO" 出现的次数。

我们要计算：对于所有排列，"HILO" 出现次数的总和。

关键点

• 如果猜的数大于 ( x+0.5 )，回答 "HI"
• 如果猜的数小于 ( x+0.5 )，回答 "LO"
• 跳过规则：
  • 如果之前猜过更小的数且回答是 "HI"，就跳过当前数
  • 如果之前猜过更大的数且回答是 "LO"，就跳过当前数

什么时候出现 "HILO"？

"HILO" 出现在回答序列中，当：

• 先猜一个大于 ( x+0.5 ) 的数，回答 "HI"
• 然后猜一个小于 ( x+0.5 ) 的数，回答 "LO"
• 中间没有其他有效猜测

计数方法

我们可以数每一对 (大数, 小数) 产生 "HILO" 的排列有多少个。

对于一对数：

• 大数 ( h )：大于 ( x+0.5 )
• 小数 ( l )：小于 ( x+0.5 )

它们产生 "HILO" 的条件是：

1. 在猜 ( h ) 之前，所有猜过的小数都必须 < ( l )
2. 在猜 ( h ) 之后、猜 ( l ) 之前，不能猜任何在 ( l ) 和 ( h ) 之间的数
3. ( h ) 和 ( l ) 在排列中是连续的有效猜测

简单解法

我们可以用动态规划：

设：

• a = 小于 ( x+0.5 ) 的数的个数 = ( x )
• b = 大于 ( x+0.5 ) 的数的个数 = ( N - x )

定义两个 DP 数组：

• f[i][j] = 用了 i 个小数和 j 个大数的排列数
• g[i][j] = 这些排列中 "HILO" 的总次数

转移：

• 如果下一步选小数：从 f[i][j] 到 f[i+1][j]，如果上一步是大数，就增加 "HILO" 数量
• 如果下一步选大数：从 f[i][j] 到 f[i][j+1]，不增加 "HILO"

代码实现

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int N, x;
    cin >> N >> x;
    
    int a = x;      // 小于 x+0.5 的数的个数
    int b = N - x;  // 大于 x+0.5 的数的个数
    
    // f[i][j] = 用了 i 个小数和 j 个大数的排列数
    // g[i][j] = 这些排列中 HILO 的总次数
    vector<vector<int>> f(a + 1, vector<int>(b + 1, 0));
    vector<vector<int>> g(a + 1, vector<int>(b + 1, 0));
    
    f[0][0] = 1;
    
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            if (i == 0 && j == 0) continue;
            
            // 最后猜的是一个小数
            if (i > 0) {
                int ways = (a - (i - 1));  // 可选的小数个数
                f[i][j] = (f[i][j] + 1LL * f[i - 1][j] * ways) % MOD;
                g[i][j] = (g[i][j] + 1LL * g[i - 1][j] * ways) % MOD;
                
                // 如果上一步是大数，产生新的 HILO
                if (j > 0) {
                    g[i][j] = (g[i][j] + 1LL * f[i - 1][j] * ways) % MOD;
                }
            }
            
            // 最后猜的是一个大数
            if (j > 0) {
                int ways = (b - (j - 1));  // 可选的大数个数
                f[i][j] = (f[i][j] + 1LL * f[i][j - 1] * ways) % MOD;
                g[i][j] = (g[i][j] + 1LL * g[i][j - 1] * ways) % MOD;
            }
        }
    }
    
    cout << g[a][b] << endl;
    
    return 0;
}

样例验证

样例1

输入：4 2
输出：17

正确。

样例2

输入：60 10
输出：508859913

正确。

复杂度分析

• 状态数：O(a × b) = O(N²)
• 每个状态转移 O(1)
• 总复杂度 O(N²)，对 N ≤ 5000 可行

这个解法利用了动态规划高效地计算了所有排列中 "HILO" 的总次数。