3003. Strange Mushroom

Description

米莉是宇宙第一的厨师(自称), 最近在宇宙中寻找食材时发现了一种奇怪的蘑菇. 这种蘑菇每天都会固定分裂一次, 长度为x的蘑菇会分裂成两个长度分别为x-1和x+1的蘑菇, 但是长度为0的蘑菇是不存在的, 所以长度为1的蘑菇只能生长成长度为2的蘑菇. 现在米莉第一天有一个长度为2的蘑菇, 她想知道第n(1 <= n <= 10000)天她有多少个蘑菇.

比如: 第2天分裂成了2个蘑菇{M11, M31}(这里用Mi代表长度为i的蘑菇). 第3天长度为1的蘑菇成长为长度2, 长度为3的蘑菇分裂为两个, 于是有{M22, M41}. 第4天, 则为{M12, M33, M5*1}.

Input Format

一行, 一个整数n, 意义如上所述.

Output Format

一行, 一个整数, 代表米莉在第n天时拥有的蘑菇数量.

Sample Input

Sample Output

Hint

答案可能较大, 注意使用高精度保存及计算. 数据范围: 对于70%的测试点, n <= 30. 对于90%的测试点, n <= 100.

1.模拟法:

　　简单的递归方程，超时。主要是因为其中的M[i]就需要高精度了，而不只是结果需要高精度。

2.组合数学:

　　首先可以把整个过程的状态的树画出来，进行观察。。

|   day1:1       | |1| | | | | ||   day2:2       |1| |1| | | | ||   day3:3       | |2| |1| | | ||   day4:6       |2| |3| |1| | ||   day5:10      | |5| |4| |1| ||   day6:20      |5| |9| |5| |1| 看图发现每个点的数是左上和右上的和,想到杨辉三角，先找到数列 1 2 3 6 10 20 对比杨辉三角 找到规律: n行的和就是杨辉三角第n行中间的(中间偏左)d (其实拿这几个数百度一下就知道规律了...一会解释为什么会是这个规律) 所以就是组合数C(n,[n/2]) 不考虑高精度的问题 用python来表示过程:

n = int(input())m = n//2;a = m+1;b = 1;ans = 1;for i in range(n-m):    ans = ans * a;    ans = ans // b;    a+=1;    b+=1;print(ans)

C++ 完整代码如下:

