首页 > 代码库 > BZOJ 1002 轮状病毒(生成树个数)

BZOJ 1002 轮状病毒(生成树个数)

2024-07-09 00:16:59   219人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1002

题意：求下面这种造型的生成树的个数。


思路：生成树的个数可以用那个矩阵A：A[i][i]等于i的度数，A[i][j]等于i到j的边数的相反数。那么A的任意一个n-1阶的行列式（就是删掉任意一行一列）就是生成树的个数。但是这里有一个递推公式，暴力完前几项可以找出这个,f[n]=3*f[n-1]-f[n-2]+2。

 

import java.util.*;import java.text.*;import java.math.*;public class Main{     public static void PR(String s){        System.out.println(s);    }        public static void PR(int x)    {        System.out.println(x);    }          public static void PR(BigInteger x)    {        System.out.println(x);    }        public static void PR(double s)    {        java.text.DecimalFormat d=new java.text.DecimalFormat("#.000000");        System.out.println(d.format(s));    }            static BigInteger a,b,c;    static int n;               public static void main(String[] args){                Scanner S=new Scanner(System.in);        while(S.hasNext())        {            n=S.nextInt();            a=BigInteger.ONE;            b=BigInteger.valueOf(5);            int i;            if(n==1) PR(a);            else if(n==2) PR(b);            else            {                for(i=3;i<=n;i++)                 {                    c=b.multiply(BigInteger.valueOf(3));                    c=c.subtract(a).add(BigInteger.valueOf(2));                    a=b;                    b=c;                }                PR(c);            }        }    }}

 

 

 


联系
我们