QAQ的幸运数字

迷南。 2022-07-12 09:53 121阅读 0赞

### QAQ的幸运数字 ###

Time Limit: 1000MS  Memory Limit: 65536KB

[Submit][]  [Statistic][]  [Discuss][]

#### Problem Description ####

金牌巨 QAQ 经常靠涨人品 (Rising RP) 来 A 题。他的幸运数字是 4 和 7，因此他也经常在第 4 发或第 7 发提交时过题（误）。

一天，突 (xian) 发 (de) 奇 (wu) 想 (liao) 的 QAQ 定义了一种新的数叫「厉害了我的金桔数」，指只含有且必须同时含有 4 和 7 的数。栗如：47, 747 是「厉害了我的金桔数」，而 2333, 666, 457, 777 就不是「厉害了我的金桔数」。

现在，他想知道在位数不超过 n 的正整数内，有多少个数是「厉害了我的金桔数」。

PS：由于「厉害了我的金桔数」实在是太多啦，QAQ 决定，所有的结果都需要 膜 (模) QAQ 自己，即计算结果需要对 816581 取模（取余）。

#### Input ####

输入数据有多组（数据组数不超过 10000），到 EOF 结束。

每组输入为一行，包含一个正整数 n (1 <= n <= 10000)。

#### Output ####

对于每组输入，输出一行，包含一个整数，表示在位数不超过 n 的正整数内「厉害了我的金桔数」的个数，结果需要对 816581 取模。

#### Example Input ####

1
    2
    3

#### Example Output ####

0
    2
    8

#### Hint ####

如果你的结果不是一步得出的，那么你可能需要在每一步运算时都进行一次取模操作。

n = 3 时，不超过 3 位的「厉害了我的金桔数」共有 8 个，分别为：47, 74, 447, 474, 477, 744, 747, 774。

#### Author ####

「2016级ACM集训队第一次选拔赛」bLue

\#include <stdio.h>  
\#define MAXN 10000  
\#define mod 816581  
  
  
int f\[MAXN+1\] = \{0, 0, 2\};  
  
  
int pow(int a, int n)   // 自己写的幂函数  
\{  
    int p = 1;  
    while(n--)  
    \{  
        p = (p\*a) % mod;//不能直接调用pow函数，需要取模  
    \}  
  
  
    return p;  
\}  
  
  
void Init()   // 递推。预处理 1 到 10000 的所有值  
\{  
    for(int i=3; i<=MAXN; ++i)  
    \{  
        f\[i\] = (f\[i-1\] + pow(2, i) - 2 ) % mod;//若n<mod 的话，取模以后还是n本身；  
    \}  
\}  
  
  
int main()  
\{  
    Init();//把所有的值先算出来存好  
    int n;  
    while(~ scanf("%d", &n))  
    \{  
        printf("%d\\n", f\[n\]);//直接用该数组的值  
    \}  
  
  
    return 0;  
\}  
/\*知识点：  
1.大数取模的计算  
2.找规律做题，推出递推公式  
3.\*/

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/submitsolution/pid/3690.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/status/pid/3690.html
[Discuss]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Discuss/discusslist/pid/3690.html