题目链接

长椅安置

题目描述

公园内有 条东西向小径与 条南北向小径，彼此相交形成一个 的网格状交叉点布局。 现有 5 张长椅需要放置在这些交叉点上，要求满足以下条件：

  1. 每张长椅必须放在一个交叉点上。
  2. 任意一条小径（无论是东西向还是南北向）上，至多只能放置一张长椅。

请计算所有满足条件的放置方案总数。

输入:

  • 输入一行一个整数 （）。

输出:

  • 输出一个整数，表示可行的方案总数。

解题思路

这是一个典型的排列组合问题。我们需要在 的网格上放置5张长椅，并保证任意两张长椅的行号和列号都互不相同。

我们可以分两步来完成放置：

  1. 选择5个不同的行和5个不同的列 首先，我们需要确定哪5行和哪5列将用于放置长椅。

    • 从 行中选择5行，方案数为 。
    • 从 列中选择5列，方案数为 。

  2. 在选定的 子网格内排列 一旦我们选定了5行和5列，就形成了一个 的子网格。我们需要在这个子网格的交叉点上放置5张长椅，且每行每列只能放一张。这等价于在一个 的棋盘上放置5个互相不攻击的“车”（Rook），其方案数正好是 。

  3. 总方案数 根据乘法原理，将以上所有步骤的方案数相乘即可得到最终答案： 总方案数 =

    我们可以对这个公式进行化简以便计算： 总方案数 =

    其中：

    由于 最大为100，结果会很大，需要使用64位整型（long long 或 long）来存储。

代码

#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    
    long long p_n_5 = 1;
    for (int i = 0; i < 5; ++i) {
        p_n_5 *= (n - i);
    }
    
    long long c_n_5 = p_n_5 / 120;
    
    long long ans = c_n_5 * p_n_5;
    
    cout << ans << '\n';
    
    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();
        
        long p_n_5 = 1;
        for (int i = 0; i < 5; i++) {
            p_n_5 *= (n - i);
        }
        
        long c_n_5 = p_n_5 / 120;
        
        long ans = c_n_5 * p_n_5;
        
        System.out.println(ans);
    }
}

n = int(input())

# 计算 P(n, 5)
p_n_5 = 1
for i in range(5):
    p_n_5 *= (n - i)

# 计算 C(n, 5)
c_n_5 = p_n_5 // 120

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

print(ans)

算法及复杂度

  • 算法：组合数学、排列与组合
  • 时间复杂度：，因为循环次数是固定的（5次）。
  • 空间复杂度：。