[POJ1737 Connected Graph]组合数学、男人8题

【题目大意】

给定N个标号为1~N的点，让你求出对于这N个点，连一些边使得它成为无向连通图的方案有多少种。

【算法分析】

= =看了一下别人的思考过程。。。公式还是自己推的。。。

要利用补集思想，首先连边方案一共有2^(n*(n-1)/2)这么多种。（每条边取或者不取）

然后我们以于1连通的点的个数i为划分状态。

ans[n]=2^(n*(n-1)/2)-Q;

Q=SUM(ans[i]*C(i-1,n-1)*2^((n-i)*(n-i-1)/2))   1<=i

就是固定住1这个点，然后在剩下的n-1个点里取i-1个，总共i个点是1的联通块上的。

然后i个点的连通图有ans[i]这么多方案，所以乘起来，然后根据乘法原理，剩下有n-i个点，

能构成2^((n-i)*(n-i-1)/2)种方案，也都乘起来。

【其他】1A

跑得非常慢，在最后一面= =

【CODE】

#include #include #include using namespace std;
const int ml=372;

int n;
int C[55][55][ml+1];
int ans[55][ml+1];
int cf[1311][ml+1];
int tmp[ml+1],tmp2[ml+1];

struct BNT{
       void plus(int *x,int *y){
            for (int i=1;i<=ml;i++) x[i]+=y[i];
            for (int i=1;i                x[i+1]+=x[i]/10;
                x[i]%=10;
            }
       }

       void mul(int *x,int *y){
            memset(tmp,0,sizeof(tmp));
            for (int i=1;i<=ml;i++)
              for (int j=1;i+j-1<=ml;j++) tmp[i+j-1]+=x[i]*y[j];
            for (int i=1;i                tmp[i+1]+=tmp[i]/10;
                tmp[i]%=10;
            }
       }

       void dec(int *x,int *y){
            for (int i=1;i<=ml;i++) x[i]-=y[i];
            for (int i=1;i                while (x[i]<0){x[i]+=10; x[i+1]--;}
                while (x[i]>9){x[i]-=10; x[i+1]++;}
            }
       }
}Big;

void deal(int m){
     memcpy(ans[m],cf[m*(m-1)/2],sizeof(ans[m]));
     for (int i=1;i         Big.mul(ans[i],C[m-1][i-1]);
         memcpy(tmp2,tmp,sizeof(tmp));
         int q=m-i;
         Big.mul(tmp2,cf[q*(q-1)/2]);
         Big.dec(ans[m],tmp);
     }
}

void init(){
     memset(C,0,sizeof(C));
     memset(cf,0,sizeof(cf));
     C[0][0][1]=1;
     for (int i=1;i<=50;i++)
       for (int j=0;j<=i;j++){
           if (j) Big.plus(C[i][j],C[i-1][j-1]);
           Big.plus(C[i][j],C[i-1][j]);
       }
     cf[0][1]=1;
     for (int i=1;i<=1300;i++){
         for (int j=1;j<=ml;j++) cf[i][j]=cf[i-1][j]*2;
         for (int j=1;j             cf[i][j+1]+=cf[i][j]/10;
             cf[i][j]%=10;
         }
     }
     for (int i=1;i<=50;i++)
       deal(i);
}

void output(){
     int i=ml;
     while (!ans[n][i]) i–;
     for (int j=i;j>=1;j–) printf("%d",ans[n][j]);
     printf("n");
}

int main(){
    init();
    while (cin >> n && n) output();
}