Description
輪狀病毒有很多變種，所有輪狀病毒的變種都是從一個(gè)輪狀基產(chǎn)生的。一個(gè)N輪狀基由圓環(huán)上N個(gè)不同的基原子和圓心處一個(gè)核原子構(gòu)成的，2個(gè)原子之間的邊表示這2個(gè)原子之間的信息通道。如下圖所示

N輪狀病毒的產(chǎn)生規(guī)律是在一個(gè)N輪狀基中刪去若干條邊，使得各原子之間有唯一的信息通道，例如共有16個(gè)不同的3輪狀病毒，如下圖所示

現(xiàn)給定n(N<=100)，編程計(jì)算有多少個(gè)不同的n輪狀病毒

Input
第一行有1個(gè)正整數(shù)n

Output
計(jì)算出的不同的n輪狀病毒數(shù)輸出

Sample Input
3

Sample Output
16

---

基爾霍夫矩陣？？貌似是的，但是我不會(huì)……
所以，打表出奇跡！
我們通過耗費(fèi)大量的時(shí)間手動(dòng)推出前8個(gè)輪狀病毒的個(gè)數(shù)
1,5,16,45,121,320,841,2205,...
然后，找規(guī)律！
通過數(shù)學(xué)知識(shí)與大膽猜想，我們推出遞推式為\(f[i]=3\times f[i-1]-f[i-2]+2\)
大膽交一發(fā)，WA掉……遞推式錯(cuò)了？不，沒開高精度……
加上高精度這題就可以愉快的A掉啦~

/*program from Wolfycz*/ #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define inf 0x7f7f7f7f using namespace std; typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; inline int read(){int x=0,f=1;char ch=getchar();for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';return x*f; } inline void print(int x){if (x>=10) print(x/10);putchar(x%10+'0'); } const int base=1e4; const int digit=4; const int maxn=15; const int N=1e2; struct Bignum{int v[maxn],len;Bignum(){memset(v,0,sizeof(v)),len=1;}void write(){printf("%d",v[len-1]);for (int i=len-2;~i;i--) printf("%0*d",digit,v[i]);putchar('\n');} }f[N+10]; Bignum operator +(const Bignum &x,const int &y){Bignum z;z.len=x.len; z.v[0]=y;for (int i=0;i<=z.len;i++) z.v[i]+=x.v[i],z.v[i+1]+=z.v[i]/base,z.v[i]%=base;while (z.v[z.len]) z.v[z.len+1]=z.v[z.len]/base,z.v[z.len]%=base,z.len++;return z; } Bignum operator -(const Bignum &x,const Bignum &y){Bignum z;z.len=x.len;for (int i=0;i<=z.len;i++){z.v[i]+=x.v[i]-y.v[i];if (z.v[i]<0) z.v[i+1]--,z.v[i]+=base;}while (!z.v[z.len-1]&&z.len>1) z.len--;return z; } Bignum operator *(const Bignum &x,const int &y){Bignum z;z.len=x.len;for (int i=0;i<=z.len;i++) z.v[i]+=x.v[i]*y,z.v[i+1]+=z.v[i]/base,z.v[i]%=base;while (z.v[z.len]) z.v[z.len+1]=z.v[z.len]/base,z.v[z.len]%=base,z.len++;return z; } int main(){int n=read();f[1].v[0]=1;for (int i=2;i<=n;i++) f[i]=f[i-1]*3-f[i-2]+2;f[n].write();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Wolfycz/p/9141910.html

總結(jié)

以上是生活随笔為你收集整理的[FJOI2007]轮状病毒的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。