「CF630C」Lucky Numbers

Portal

Portal2: Luogu

Description

The numbers of all offices in the new building of the Tax Office of IT City will have lucky numbers.

Lucky number is a number that consists of digits (7) and (8) only. Find the maximum number of offices in the new building of the Tax Office given that a door-plate can hold a number not longer than (n) digits.

Input

The only line of input contains one integer (n (1 le n le 55)) — the maximum length of a number that a door-plate can hold.

Output

Output one integer — the maximum number of offices, than can have unique lucky numbers not longer than (n) digits.

Sample Input

Sample Output

Solution

题目要我们构造(1 sim n)位由(7, 8)的数的个数。我们先来找一找规律：

位数为(1)时：有(7, 8)，共(2 imes 2 ^ 0 = 2)种；

位数为(2)时：有(77, 78, 87, 88)，共(2 imes 2 ^ 1 = 4)种；

位数为(3)时：有(777, 778, 787, 788, 877, 878, 887, 888)共(2 imes 2 ^ 2 = 8)种；

(cdots cdots)

所以，位数是(n)的总个数是(2 imes 2 ^ {n - 1})；

那么位数为(1 sim n)的总个数为

[egin{aligned} sum^{n}_{i = 1}{2 imes 2 ^ {i - 1}} & = 2 imes sum^{n}_{i = 1}{2 ^ {i - 1}} \\ & = 2 imes (2 ^ {n} - 2) \\ & = 2 ^ {n + 1} - 2end{aligned} ]

于是就解决了。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

typedef long long LL;
LL n;
inline LL power(LL x, LL y) {//求x的y次方
    LL ret = 1;
    for (LL i = 1; i <= y; i++)
        ret *= x;
    return ret;
}
int main() {
    scanf("%lld", &n);
    printf("%lld
", power(2, n + 1) - 2);//推出来的公式
    return 0;
}