题目链接

长椅安置

题目描述

公园内有 条东西向小径与 条南北向小径，彼此相交形成 个交叉点。现有 张长椅需要放置，要求：

  • 每张长椅放在某个交叉点；
  • 同一条小径上 至多 放置一张长椅。

请计算满足条件的放置方案数量。输入 满足 。

解题思路

这个问题是在一个 的网格中放置 张长椅，并要求任意两张长椅都不能在同一行或同一列。这是一个经典的组合计数问题。

我们可以分两步来构造一个合法的放置方案：

第一步：选择放置长椅的行和列

要放置 张长椅，它们必须占据 个不同的行和 个不同的列。

  1. 选择 5 个不同的行：从 个可用的行中，选择 个来放置长椅。这是一个组合问题，方案数为 。
  2. 选择 5 个不同的列：同样，从 个可用的列中，选择 个。方案数也是 。

第二步：将选定的行和列进行配对

现在我们已经选定了 个行和 个列，形成了一个 的子网格。我们需要在这个子网格中放置 张长椅，且每行每列恰好一个。

  • 对于第一个选定的行，我们可以在 个选定的列中任选一个位置。
  • 对于第二个选定的行，我们只剩下 个可选的列。
  • ...
  • 对于最后一个选定的行，只剩下 个列可选。

因此，配对的方案数是 。

最终公式

根据乘法原理，总方案数是以上所有步骤方案数的乘积：

另一种等价思路

我们也可以这样思考：

  1. 选择 5 个行：有 种方法。
  2. 为这 5 行分配不同的列：
    • 对于第一个被选中的行，我们有 个列可以选择。
    • 对于第二个被选中的行，我们有 个列可以选择。
    • ...
    • 对于第五个被选中的行，我们有 个列可以选择。 这部分的方案数是一个排列数 。

总方案数为这两个步骤的乘积：

这两个公式是等价的，因为 。

实现

由于 最大为 ，结果会很大，需要使用 64 位整型（long long）来存储。我们可以先计算 ，然后计算 ，最后将两者相乘。

代码

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    // 计算 P(n, 5)
    long long p_n_5 = 1;
    for (int i = 0; i < 5; ++i) {
        p_n_5 *= (n - i);
    }
    
    // 计算 C(n, 5)
    long long c_n_5 = p_n_5 / 120;
    
    // 总方案数 = C(n, 5) * P(n, 5)
    long long ans = c_n_5 * p_n_5;
    
    cout << ans << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 计算 P(n, 5)
        long p_n_5 = 1;
        for (int i = 0; i < 5; i++) {
            p_n_5 *= (n - i);
        }
        
        // 计算 C(n, 5)
        long c_n_5 = p_n_5 / 120;
        
        // 总方案数 = C(n, 5) * P(n, 5)
        long ans = c_n_5 * p_n_5;
        
        System.out.println(ans);
    }
}

import math

n = int(input())

# 计算 P(n, 5)
p_n_5 = math.perm(n, 5)

# 计算 C(n, 5)
c_n_5 = math.comb(n, 5)

# 总方案数 = C(n, 5) * P(n, 5)
ans = c_n_5 * p_n_5

print(ans)

算法及复杂度

  • 算法：组合学、排列组合计数

  • 时间复杂度：由于放置的长椅数量是固定的 5，计算 和 的循环次数是常数。因此，时间复杂度为 。

  • 空间复杂度：只使用了常数个变量来存储结果，空间复杂度为 。