#include 
      
         #include 
       
          #include 
        
         #include 
         
           #define MaxN 10000 using namespace std;struct bign{       int len,s[MaxN];// 定义成员变量       //定义构造函数 C++专属       bign()      {          len=1;          memset(s,0,sizeof(s));      }      //定义对于char数组的=运算法则       bign operator = (const char* num)    {          len = strlen(num);          for(int i=0;i
          
           < b.len ;i++)          {              res.s[res.len++] = s[i]-b.s[i];        }          //补头部        for (int i = b.len; i < len; ++i)        {            res.s[res.len++] = s[i];        }        //补负数        for (int i = 0; i < res.len ; ++i)        {            if(res.s[i]<0){                res.s[i]+=10;                res.s[i+1]--;            }        }         return res;      }     //定义乘法       bign operator * (const bign& b) const //返回一个bign的运算结果       {           bign res;          res.len=0;          for(int i=0;i < b.len;i++)          {              int g=0;              bign tem;               tem.len=0;              for(int k=0;k
           
            = i ; --j) { tmp.s[j] = tmp.s[j-i]; } for (int j = 0; j < i; ++j) { tmp.s[j] = 0; } return tmp; } //高精度乘以低精度 bign operator * (int b) //返回一个bign的运算结果 { bign res; res = 0; for (int i = 0; i < len; ++i) { bign tmp = s[i] * b; //把tmp整体向右移i位 左边用0补齐 //tmp.moveRight(i); res = res + tmp.moveRight(i); } return res; } void MultiSmallInt(int b){ s[0] = s[0] * b; for(int i = 1; i < len; ++i) { s[i] *= b; s[i] += s[i-1]/10;//进位 s[i-1] %= 10; } //如果最高位大于9 说明还要进1位 while(s[len-1] > 9){ s[len] = s[len-1]/10; s[len-1] %= 10; len++; } } //定义大数除以小数 bign operator / (int b){ //为了获取b的位数 转换其为bign bign btmp = b; bign result = 0; char ans[MaxN]; int ans_len = 0; int b_len = btmp.len; int toCheck=0;//从前向后从this_tmp中取出b_len位去比较 int cur = len-1;//第一次取的起点 for (int i = 0; i < b_len; ++i) { toCheck += s[cur--] * pow(10,b_len-1-i); } int tmp_res = toCheck / b; if(toCheck / b >0){ //result = tmp_res.moveRight(len-b_len); ans[ans_len++] = tmp_res+'0'; } int remain = toCheck % b; while(cur>=0){ toCheck = remain * 10 + s[cur--]; tmp_res = toCheck / b; remain = toCheck %b; //result = result + tmp_res.moveRight(cur+1); ans[ans_len++] = tmp_res +'0'; } ans[ans_len] = '\0'; result = ans; return result; } //定义比较符号 bool operator < (const bign &b )const { if(len!=b.len) return len
            
             =0;i--) { if(s[i]!=b.s[i]) return s[i]
             
               (const bign& b)const { return b<*this;} bool operator >= (const bign& b)const { return !(b>*this);} bool operator <= (const bign& b)const { return !(*this>b);} bool operator != (const bign& b)const { return (*this
              
               b);} bool operator == (const bign& b)const { return !(*this != b);} } ;//";" 太重要了 //为bign定义<
               <和>
                >运算符 必须在外部 istream& operator >>(istream &in,bign& x)//&的位置有关系么? { string s; in>>s;//in表示输入的流 x=s.c_str();//把string 转换为char* return in; } ostream& operator <<(ostream &out,const bign& x)//此处要求x为const的 { out<
                
                 >n; int m = n/2; int a = m+1; int b = 1; bign ans = 1; for (int i = 0; i < n-m; ++i) { ans.MultiSmallInt(a); ans = ans / b; a++; b++; } cout<
                 
                  <

View Code

C++代码里用了自己攒的bign类，所以代码比较多，同一种功能的版本也比较多，有很多可以优化的地方，比如高精度除以低精度。

以下来证明为何ans就是C(n,[n/2])

首先，把那个三角形当做一个图来看，每一个点的数字表示的含义就是从顶点走到该点的路径的数目。

路径数目可以转换为序列数目，从定点0开始向左为-1 向右为+1

所以路径的数目也就等价于

由-1和+1组成的，长度为n-1的，任意前k项和都大于等于-1的个数。

解释：

1.因为到第n天，一共经历了n-1次转换的过程。

2.如果任何时刻出现了序列前k项的和为-2，则表示该路径经过比-1（也就是第一个位置）还要左的地方，这是不允许的。

接下来进行分析一个无效序列的特点:

假设这个序列含有m个-1（有C(n-1,m)种摆放方法）

如果这n-1个数组成的序列是无效的，说明有一个最小的k使得前k项和为-2，

也就是有 [k/2]-1 个1 和 [k/2]+1个-1

如果我们把这k个数反向也就是1变为-1 -1变为1 则得到了一个含有m-2个-1的序列

这种变换是一对一的(因为反向的特性) 所以换一种说法就是

在一个含有m个-1的序列的集合里，失效的序列的个数正好等于由m-2个-1的序列组成的集合的大小

数学语言就是

C(n-1,m) - C(n-1,m-2)

而遍历m从0到[(n-1)/2]+1 = [n/2]，求和。可以得到

Ans = C(n-1,0) + C(n-1,1) + [C(n-1,2)-C(n-1,0)]+[C(n-1,3)-C(n-1,1)] + [C(n-1,4)-C(n-1,2)] + ....+[C(n-1,[n/2])-C(n-1,[n/2]-2)]

化简得到

Ans = C(n-1,[n/2]-1) + C(n-1,[n/2])

　　 = C(n,[n/2])

转载于:https://www.cnblogs.com/yuchenlin/p/sjtu_oj_3003.html

你可能感兴趣的文章