[FJOI2007]轮状病毒

题目描述

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

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

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

输入输出格式

输入格式：

第一行有1个正整数n。

输出格式：

将编程计算出的不同的n轮状病毒数输出

输入输出样例

输入样例#1：

3

输出样例#1：

16
其实可以用矩阵树定理来算方案数
但是没有取模，高精是必需的
实际每个矩阵都是相似的
1 5 16 45 121 320
归纳找到规律：
f[i]=3*f[i-1]-f[i-2]+2
证明
还有DP和高精度矩阵树(太毒了找不到)的做法

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 struct Num

 {

   int len;

   int a[];

 }f[];

 int n;

 Num chen(Num a,int k)

 {

   int i;

     Num ans;

     for (i=;i<=a.len;i++)

       ans.a[i]=a.a[i]*k;

     for (i=;i<=a.len;i++)

       ans.a[i+]+=ans.a[i]/,ans.a[i]%=;

     ans.len=a.len;

     while (ans.a[ans.len+])

       {

     ans.len++;

     ans.a[ans.len+]+=ans.a[ans.len]/;

     ans.a[ans.len]%=;

       }

     return ans;

 }

 Num add(Num a,int k)

 {

   int i;

     Num ans;

     for (i=;i<=a.len;i++)

       ans.a[i]=a.a[i];

     ans.len=a.len;

     ans.a[]+=k;

     for (i=;i<=a.len;i++)

       ans.a[i+]+=ans.a[i]/,ans.a[i]%=;

     while (ans.a[ans.len+])

       {

     ans.len++;

     ans.a[ans.len+]+=ans.a[ans.len]/;

     ans.a[ans.len]%=;

       }

     return ans;

 }

 Num jian(Num a,Num b)

 {

   int i;

     Num ans;

     ans.len=a.len;

     for (i=;i<=b.len;i++)

       ans.a[i]=a.a[i]-b.a[i];

     for (i=b.len+;i<=a.len;i++)

       ans.a[i]=a.a[i];

     for (i=;i<=a.len;i++)

       {

     if (ans.a[i]<) ans.a[i]+=,ans.a[i+]-=;

       }

     while (ans.a[ans.len]&&ans.len>) ans.len--;

     return ans;

 }

 int main()

 {int i,j;

   cin>>n;

   f[].a[]=;f[].len=;

   f[].a[]=;f[].len=;

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

     {

       f[i]=chen(f[i-],);

       f[i]=jian(f[i],f[i-]);

       f[i]=add(f[i],);

     }

   for (i=f[n].len;i>=;i--)

     printf("%d",f[n].a[i]);

 }