[BZOJ1002](FJOI 2007) 轮状病毒

【题目描述】

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

【输入格式】

第一行有1个正整数n。

【输出格式】

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

【样例输入】

【样例输出】

【题目来源】

耒阳大世野（衡阳八中） OJ 1002

（福建省选赛2007）

【分析】

从“各原子有唯一的信息通道”不难看出，每种轮状病毒对应着轮状基的一棵生成树。一般图的生成树计数可以用Matrix-Tree 定理求解，但这里的图比较特殊，用Matrix-Tree未免有些小题大做，我们可以用组合递推的方法求解。

先设$f(n)$为n轮状基上删去一条弧得到的“缺口轮”上的生成树个数，再设$S(n) = \sum \limits_{i = 1}^n {f(i)}$. 于是就有:

$$\begin{array}{F} f(0) = f(1) = 1\\ f(n) = 2f(n-1) + \sum_{i=0}^{n-2} f(i) = f(n-1) + S(n-1) + 1 \end{array}$$

$$ans(n) = f(n) + 2\sum_{i = 1}^{n-1}f(i) = S(n) + S(n-1)$$

（这个公式我推了一上午我会说？）

考虑到n最大为100，答案会超过long long的范围，这里的状态值应用高精度类存储。

1 /**************************************************************
2     Problem: 1002
3     User: 935671154
4     Language: C++
5     Result: Accepted
6     Time:44 ms
7     Memory:2068 kb
8 ****************************************************************/
9
//Author : Asm.Def
#include <iostream>
#include <cctype>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
inline void getd(int &x){
     char c = getchar();
     bool minus = ;
     while(!isdigit(c) && c != '-')c = getchar();
     if(c == '-')minus = , c = getchar();
     x = c - '';
     while(isdigit(c = getchar()))x = x *  + c - '';
     if(minus)x = -x;
}
/*======================================================*/
const int maxn = ;

struct BigN{
     #define base 10000
     #define maxl 1000
     int A[maxl], len;
     BigN(){len = , A[] = ;}
     BigN &operator = (const BigN &x){
         len = ;
         while(len < x.len){A[len] = x.A[len]; ++len;}
         return *this;
     }
     BigN &operator = (int k){len = ;A[] = k; return *this;}
     BigN &operator += (const BigN &x){
         int i, mor = ;
         for(i = ;i < x.len || mor;++i){
             if(i < len)mor += A[i];
             if(i < x.len)mor += x.A[i];
             A[i] = mor % base;
             mor /= base;
         }
         if(i > len)len = i;
         return *this;
     }
}f[maxn], S[maxn];

inline void work(int k){
     int i;
     if(!k){printf("0\n");return;}
     f[] = , f[] = , S[] = ;
     if(k == ){printf("1\n");return;}
     for(i = ;i <= k;++i){
         f[i] = ; f[i] += f[i-]; f[i] += S[i-];
         S[i] = S[i-]; S[i] += f[i];
     }
     S[k] += S[k-];
     i = S[k].len - ;
     printf("%d", S[k].A[i]);
     while(i)
         printf("%04d", S[k].A[--i]);
     putchar('\n');
}

int main(){
     #if defined DEBUG
     freopen("test", "r", stdin);
     #endif
     int k;
     getd(k);

     work(k);

     #if defined DEBUG
     cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
     #endif
     return ;
}

高精度 + 递推

巴特西