BZOJ2786:Ural1142 Relation 递推+高精度

思路:

令\(f[i][j]\)表示将\(i\)个数划分为\(j\)个集合的方案数.

则有递推式:

\[f[i][j]=f[i-1][j]*j+f[i-1][j-1]\]

于是\(ans(n)=\sum_{i=1}^{n}f[n][i]*fac(i)\)

数据范围小,随便写写.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int mod=1e4;
struct Int{
    int d[100],l;
    Int():l(1){memset(d,0,sizeof d);}
    inline void operator=(const int&x){memset(d,0,sizeof d),l=1,d[0]=x;}
    inline void operator+=(const Int&B){
        l=l>B.l?l:B.l;
        for(int i=0;i<l;++i){
            d[i]+=B.d[i];
            if(d[i]>=mod)d[i+1]+=d[i]/mod,d[i]%=mod;
        }if(d[l])l++;
    }
    inline void operator*=(const int&x){
        int p=0;
        for(int i=0;i<l;++i)d[i]=(p+=d[i]*x)%mod,p/=mod;
        if(p)d[l++]=p;
    }
    inline Int operator*(const Int&B){
        Int C;
        for(int i=0;i<l;++i)for(int j=0;j<B.l;++j){
            C.d[i+j]+=d[i]*B.d[j];if(C.d[i+j]>=mod)C.d[i+j+1]+=C.d[i+j]/mod,C.d[i+j]%=mod;
        }
        for(C.l=l+B.l+1;!C.d[C.l-1];--C.l);
        return C;
    }
    inline void output(){
        printf("%d",d[l-1]);for(int i=l-2;i>=0;--i)printf("%04d",d[i]);
    }
};
 
Int f[51][51],fac[51],res[51];
 
int main(){
    int i,j;
    for(fac[0]=1,fac[1]=1,i=2;i<=50;++i)fac[i]=fac[i-1],fac[i]*=i;
    for(i=1;i<=50;++i){
        f[i][1]=1,f[i][i]=1;
        for(j=2;j<i;++j)f[i][j]=f[i-1][j],f[i][j]*=j,f[i][j]+=f[i-1][j-1];
    }
     
    for(i=1;i<=50;++i)for(j=1;j<=i;++j)res[i]+=f[i][j]*fac[j];
     
    int T;scanf("%d",&T);
    int x;while(T--)scanf("%d",&x),res[x].output(),puts("");
     
    return 0;
}