e678 - 12024 - Hats

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 n 個人，每個人都戴錯帽子的情況數，並以分數形式輸出，分子是戴錯帽子的情況數，分母是所有人戴帽子的總情況數。n 的範圍是 2 到 12。

解題思路

這題是個組合數學問題。對於 n 個人，總共有 n! 種戴帽子的方式。戴錯帽子的情況數，稱為錯位排列 (derangement) 的數量，可以用遞迴關係式計算：D(n) = (n-1) * [D(n-1) + D(n-2)]，其中 D(1) = 0, D(2) = 1。 題目要求的是 D(n) / n!。由於 n 的範圍不大，可以預先計算出 D(n) 和 n! 的值，然後直接輸出結果。程式碼中 ans1 陣列儲存錯位排列的數量，ans2 陣列儲存 n! 的值。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
long long int ans1[12]={1,2},ans2[12]={2,6};
int main(){
	int n;
	for(int i=2;i<12;++i){
		ans1[i]=(i+1)*(ans1[i-1]+ans1[i-2]);
		ans2[i]=ans2[i-1]*(i+2);
	}
	cin >> n;
	while(cin >> n)
		cout << ans1[n-2] << "/" << ans2[n-2] << "\n";
}