[BZOJ1002](FJOI 2007) 轮状病毒

时间:2022-05-19 14:08:47

【题目描述】

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

[BZOJ1002](FJOI 2007) 轮状病毒

【输入格式】

第一行有1个正整数n。

【输出格式】

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

【样例输入】

3

【样例输出】

16

【题目来源】

耒阳大世野(衡阳八中) 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的范围,这里的状态值应用高精度类存储。

[BZOJ1002](FJOI 2007) 轮状病毒[BZOJ1002](FJOI 2007) 轮状病毒
 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 ;
 }

高精度 + 递推

[BZOJ1002](FJOI 2007) 轮状病毒的更多相关文章

  1. BZOJ 1002 FJOI 2007 轮状病毒 暴力&plus;找规律&plus;高精度

    题目大意: 思路:基尔霍夫矩阵求生成树个数,不会. 可是能够暴力打表.(我才不会说我调试force调试了20分钟... CODE(force.cc): #include <cstdio> ...

  2. 【BZOJ1002】&lbrack;ZJOI2006&rsqb;轮状病毒

    [BZOJ1002]轮状病毒 题面 bzoj 题解 统计个数显然直接矩阵树定理,找规律截这里 打标如下: #include <iostream> #include <cstdlib& ...

  3. 【BZOJ1002】&lbrack;FJOI2007&rsqb;轮状病毒 递推&plus;高精度

    Description 给定n(N<=100),编程计算有多少个不同的n轮状病毒. Input 第一行有1个正整数n. Output 将编程计算出的不同的n轮状病毒数输出 Sample Inpu ...

  4. 【bzoj1002】&lbrack;FJOI2007&rsqb;轮状病毒

    1002: [FJOI2007]轮状病毒 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 4381  Solved: 2393[Submit][Statu ...

  5. 【bzoj1002】&lbrack;FJOI2007&rsqb;轮状病毒 矩阵树定理&plus;高精度

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

  6. BZOJ 1002 &lbrack; FJOI 2007 &rsqb;

    -------------------------萌萌哒分割线------------------------- 题目很容易看懂,数据范围也不大.当然可以卡过暴力的人了. 在n=1时很明显是一种,如下 ...

  7. bzoj1002:&lbrack;FJOI2007&rsqb;轮状病毒

    思路:一道很裸的生成树计数问题,然而要高精度,而且听说直接行列式求值会被卡精度,所以可以模拟行列式求值的过程得到递推公式:f[i]=3*f[i-1]-f[i-2]+2,证明详见vfk博客: http: ...

  8. 【bzoj1002】 &lbrack;FJOI2007&rsqb;轮状病毒DP

    递推+环状特殊处理+高精度   #include<algorithm> #include<iostream> #include<cstdlib> #include& ...

  9. BZOJ第一页刷题计划

    BZOJ第一页刷题计划 已完成:67 / 90 [BZOJ1000]A+B Problem:A+B: [BZOJ1001][BeiJing2006]狼抓兔子:最小割: [BZOJ1002][FJOI2 ...

随机推荐

  1. BZOJ1036——树的统计count

    1.题目大意:给你一棵树,有三种操作 1>qmax,询问u到v中间点权的最大值 2>qsum,询问u到v中间点权和 3>change,把u这个节点的权值改为v 2.分析:树链剖分的裸 ...

  2. Asp&period;net MVC 视图(三)

    Html辅助方法(HtmlHelper类) 可以通过视图的Html属性调用HTML辅助方法,也可以通过Url属性调用URL辅助方法,还可以通过Ajax属性调用Ajax辅助方法. 在控制器中也存在Url ...

  3. OC基础&lpar;21&rpar;

    Foundation框架介绍 NSString基本概念 字符串读写 字符串比较 字符串搜索 字符串截取 字符串替换 字符串与路径 字符串与基本数据类型转换 *:first-child { margin ...

  4. 【BZOJ 1821】 &lbrack;JSOI2010&rsqb;Group 部落划分 Group

    Description 聪聪研究发现,荒岛野人总是过着群居的生活,但是,并不是整个荒岛上的所有野人都属于同一个部落,野人们总是拉帮结派形成属于自己的部落,不同的部落之间则经常发生争斗.只是,这一切都成 ...

  5. SFTP上传下载&lpar;C&num;&rpar;

    sftp是ftp协议的升级版本,是牺牲上传速度为代价,换取安全性能,本人开始尝试使用Tamir.SharpSSH.dll但它对新版本的openssh 不支持,所有采用Ssh.Net方式 需要依赖:Re ...

  6. 从最大似然到EM算法浅解

    从最大似然到EM算法浅解 zouxy09@qq.com http://blog.csdn.net/zouxy09 机器学习十大算法之中的一个:EM算法.能评得上十大之中的一个,让人听起来认为挺NB的. ...

  7. iosiOStextView实现文字高度自适应

    跟为textView设置提示性文字一样   需要在textView的代理方法中实现如下 如有偏差  请谅解 定义UITextView,实现UITextViewDelegate: -(UITextVie ...

  8. Python--urllib3库详解1

    Python--urllib3库详解1 Urllib3是一个功能强大,条理清晰,用于HTTP客户端的Python库,许多Python的原生系统已经开始使用urllib3.Urllib3提供了很多pyt ...

  9. C&num;程序编写规范

    代码书写规则 1.尽量使用接口,然后使用类实现接口,提高程序的灵活性. 2.一行不要超过80个字符. 3.尽量不要手工更改计算机生成的代码,若必须要改,一定要改为和计算机生成的代码风格一样. 4.关键 ...

  10. 用powermock 方法中new对象

    在单元测试中有时需要对方法体内new出来的对象进行方法隔离,powermock提供了这个功能,下面是一个段样例代码: UserBean user = mock(UserBean.class, RETU ...