xtu oj 1194 Recipient

2023-12-13 14:45:03
题目描述

快递小哥每天都辛苦的送快递,今天他需要送N份快递给N个收件人,第i份快递需要送给第i个收件人。 请问其中发生恰好K个送错了的情况数是多少?

输入

存在多样例。 每行输入两个整数N和K,1≤N≤1000,0≤K≤N。 如果两个都为0,则表示输入结束,这个样例不需要处理。

输出

每行输出一个样例的结果,因为数值会比较大,所有结果需要对109+7取模。

样例输入
1 1
2 1
3 2
1000 1000
0 0

样例输出
0
0
3
37043040

AC代码

#include<stdio.h>
#define mod 1000000007
#define N 1005
#define ll long long
ll dp[N][N]={};//杨辉三角
ll D[N]={};//错排 
void init(){
	int i,j;
	D[2]=1;
	for(i=3;i<N;i++){
		D[i]=(i-1)*(D[i-1]+D[i-2])%mod;
	}
    for(i=0;i<N;i++){
		dp[i][0]=1;
		dp[i][i]=1;
	}
	for(i=1;i<N;i++){//动态规划思想 
		for(j=1;j<i;j++){
			dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;
		}
	}
} 
int main()
{
	init();
	int n,k;
	while(scanf("%d%d",&n,&k)!=EOF){
		if(n==0&&k==0)break;
		if(k==0)printf("1\n");
		else{
			printf("%I64d\n",D[k]*dp[n][k]%mod);
		} 
	}
}

解题思路:动态规划+错排思想,动态规划可参考1354 Robot这道题。先求出n个元素错误排列数,即D(n),再就是从n个元素取k个元素的方案数,就是求组合数C(n,k),C(n,k)*D(n)即为恰好K个送错了的情况数。

求组合数,杨辉三角求组合数是很常用的一种方法。为什么杨辉三角可以求组合数呢?分析如下

杨辉三角

dp[i][j]=dp[i-1][j]+dp[i-1][j-1]

dp[i][0]=dp[i][i]=1

组合数

这和杨辉三角的表示是一样的,所以可以用杨辉三角表示组合数。

错排

考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。n个元素的错排数记为D(n)。

错排公式

D(n)=(n-1)(D(n-1)+D(n-2))

初始值:D(1)=0,D(2)=1

要注意考虑特殊值:当k=0时,即全部送对,只有一种情况。

文章来源:https://blog.csdn.net/m0_75005390/article/details/134969621
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。