本文共 2678 字，大约阅读时间需要 8 分钟。
楼教主男人八题中的第一题：
最大50座不同城市，组成全联通图的数量，不取模。
#include #include #include #include #include #define maxn 55std::vector C[maxn][maxn]; // 组合数std::vector P[maxn*maxn]; // 2的n次幂bool Pc[maxn]; // 幂级数染色std::vector ans[maxn]; // 图的数量bool ansc[maxn]; // ans染色const long long BASE = 100000000; // 进制void print(const std::vector &x) { int l = x.size(); if( l == 0) printf("0\n"); else{ printf("%lld",x[l-1]); for(int i = l - 2; i >= 0; i--){ printf("%08lld",x[i]); } printf("\n"); }}void assignment(std::vector &x,long long y){ x.clear(); while(y > 0){ x.push_back(y % BASE); y /= BASE; }}void addv(std::vector &z,const std::vector &x,const std::vector &y){ z.clear(); for(long long i = 0, g = 0; ; i++){ if( g == 0 && i >= x.size() && i >= y.size()) break; long long t = g; if( i < x.size()) t += x[i]; if( i < y.size()) t += y[i]; z.push_back(t % BASE); g = t / BASE; }}void minusv(std::vector &z,const std::vector &x,const std::vector &y){ z.clear(); long long g = 0; for(int i = 0; i < x.size() ; i++){ long long t = 0; if(i < y.size()) t += y[i]; if(x[i] - g < t){ z.push_back(BASE - t + x[i] - g); g = 1;} else{ z.push_back(x[i] - g - t); g = 0;} } int loc = (int)z.size() - 1; while(loc>=0&&loc &z, long long x,const std::vector &y){ z.clear(); long long t = 0; for(int i = 0; i < y.size(); i++){ t += y[i] * x; z.push_back( t % BASE ); t /= BASE; } if(t!=0) z.push_back(t);}void multi(std::vector &z,const std::vector &x,const std::vector &y){ z.clear(); std::vector t; std::vector zt; for(int i = 0; i < x.size(); i++){ multilong(t,x[i],y); t.insert(t.begin(),i,0); addv(zt,t,z); z = zt; }}void f(int y);// 2^(y*(y-2)/2)void h(int y){ if(!Pc[y]){ std::vector p; assignment(P[y],1); assignment(p,2); std::vector Pt; for(int i = y*(y-1)/2; i > 0 ; i>>=1){ if(i & 1){ multi(Pt,p,P[y]); P[y] = Pt;} multi(Pt,p,p); p = Pt; } Pc[y] = true; }}//void g(std::vector &z,int y){ std::vector x; std::vector t; for(int i = 1; i < y; i++){ f(i); h(y-i); multi(x,P[y-i],ans[i]); multi(t,C[y-1][i-1],x); addv(x,z,t); z = x; }}void f(int y){ if(!ansc[y]){ std::vector gv; h(y); g(gv,y); minusv(ans[y],P[y],gv); ansc[y] = true; }}int main(){ memset(C,0,sizeof(C)); memset(ansc,0,sizeof(ansc)); memset(Pc,0,sizeof(Pc)); // 组合数 for(int i = 1; i < 51; i++){ assignment(C[i][0],1); assignment(C[i][i],1); for(int j = 1; j < i; j++){ addv(C[i][j],C[i-1][j-1],C[i-1][j]); } } // 30ms //freopen("input.txt","r",stdin); //freopen("output0.txt","w",stdout); int n; while(scanf("%d",&n) != EOF && n){ //double timeS = (double)clock(); if(ansc[n]) print(ans[n]); else{ f(n); print(ans[n]);} //printf("time:%fms\n",(double)clock() - timeS); } return 0;}
转载地址：http://dkwji.baihongyu.com/