[关闭]
@zzzc18 2017-05-10T12:18:01.000000Z 字数 1301 阅读 748

bzoj 1002(递推关系)

bzoj


bzoj 1002

Description

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

1

N轮状病毒的产生规律是在一个N轮状基中删去若干条边,使得各原子之间有唯一的信息通道,例如共有16个不同的3轮状病毒,如下图所示

2

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

Input

第一行有1个正整数n

Output

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

Sample Input

3

Sample Output

16

solve

我们只要选择连在一起有几个就行了,相当于把n分成很多段连续的圆弧

可以由递推关系来解决
以下面n=4为例

3

上图为一种可行解,弧上的实、虚线可互相替换,十字上的实、虚线可互相替换
有4*4种方法

4

上图,弧上n=3的点集再连上4的,有1*f(3)种的情况

5

上图,相连的是同一点集,显然有2*f(2)种

同理,还有3*f(1)种


于是,有了f(4)=4*4+1*f(3)+2*f(2)+3*f(1)

同样的
f(i)=i*i+1*f(i-1)+2*f(i-2)+3*f(i-3)+...+(n-1)*f(1)


这时再将上式改为递推式
f(i)=2*i-1 + f(1) + f(2) + ... + f(i-1) + f(i-1)

怎么来的呢?
还以n=4为例

当前式 常数 f(1) f(2) f(3)
f(1) 1*2-1 0 0 0
f(2) 2*2-1 1 0 0
f(3) 3*2-1 1 1 0
f(4) 4*2-1 1 1 1
ANS(4)(求和) 4^2 3 2 1

然后就可以搞事情了,递推式推到底就AC了
注意高精

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #define MAXN 1000
  5. using namespace std;
  6. int n;
  7. struct BIGNUM{
  8. int num[MAXN];
  9. int len;
  10. BIGNUM(){
  11. memset(num,0,sizeof(num));
  12. len=1;
  13. }
  14. }SUM,f,ANS;
  15. BIGNUM ADD(const BIGNUM &x,const BIGNUM &y){
  16. int len=max(x.len,y.len);
  17. int i;
  18. BIGNUM tmp;
  19. for(i=0;i<=len;i++){
  20. tmp.num[i]+=x.num[i]+y.num[i];
  21. tmp.num[i+1]=tmp.num[i]/10;
  22. tmp.num[i]%=10;
  23. }
  24. if(tmp.num[len])
  25. len++;
  26. tmp.len=len;
  27. return tmp;
  28. }
  29. void PRINT(const BIGNUM & x){
  30. int i;
  31. for(i=x.len-1;i>=0;i--)
  32. printf("%d",x.num[i]);
  33. }
  34. void solve(){
  35. int i;
  36. for(i=1;i<=n;i++){
  37. f.num[0]+=i*2-1;
  38. f=ADD(f,SUM);
  39. SUM=ADD(f,SUM);
  40. ANS=f;
  41. }
  42. }
  43. int main(){
  44. scanf("%d",&n);
  45. solve();
  46. PRINT(ANS);
  47. return 0;
  48. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注