1002: [FJOI2007]轮状病毒
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 5946 Solved: 3243
[Submit][Status][Discuss]
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
听说这题是基尔霍夫矩阵……我其实是乱搞的
在数学课上不想听，就开始想这道题，然后画了二十分钟的图……找到了前几项如下：
1 5 16 45 121 ……
然后看到了什么呢？平方！
但是5, 45怎么解释呢？我又画了n=6的图， 320，然后作出猜想，偶数项可能是某个数的平方-4，2是3^2 - 4，4是7^2 - 4……
那么底数又有什么规律呢？1, 3, 4, 7, 11, 18……
4 = 3 + 1
7 = 4 + 3
11 = 7 + 4
就是个fibonacci，只是前两项不同而已
再套上高精度，借用黄学长的板子
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rad 1000
ll n;
struct data
{int v[10005],l;data(){memset(v,0,sizeof(v));l=0;}
};
void print(data a)
{for(int i=a.l;i;i--)printf("%d",a.v[i]);printf("\n");
}
bool operator>(data a,data b)
{if(a.l>b.l)return 1;if(a.l<b.l)return 0;for(int i=a.l;i;i--)if(a.v[i]>b.v[i])return 1;else if(a.v[i]<b.v[i])return 0;return 0;
}
data operator*(data a,data b)
{data c;for(int i=1;i<=a.l;i++)for(int j=1;j<=b.l;j++)c.v[i+j-1]+=a.v[i]*b.v[j];for(int i=1;i<=a.l+b.l;i++){if(c.v[i]>=10){c.v[i+1]+=c.v[i]/10;c.v[i]%=10;}if(c.v[i])c.l=i;}return c;
}
data operator-(data a,data b)
{data c;for(int i=1;i<=a.l;i++){c.v[i]=a.v[i]-b.v[i];if(c.v[i]<0){c.v[i]+=10;a.v[i+1]--;}}c.l=a.l;while(!c.v[c.l]&&c.l)c.l--;return c;
}
data operator+(data a,data b)
{data c;c.l=max(a.l,b.l);for(int i=1;i<=c.l;i++)c.v[i]=a.v[i]+b.v[i];for(int i=1;i<=c.l;i++)if(c.v[i]>=10){c.v[i]%=10;c.v[i+1]++;}while(c.v[c.l+1])c.l++;return c;
}
data F[1001];
data ans;
signed main() {scanf("%lld", &n);F[1].v[1] = 1;F[2].v[1] = 3;F[1].l = 1;F[2].l = 1;data dec;dec.v[1] = 4; dec.l = 1;for(int i = 3; i <= n; i++) F[i] = F[i - 1] + F[i - 2];if(n & 1) ans = F[n] * F[n];else ans = F[n] * F[n] - dec;print(ans);puts("");return 0;
}