zrt中文题

orzzrt....

题意：给n个点n条边，问能形成几个无向连通图
公式：ans=Σ(k=3~n){[n^(n-k)]* (n-1)!/2(n-k)!}
推导：ans=Σ（k=3~n)(f(n,k)*h(k))
f(n,k)表示能形成的森林个数，h(k)表示能形成的环的个数
h(k)=n!/2n n!：排列的种类 n!/n:去重(123,231,312) (n!/n)/2:去重(123,321)
∴h(k)=(k-1)!/2
设g(n,k)=f(n,k)*(n-k)! (边有编号时森林的个数)
=n(n-1)n(n-2)*...*n*k
=n^(n-k)*(n-1)!/(k-1)!
∴f(n,k)=n^(n-k)*(n-1)!/[(k-1)!*(n-k)!]
∴ans=Σ(k=3~n){[n^(n-k)]* (n-1)!/2(n-k)!}
需要用到高精度

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<string>

#define MAX 10010

using namespace std;

char ans[MAX],sum[MAX];

int bigchenfa(int *sum2,int *a,int *b,int lsum,int la,int lb)

{

    int i,j,k ;

    memset(sum2,,sizeof(sum2));

    lsum=;

    for(i=;i<=la;i++)

    for(j=,lsum=i-;j<=lb;j++)

    sum2[++lsum]+=b[j]*a[i];

    for(i=;i<=lsum;i++)

    if(sum2[i]>=)

    {

        if(sum2[lsum]>=)

        lsum++;

        sum2[i+]+=sum2[i] /  ;

        sum2[i]%= ;

    }

    return lsum ;

}

void multiply(int ac)

{

    int a[MAX]={},b[MAX]={},sum2[MAX*]={} ;

      int la=,lb=,lsum=;

      int i,j;

      int b1=ac;

      la=strlen(ans);

      for(int i=,j=la-;i<=la;i++,j--) a[i]=ans[j]-'';

      while(b1>)

      {

        b[lb]=b1%;

        lb++;

        b1/=;

    }

    lb-=;

      lsum = bigchenfa(sum2,a,b,lsum,la,lb) ;

      memset(ans,,sizeof(ans));

      for(i=lsum,j=;i>=;i--,j++) ans[j]=sum2[i]+'';

}

int sum1[MAX],ans1[MAX];

void add()

{

    int lena,lenb,len;

    lena=strlen(sum);

    lenb=strlen(ans);

    len=max(lena,lenb);

    memset(sum1,,sizeof(sum1));

    memset(ans1,,sizeof(ans1));

    for(int i=lena-,j=;i>=;i--,j++)sum1[j]=sum[i]-'';

    for(int i=lenb-,j=;i>=;i--,j++)ans1[j]=ans[i]-'';

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

    {

        if(sum1[i]+ans1[i]>=) sum1[i+]++;

        sum1[i]=(sum1[i]+ans1[i])%;

    }

    if(sum1[len]!=)len++;

    memset(sum,,sizeof(sum));

    for(int i=len-,j=;i>=;i--,j++)

    {

        sum[j]=sum1[i]+'';

    }

}

void divide()

{

    int a[MAX]={},c[MAX]={};

    int i,k,d=;

    k=strlen(sum);

    for(i=;i<k;i++)

        a[i]=sum[k-i-] - '';

    for(i=k-;i>=;i--)

    {

        d=d*+a[i];

        c[i]=d/;

        d=d%;

    }

    while(c[k-]==&&k>) k--;

    for(i=k-;i>=;i--) cout<<c[i];

}

int main()

{

    int n;

    cin>>n;

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

    {

        memset(ans,,sizeof(ans));

        ans[]='';

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

        {

            multiply(n);

        }

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

        {

            multiply(i);

        }

        add();

    }

    divide();

    return ;

}

巴特西

zrt中文题

最新文章

热门文章