HDU2048 神、上帝以及老天爷

题目：http://acm.hdu.edu.cn/showproblem.php?pid=2048

看书发现了这道题，刚开始没理解题意，以为是中奖的概率，---> 1/n

后来知道了是典型的错排问题。（后来发现是真的裸）

递推：

Di 为 i个人的错排数 D1 = 0, D2 = 1;

第N个人拿了自己的名字，假如前面的N-1个人是错排的，那么第N个人随便找一个人交换就整体满足错排。 N-1(Dn-1)

假如前面的N-1个人里面有一个拿的是自己的票（N-1种可能）剩余的满足错排，那个人和N交换后整体满足错排。 N-1(Dn-2)

所以 Dn = (n-1)*(Dn-1+Dn-2)

容斥原理也可以推到，但是还没有学习，所以先不写出来了。

AC代码：

#include <iostream>

#include <stdio.h>

#include <math.h>

#include <string.h>

#include <stdlib.h>

#include <string>

#include <bitset>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <algorithm>

#include <sstream>

#include <stack>

using namespace std;

#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 pb push_back

#define mp make_pair

#define all(x) (x).begin(),(x).end()

#define fi first

#define se second

#define SZ(x) ((int)(x).size())

#define FO freopen("in.txt", "r", stdin);

#define lowbit(x) (x&-x)

typedef vector<int> VI;

typedef long long ll;

typedef pair<int,int> PII;

const ll mod=1000000007;

const int inf = 0x3f3f3f3f;

ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

template <class T>

inline bool scan_d(T &ret)

{

    char c; int sgn;

    if (c = getchar(), c == EOF) return 0; //EOF

    while (c != '-' && (c < '0' || c > '9')) c = getchar();

    sgn = (c == '-') ? -1 : 1;

    ret = (c == '-') ? 0 : (c - '0');

    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');

    ret *= sgn;

    return 1;

}

inline void out(int x)

{

    if (x > 9) out(x / 10);

    putchar(x % 10 + '0');

}

ll a[30], sum;

int main() {

	a[1] = 0;//1个人的时候，不会出现错排

	a[2] = 1;//2个人的时候，只能出现一种错排

	rep(i, 3, 25) {

		a[i] = (i-1)*(a[i-1]+a[i-2]);//递推关系

	}

	int _, n;

	for(scan_d(_);_;_--) {

		scan_d(n);

		sum = 1;

		rep(i, 1, n+1) {//总的排列数

			sum *= i;

		}

		printf("%.2lf%%\n", a[n]*100.0/sum);

	}

}

巴特西

HDU2048 神、上帝以及老天爷

最新文章

热门文章