题解：UVA12024 Hats

_fallen_leaves_ · 2025-06-02 20:51:38 · 题解

UVA12024 Hats

题意

每人一顶帽子，求每个人都拿错帽子的概率。

思路

每个数都是一个分数，我们把分子和分母分开考虑，本题考虑递推。

分子

考虑错排列，可以直接用错排列（不懂的可以去百度搜索）。f(i)=(i-1)\times(f(i-1)+f(i-2))

其中，我们需要初始化 f(0)=1。

分母

就是总的方案数，分母怎么求呢？其实就可以看成是全排列问题，有 n! 种排列。

其中，我们需要初始化 a(1)=1。

代码

#include<bits/stdc++.h>
using namespace std;
int t,a[15],b[15];
int main()
{
    a[0]=1;
    b[1]=1;
    for(int i=2;i<=12;i++) a[i]=(i-1)*(a[i-2]+a[i-1]);//分子 
    for(int i=2;i<=12;i++) b[i]=b[i-1]*i;//分母 
    cin>>t;
    while(t--)//多组数据 
    {
        int n;
        cin>>n;
        cout<<a[n]<<"/"<<b[n]<<"\n";//多组数据换行 
    }
    return 0;
}