原始题目

神、上帝以及老天爷

• Time Limit: 2000/1000 MS (Java/Others)
  
• Memory Limit: 65536/32768 K (Java/Others)
• Total Submission(s): 50425
  
• Accepted Submission(s): 20379

Problem Description

HDU 2006'10 ACM contest的颁奖晚会隆重开始了！ 为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的：

首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中； 然后，待所有字条加入完毕，每人从箱中取一个字条； 最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！” 大家可以想象一下当时的气氛之热烈，毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀！不过，正如所有试图设计的喜剧往往以悲剧结尾，这次抽奖活动最后竟然没有一个人中奖！

我的神、上帝以及老天爷呀，怎么会这样呢？

不过，先不要激动，现在问题来了，你能计算一下发生这种情况的概率吗？

不会算？难道你也想以悲剧结尾？！

Input

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数\(n(1<n≤20)\),表示参加抽奖的人数。

Output

对于每个测试实例，请输出发生这种情况的百分比，每个实例的输出占一行, 结果保留两位小数(四舍五入)，具体格式请参照sample output。

Sample Input

1
2

Sample Output

50.00%

Author

lcy

Source

递推求解专题练习（For Beginner）

Recommend

lcy

题目大意

如题 # 解题思路

• DP

  手动写一下如何安排参加人员都不中奖就可以发现规律。\(D[i]\)表示i个人符合要求的方案数目

  比如计算dp[4]时，将1的纸条分给2或3或4，这三种情况下，可以变为解决子问题，比如将1的纸条分给2，之后将2、3、4的纸条分给1、3、4，与dp[3]接近，但是1位置不受限制，即1位置可以放2的纸条，这样又变为dp[2]。

  故得到状态转移方程。

  \[ D[n]=(n-1)(D[n-1]+D[n-2]) \]

  最后除以总情况数（排列），计算百分数即可。

• 错排公式

  其实本题是一个错排公式题目，我们上面推导出来的$ D[i]=(i-1)(D[i-1]+D[i-2]) $，实际上就是错排公式的一个递推关系。

  又因为\(D[1]=0,D[2]=1\) 继续推导 \[ \begin{align} D[n] & =(n-1)(D[n-1]+D[n-2]) \\ D[n] - n D[n-1] & = (-1) (D[n-1] - (n-1) D[n-2])\\ D[n] - n D[n-1] & = (-1)^{n-2} (D[2] - 2 D[1]) \\ D[n] & = n D[n-1] + (-1)^{n} \end{align} \] 如此我们得到了递推关系式，那么求通项公式可以用下面几种方法：

  • 可以用母函数方法求出通项公式（还不会，待学了母函数填坑）

  • 可以用容斥原理

  最后得到错排公式为

  \[ D[n] = n!( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots (-1)^{n} \frac{1}{n!} ) \]

• 再补充

  简化公式

  \[ D(n) = [ \frac{n!}{e} + 0.5 ] \]

  证明相见百度，e是自然对数的底，[x]为x的整数部分。

解题代码

• DP

  #include <cstdio>
  #include <cstring>
  #include <iostream>
  #include <set>
  #include <algorithm>
  #include <queue>
  #include <map>
  #include <string>
  #define eps 1e-8
  #define INF 0x3f3f3f3f
  #define rep(i,a,n) for(int i=a;i<n;i++)
  #define per(i,a,n) for(int i=n-1;i>=a;i--)
  using namespace std;
  const int maxn=1e5+5;
  typedef long long ll;
  ll dp[maxn],A[maxn];
  void solve(){
  	memset(dp,0,sizeof(dp));
  	dp[1]=0;
  	dp[2]=1;
  	
  	A[1]=1;
  	A[2]=2;
  	for(ll i=3;i<=20;i++){
  		dp[i]=(i-1)*(dp[i-1]+dp[i-2]);
  		A[i]=A[i-1]*i; 
  //		cout<<dp[i]<<"  "<<A[i]<<endl;
  	}
  }
  using namespace std;
  int main(){
  	int t;
  	solve();
  	while(cin>>t){
  		rep(i,0,t){
  			ll a;
  			cin>>a;
  			double ans=(double)dp[a]/(double)A[a];
  //			cout<<"dp[i]"<<dp[a]<<" "<<"A[i]"<<A[a]<<endl;
  			printf("%.2lf%%\n",ans*100); 
  		}
  	}
  }

• 错排简化公式

  #include <cstdio>
  #include <cstring>
  #include <cmath>
  #include <iostream>
  #include <iomanip>
  #include <set>
  #include <queue>
  #include <stack>
  #include <vector>
  #include <string>
  #include <sstream>
  #include <bits/stdc++.h>
  #define rep(i,a,n) for(int i=a;i<n;++i)
  #define per(i,a,n) for(int i=n-1;i>=a;--i);
  #define ms(x,a) memset((x),a,sizeof((x))) 
  #define INF 0x3f3f3f3f
  #define eps 1e-8
  #define fi first
  #define e 2.718281828459045235360287471352662497757247093699959574966967627724076630353 
  #define se second
  #define mp make_pair
  #define pb push_back
  #define np next_permutation
  #define gapline cout<<"##======================##"<<endl
  using namespace std;
  const int maxn=1e5+5;
  const int maxl=26;
  const int maxm=1e5+5;
  
  typedef long long ll;
  typedef unsigned long long ull;
  typedef vector<int> vi;
  typedef pair<int,int> pii;
  
  ll A[maxl];
  void solve(){
  	A[0]=1;
  	A[1]=1;
  	rep(i,2,maxl) A[i]=A[i-1]*i;
  }
  int n; 
  int main(){
  	ios::sync_with_stdio(false);
  	solve();
  	ll t;
  	cin>>t;
  	while(t--){
  		cin>>n;
  		double ans=floor((double)A[n]/e+0.5);
  		cout<<fixed<<setprecision(2)<<ans*100/A[n]<<"%"<<endl;
  	} 
  }

收获与反思

• 注意分析递推公式。手写前几项找规律也可以。

• 错排公式推导学习

• 挖坑母函数