bzoj1002: [FJOI2007]轮状病毒生成树计数

　轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子
和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示

　　N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不
同的3轮状病毒，如下图所示

　　现给定n(N<=100)，编程计算有多少个不同的n轮状病毒

裸的生成树计数，需要高精，同时需要特判2的重边情况

/**************************************************************

    Problem: 1002

    User: walfy

    Language: Java

    Result: Accepted

    Time:1700 ms

    Memory:24832 kb

****************************************************************/

import java.awt.List;

import java.math.BigInteger;

import java.sql.Date;

import java.util.*;

import java.util.Map.Entry;

import javax.swing.text.html.HTMLDocument.Iterator;

public class Main {

    static BigInteger [][] A = new BigInteger [100+10][100+10];

    static BigInteger [] D = new BigInteger [100+10];

    static void cal(int n)

    {

        BigInteger ans=BigInteger.valueOf(1);

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

        {

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

            {

                while(!A[j][i].equals(BigInteger.valueOf(0))){

                    BigInteger t=A[i][i].divide(A[j][i]);

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

                        A[i][k]=A[i][k].subtract(A[j][k].multiply(t));

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

                    {

                        BigInteger te=A[i][k];

                        A[i][k]=A[j][k];

                        A[j][k]=te;

                    }

                    ans=ans.negate();

                }

            }

            if(A[i][i]==BigInteger.valueOf(0))

            {

                System.out.println(0);

                return ;

            }

            ans=ans.multiply(A[i][i]);

        }

        if(ans.compareTo(BigInteger.valueOf(0))<0)ans=ans.negate();

        System.out.println(ans);

    }

    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);

        int n = cin.nextInt();n++;

        if(n==3)

        {

            System.out.println("5");

            return ;

        }

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

        {

            D[i]=BigInteger.valueOf(0);

            for(int j=1;j<=n;j++)

                A[i][j]=BigInteger.valueOf(0);

        }

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

        {

            if(i==n)

            {

                A[n][2]=BigInteger.valueOf(1);

                A[2][n]=BigInteger.valueOf(1);

            }

            else

            {

                A[i][i+1]=BigInteger.valueOf(1);

                A[i+1][i]=BigInteger.valueOf(1);

            }

            A[1][i]=BigInteger.valueOf(1);

            A[i][1]=BigInteger.valueOf(1);

        }

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

        {

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

            {

                if(A[i][j].compareTo(BigInteger.ZERO)!=0)

                {

                    D[i]=D[i].add(BigInteger.ONE);

                    D[j]=D[j].add(BigInteger.ONE);

                }

            }

        }

//      for(int i=1;i<=n;i++)System.out.println(D[i]);

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

        {

            for(int j=1;j<=n;j++)

            {

                if(i==j)A[i][j]=D[i];

                else A[i][j]=A[i][j].negate();

            }

        }

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

//      {

//          for(int j=1;j<=n;j++)

//              System.out.print(A[i][j]+" ");

//          System.out.println();

//      }

        cal(n);

    }

}

巴特西

bzoj1002: [FJOI2007]轮状病毒生成树计数

最新文章

热门文章

巴特西

bzoj1002: [FJOI2007]轮状病毒 生成树计数

最新文章

热门文章

bzoj1002: [FJOI2007]轮状病毒生成树计数