HDU2048 神、上帝以及老天爷-白红宇

HDU2048 神、上帝以及老天爷

阅读量：7072 次

发布时间：2019-06-28

本文共 1719 字，大约阅读时间需要 5 分钟。

题目：

看书发现了这道题，刚开始没理解题意，以为是中奖的概率，---> 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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;#define rep(i,a,n) for (int i=a;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
                   
                     VI;typedef long long ll;typedef pair
                    
                      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 
                     
                      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); }}