猫王相亲

题目大意

给定一个金字塔，从第二层起每一层中的数均等于下面一层左右的两个数之和。给定正整数$n（nle10^5）$，金字塔的第一层为$1$到$n$从小到大排列而成的数列，求金字塔顶的数。

数列特征

从已知条件只能知道第一行为$1～N$的等差数列。

假设第一行中某三个连续的数字为$a-d, a, a+d$，（$d$为等差数列的公差，此处$d=1$），那么第二行对应的数为$2a-d,2a+d$，相差$2d$，由于$a$的一般性，所以对于第二行任意两项的差都为$2d$，以此类推每一行的数列都组成等差数列，第$i$行数列的公差为$d_i=2^{i-1}$。

首项的值

推导出公差之后，只要知道数列的首项，就能很快得出整个数列，而最后求的是金字塔顶的数，就相当于最顶上一层的首项，所以设$F_i$为第$i$层的首项。

根据每个数等于下一层左右两个数的和，那么就有
$$egin{array}\F_i&=&F_{i-1}+(F_{i-1}+d_{i-1}) \&=&2F_{i-1}+2^{i-1} end{array}$$

代入$n$，则有

$$egin{array} \ F_n&=&2F_{n-1}+2^{n-2} \ &=&2(2F_{n-2}+2^{n-3})+2^{n-2}&=&4F_{n-2}+2cdot 2^{n-2} \ &=&4(2F_{n-3}+2^{n-4})+2^{n-2}&=&8F_{n-3}+3cdot 2^{n-2} \&=&……\ _{第i行}&=&2^iF_{n-i}+icdot 2^{n-2} \ _{当i=n-1时}&=&2^{n-1}F_1+(n-1)cdot 2^{n-2} \ &=&(n+1)cdot 2^{n-2} end{array}$$

所以只要高精度加个快速幂就好了。

代码

  1 #include <cstdio>
  2 #include <cstring>
  3 
  4 struct BigNumber
  5 {
  6     static const long long BASE = 1000000000;
  7     static const int BASEDIGS = 9;
  8     
  9     int ndigs;
 10     long long *digs;
 11     
 12     void init(int n, const long long *d)
 13     {
 14         while (n > 0 && d[n - 1] == 0)
 15             --n;
 16         ndigs = n;
 17         digs = new long long[n];
 18         for (int i = 0; i < n; ++i)
 19             digs[i] = d[i];
 20     }
 21     
 22     BigNumber(int n, const long long *d)
 23     {
 24         init(n, d);
 25     }
 26     
 27     BigNumber(long long x = 0)
 28     {
 29         long long d[2];
 30         d[0] = x % BASE;
 31         d[1] = x / BASE;
 32         init(2, d);
 33     }
 34     
 35     BigNumber operator *(const BigNumber &a) const
 36     {
 37         int n = ndigs + a.ndigs;
 38         long long d[n], p;
 39         for (int i = 0; i < n; i++)
 40             d[i] = 0;
 41         for (int i = 0; i < ndigs; i++)
 42         {
 43             p = 0;
 44             for (int j = 0; j < a.ndigs; j++)
 45             {
 46                 long long v = digs[i] * a.digs[j];
 47                 long long v1 = v / BASE, v0 = v % BASE;
 48                 d[i + j] += v0 + p;
 49                 p = v1 + d[i + j] / BASE;
 50                 d[i + j] %= BASE;
 51             }
 52             for(int j = i + a.ndigs; p > 0; ++j)
 53             {
 54                 d[j] += p;
 55                 p = d[j] / BASE;
 56                 d[j] %= BASE;
 57             }
 58         }
 59         return BigNumber(n, d);
 60     }
 61 
 62     BigNumber operator *(long long x) const
 63     {
 64         int n = ndigs + 1;
 65         long long d[n];
 66         long long a = 0;
 67         for (int i = 0; i < ndigs; i++)
 68         {
 69             a += digs[i] * x;
 70             d[i] = a % BASE;
 71             a /= BASE;
 72         }
 73         d[ndigs] = a;
 74         return BigNumber(n, d);
 75     }
 76 
 77     void write() const
 78     {
 79         if (ndigs == 0) printf("0");
 80         else
 81         {
 82             printf("%lld", digs[ndigs - 1]);
 83             for (int i = ndigs - 2; i >= 0; i--)
 84                 printf("%0*lld", BASEDIGS, digs[i]);
 85         }
 86     }
 87 };
 88 
 89 int n;
 90 
 91 BigNumber pow(BigNumber x, int p)
 92 {
 93     if (p == 0) return BigNumber(1);
 94     if (p == 1) return x;
 95     if (p == 2) return x * x;
 96     if (p & 1) return pow(pow(x, p / 2), 2) * x;
 97     return pow(pow(x, p / 2), 2);
 98 }
 99 
100 int main()
101 {
102     scanf("%d", &n);
103     if (n == 1) printf("1");
104     else (pow(BigNumber(2), n - 2) * (n + 1)).write();
105 }