「BZOJ1002」[FJOI2007] 轮状病毒（基尔霍夫矩阵）

本文主要是介绍「BZOJ1002」[FJOI2007] 轮状病毒（基尔霍夫矩阵），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

现给定n(N<=100)，编程计算有多少个不同的n轮状病毒
Input
　　第一行有1个正整数n

Output
　　计算出的不同的n轮状病毒数输出

Sample Input
3
Sample Output
16
Hint
Source

f[i] = f[i - 1] X 3 - f[i - 2] + 2

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;const int maxn = 1000;struct bign{int d[maxn], len;void clean() { while(len > 1 && !d[len-1]) len--; }bign()             { memset(d, 0, sizeof(d)); len = 1; }bign(int num)     { *this = num; }bign(char* num) { *this = num; }bign operator = (const char* num){memset(d, 0, sizeof(d)); len = strlen(num);for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';clean();return *this;}bign operator = (int num){char s[20]; sprintf(s, "%d", num);*this = s;return *this;}bign operator + (const bign& b){bign c = *this; int i;for (i = 0; i < b.len; i++){c.d[i] += b.d[i];if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;}while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;c.len = max(len, b.len);if (c.d[i] && c.len <= i) c.len = i+1;return c;}bign operator - (const bign& b){bign c = *this; int i;for (i = 0; i < b.len; i++){c.d[i] -= b.d[i];if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;}while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;c.clean();return c;}bign operator * (const bign& b)const{int i, j; bign c; c.len = len + b.len;for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)c.d[i+j] += d[i] * b.d[j];for(i = 0; i < c.len-1; i++)c.d[i+1] += c.d[i]/10, c.d[i] %= 10;c.clean();return c;}bign operator / (const bign& b){int i, j;bign c = *this, a = 0;for (i = len - 1; i >= 0; i--){a = a*10 + d[i];for (j = 0; j < 10; j++) if (a < b*(j+1)) break;c.d[i] = j;a = a - b*j;}c.clean();return c;}bign operator % (const bign& b){int i, j;bign a = 0;for (i = len - 1; i >= 0; i--){a = a*10 + d[i];for (j = 0; j < 10; j++) if (a < b*(j+1)) break;a = a - b*j;}return a;}bign operator += (const bign& b){*this = *this + b;return *this;}bool operator <(const bign& b) const{if(len != b.len) return len < b.len;for(int i = len-1; i >= 0; i--)if(d[i] != b.d[i]) return d[i] < b.d[i];return false;}bool operator >(const bign& b) const{return b < *this;}bool operator<=(const bign& b) const{return !(b < *this);}bool operator>=(const bign& b) const{return !(*this < b);}bool operator!=(const bign& b) const{return b < *this || *this < b;}bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}string str() const{char s[maxn]={};for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';return s;}
};istream& operator >> (istream& in, bign& x)
{string s;in >> s;x = s.c_str();return in;
}ostream& operator << (ostream& out, const bign& x)
{out << x.str();return out;
}bign c[55][55];void ready()
{for(int i=0;i<=50;i++)c[i][0]=1;for(int i=1;i<=50;i++){for(int j=1;j<=i;j++){c[i][j]=c[i-1][j-1]+c[i-1][j];}}
}bign f[1005];
int main()
{f[2] = 5;f[1] = 1;int n;cin >> n;for(int i = 3;i <= n;i++){f[i] = f[i - 1] * 3 - f[i - 2] + 2;}cout << f[n] << endl;return 0;
}