HDU2049全错位排序

先Copy一下什么是全错位排序:

全错位排列:即被著名数学家欧拉(Leonhard Euler,1707-1783)称为组合数论的一个妙题的“装错信封问题”。

“装错信封问题”是由当时最有名的数学家约翰·伯努利(Johann Bernoulli,1667-1748)的儿子丹尼尔·伯努利(DanidBernoulli,1700-1782)提出来的,大意如下:

一个人写了n封不同的信及相应的n个不同的信封,他把这n封信都装错了信封,问都装错信封的装法有多少种?

递推公式

瑞士数学家欧拉按一般情况给出了一个递推公式:

用A、B、C……表示写着n位友人名字的信封,a、b、c……表示n份相应的写好的信纸。把错装的总数为记作f(n)。假设把a错装进B里了,包含着这个错误的一切错装法分两类:

(1)b装入A里,这时每种错装的其余部分都与A、B、a、b无关,应有f(n-2)种错装法。

(2)b装入A、B之外的一个信封,这时的装信工作实际是把(除a之外的)(n-1 )份信纸b、c……装入(除B以外的)n-1个信封A、C……,显然这时装错的方法有f(n-1)种。

总之在a装入B的错误之下,共有错装法f(n-2)+f(n-1)种。a装入C,装入D……的n-2种错误之下,同样都有f(n-2)+f(n-1)种错装法,因此:

f(n)=(n-1) {f(n-1)+f(n-2)}

公式可重新写成 f(n)-nf(n-1)=-[f(n-1)-(n-1)f(n-2)] (n>2)

很显然,比如在10对儿里面有3对儿排错了,3C6选出3对儿再乘以3对儿的错排可能—>AC!

#include <stdio.h>

#include <math.h>

#include <string.h>
long long int combination(int a,int b);
long long int fac(int num);
int main()
{
int m,n,e;
long long int data[21];
memset(data,sizeof(data),0);
data[1]=0;data[2]=1;data[3]=2;
for(int i=4;i<=20;i++)
data[i]=(i-1)(data[i-2]+data[i-1]);
scanf(“%d”,&e);
for(int z=1;z<=e;z++)
{
scanf(“%d%d”,&n,&m);
if(m==n)
printf(“%lld\n”,data[n]);
else
printf(“%lld\n”,combination(n,m)
data[m]);
}
return 0;
}
long long int combination(int a,int b)
{
int i,j;
long long int ans=1;
for(i=a;i>=a-b+1;i–)
ans=ansi;
return ans/fac(b);
}
long long int fac(int num)
{
int i;
long long int out=1;
for(i=1;i<=num;i++)
out=out
i;
return out;
}

字符串匹配的KMP算法 Let's Start From Here

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×