題目鏈接：點(diǎn)擊查看

題目大意：有n對新婚夫婦，有m個(gè)新郎找錯了新娘，問發(fā)生這種情況的可能

題目分析：匹配錯誤問題可以類比于全錯排問題，這里插眼放一個(gè)講的不錯的博客：

https://blog.csdn.net/qq_41661809/article/details/83960179

然后我們就可以直接背過結(jié)論了，關(guān)于全錯排的遞推公式是：

F(n) = (n-1)* [F(n-2) + F(n-1)](F(0)=0,F(1)=0,F(2)=1)

因?yàn)檫@個(gè)題目要求的是n個(gè)人中m個(gè)人全錯排的可能，也就是說我們需要先從n個(gè)人中選出m個(gè)人，也就涉及到了組合數(shù)學(xué)的問題：

C(n,m)=n!/((n-m)!*n!)

這樣一來這個(gè)題目的答案就是C(n,m)*F(m)了，實(shí)現(xiàn)一下就行

注意一下，因?yàn)?0的階乘已經(jīng)到了2e18的程度，所以我們要用longlong來儲存，預(yù)處理遞推打一下表就能實(shí)現(xiàn)O(1)查詢了

還需要注意一下，在實(shí)現(xiàn)答案那個(gè)公式的時(shí)候，記得先除再乘，不然會爆longlong

上代碼吧：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=25;LL f[N],b[N];//f[i]:i的階乘 b[i]:i的全錯排void init() {f[0]=1;for(int i=1;i<=20;i++)f[i]=f[i-1]*i;b[0]=b[1]=0;b[2]=1;for(int i=3;i<=20;i++)b[i]=(i-1)*(b[i-1]+b[i-2]); }int main() { // freopen("input.txt","r",stdin);init();int w;cin>>w;while(w--){int n,m;scanf("%d%d",&n,&m);printf("%lld\n",f[n]/f[n-m]/f[m]*b[m]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 2049 不容易系列之(4)——考新郎(错排问题+组合数学)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。