这道题一开始我想的是使用组合数求解……后来发现这根本不可能……
无奈之下看了dalao们的题解，有人说要用什么矩阵生成树……我也看不懂……只好看了各位dalao把DP式推出来的题解。
在1~5的时候，对应的轮状病毒的个数分别为1,5,16,45,121.可以发现奇数项全部是完全平方式，而偶数项是完全平方式-4.
我们看一下完全平方式的底数，分别是1,3,4,7,11，发现是一个变形的斐波那契数列，那么我们就直接递推就可以了。
套用一下高精度模板。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #include<set> #include<utility> #include<iostream> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; typedef pair<int,int> pr; const int INF = 1e9; const int M = 2000005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct big { int len,num[1000]; big() { len = 0; memset(num,0,sizeof(num)); } big(int p) { len = 0; while(p) num[++len] = p % 10,p /= 10; } void init(int p) { len = 0; while(p) num[++len] = p % 10,p /= 10; } big operator + (const big &g) const { big ans; int s = max(len,g.len); ans.len = s; rep(i,1,s) { ans.num[i] += num[i] + g.num[i]; if(ans.num[i] >= 10) ans.num[i] -= 10,ans.num[i+1]++; } if(ans.num[s+1]) ans.len++; return ans; } big operator - (const big &g) const { big ans; int s = max(len,g.len); ans.len = s; rep(i,1,s) ans.num[i] = num[i] - g.num[i]; rep(i,1,s) if(ans.num[i] < 0) ans.num[i+1]--,ans.num[i] += 10; if(ans.num[s+1] != 0) ans.len++; return ans; } big operator * (const big &g) const { big ans; ans.len = len + g.len; rep(i,1,len) rep(j,1,g.len) ans.num[i+j-1] += num[i] * g.num[j]; rep(i,1,ans.len) ans.num[i+1] += ans.num[i] / 10, ans.num[i] %= 10; while(ans.len > 1 && !ans.num[ans.len]) ans.len--; return ans; } void out() { per(i,len,1) printf("%d",num[i]); enter; } }; big a,b,c,f[200]; int n; int main() { f[1].init(1),f[2].init(3),b.init(4); n = read(); rep(i,3,n) f[i] = f[i-1] + f[i-2]; if(n&1) a = f[n] * f[n]; else a = f[n] * f[n] - b; a.out(); return 0; }