我们称一个十进制正整数是幸运数当且仅当它只由数字4和7构成,现在给出一个整数n,你需要计算有多少个不大于n的运行数。由于答案可能非常大,你只需要输出答案除于10^9 + 7后的余数。
第一行包含一个数n。1≤n≤10^1000000
输出对应的答案。
125 21857711 |
6 254 |
输入使用字符串str来存储。使用递归来写,先写出递归表达式。
每次考虑最高位与7和4的大小关系,当当前最高位大于7,则后面可以选择7或者4,即有2^n个数,如果最高位为0次高位部位0时,可以有2^(n - 1)个幸运数;当当前最高位和次高位都为0,有2^(n - 2)个幸运数,以此类推。故f(n) = 2^(n + 1) - 1 str[n] > ‘7’;
当最高位等于7时,如果最高位选7,则有f(n - 1)个幸运数,如果最高位选4,有2^(n - 1)个运行数,当最高位为0且次高位不为0时,有2^(n - 1)个运行数,当最高位为0且次高位也为0,但次次高位不为0时,有2^(n - 2)个幸运数,以此类推。f(n) = f(n - 1) + 3 * ^(n - 1);
然后依次考虑最高位str[n] < 7 && str[n] > 4,str[n] == 4,str[n] < 4的情况。
由于
- #include <iostream>
- #include <string>
- using namespace std;
- #define MOD (long)pow(10,9) + 7
- string str;
- int len;
- //求解运行数的个数
- int lucky(int num)
- {
- int start = len - num;
- if (num == 1)
- {
- if (str[start] >= '7')
- return 2;
- else if (str[start] >= '4')
- return 1;
- else
- return 0;
- }
- if (str[start] > '7')
- return pow(2, num + 1) - 1;
- else if (str[start] == '7')
- return 3 * pow(2, num - 1) - 1 + lucky(num - 1);
- else if (str[start] < '7' && str[start] > '4')
- return 3 * pow(2, num - 1) - 1;
- else if (str[start] == '4')
- return pow(2, num) - 1 + lucky(num - 1);
- else
- return pow(2,num) - 1;
- }
- int main()
- {
- while (cin >> str)
- {
- len = str.length();
- cout << (lucky(len) - 1) % (MOD) << endl;
- }
- return 0;
- }
使用代换法,明显可以看出,是一个等差数列,故时间复杂度为O(n),其中n为输入字符串的长度,即为输入数的位数。
来源: http://blog.csdn.net/qq_25245961/article/details/78055434