vijosP1687 细菌总数

vijosP1687 细菌总数

链接：https://vijos.org/p/1687

【思路】

错排公式+高精度。

题目要求排列数目而且不能有Pi==i的情况出现，可以看出这正是1,2,3,4,5,…n的错排数目。应用错排公式以及高精高精加、高精单精乘即可。

【代码】

 #include<iostream>

 #include<cstring>

 #include<cmath>

 using namespace std;

 struct Bign{

     int len,N[];

     Bign() {

         memset(N,,sizeof(N));

     }

 };

 int n;

 void Add(Bign& a,Bign b) {

     a.len=max(a.len,b.len);

     for(int i=;i<a.len;i++) {

         a.N[i] += b.N[i];

         a.N[i+] += a.N[i]/;

         a.N[i] %= ;

     }

     if(a.N[a.len]) a.len++;

 }

 void multi(Bign& a,int x)

 {

     for(int j=;j<a.len;j++) a.N[j] *= x;

     int i=;

     while(i<a.len || a.N[i]>) {

         a.N[i+] += a.N[i]/;

         a.N[i] %= ;

         i++;                    //i++

     }

     if(a.N[i]) a.len=i+;  //判断

     else a.len=i;

 }

 int main() {

     cin>>n;

     Bign D[];

     D[].len=D[].len=D[].len=; D[].N[]=; D[].N[]=;

     for(int i=;i<=n;i++)

     {

        memset(D[].N,,sizeof(D[].N));

        Add(D[],D[]); Add(D[],D[]);

        multi(D[],i-);

        D[]=D[]; D[]=D[];

     }

     for(int i=D[].len-;i>=;i--) cout<<D[].N[i];

     return ;

 }