九度oj 题目1491：求1和2的个数

题目描述：: 给定正整数N，函数F(N)表示小于等于N的自然数中1和2的个数之和，例如：1,2,3,4,5,6,7,8,9,10序列中1和2的个数之和为3，因此F(10)=3。输入N，求F(N)的值，1=<N<=10^100(10的100次方)若F(N)很大，则求F(N)mod20123的值。

输入：: 输入包含多组测试数据，每组仅输入一个整数N。

输出：: 对于每组测试数据，输出小于等于N的自然数中1和2的个数之和，且对20123取模。

样例输入：

10
11

样例输出：

3
5

提示：

建议用scanf ("%s")输入，而不建议用gets()！

这道题好难

开始用的思路简单，但必然超时

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <queue>
 8 #define inf 0x3f3f3f3f
 9 #define MAX 102
10 using namespace std;
11 
12 char N[MAX];
13 int temp[MAX];
14 int end[MAX];
15 
16 int inc(int wei) {
17     int ci = 1;
18     for(int i = 0; i < wei; i++) {
19         int sum = temp[i] + ci;
20         int ben = sum%10;
21         ci =  sum/10;
22         temp[i] = ben;
23     }    
24     if(ci == 1) {
25         temp[wei] = 1;
26         wei++;
27         return wei;
28     }
29     else {
30         return wei;
31     }
32     
33 }
34 
35 bool isEqual(int n) {
36     for(int i = 0; i < n; i++) {
37         if(temp[i] != end[i]) {
38             return false;
39         }
40     }
41     return true;
42 }
43 
44 void show(int wei) {
45     for(int i = wei-1;i >= 0; i--) {
46         printf("%d",temp[i]);
47     }
48     puts("");
49 }
50 
51 void showE(int n) {
52     for(int i = n-1;i >= 0; i--) {
53         printf("%d",end[i]);
54     }
55     puts("");
56 }
57 
58 int main(int argc, char const *argv[])
59 {
60     while(scanf("%s",N) != EOF) {
61         int weiSum = strlen(N);
62         int wei = 1;
63         for(int i = 0; i < strlen(N); i++) {
64             temp[i] = 0;
65             end[i] = 0;
66         }
67         for(int i = 0,j = strlen(N) - 1; i < strlen(N); i++, j--) {
68             end[j] = N[i] - '0';
69         }
70         //showE(weiSum);
71         temp[0] = 1;
72         int ans = 0;
73         while(!isEqual(weiSum)) {
74             int ttt = 0;
75             for(int i = 0; i < wei; i++) {
76                 if(temp[i] == 1 || temp[i] == 2) {
77                     ttt++;
78                 }
79             }
80             ans = (ans + ttt) % 20123;
81             wei = inc(wei);
82             //show(wei);
83         }
84         int ttt = 0;
85         for(int i = 0; i < weiSum; i++) {
86             if(end[i] == 1 || end[i] == 2) {
87                 ttt++;
88             }
89         }
90         ans = (ans + ttt) % 20123;
91         printf("%d
", ans);
92     }
93     return 0;
94 }

后一种思路是这样的，比如算123, 先求F(1)，再求F(2)，再求F(3)

先上代码

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <queue>
 8 #define inf 0x3f3f3f3f
 9 #define MAX 102
10 using namespace std;
11 
12 char N[MAX];
13 
14 int main(int argc, char const *argv[])
15 {
16     while(scanf("%s",N) != EOF) {
17         int result = 0;
18         int count12 = 0;
19         int num = 0;
20         for(int i = 0; i < strlen(N); i++) {
21             int temp = N[i] - '0';
22             int q = 2;
23             if(temp == 0) {
24                 q = 0;
25             }
26             else if(temp == 1) {
27                 q = 1;
28             }
29             else if(temp == 2) {
30                 q = 2;
31             }
32             //个位 2 * num + q
33             //前面的位(前1) (result - count12) * (temp+1)
34             //本身 count12 * (temp+1)
35             
36             //for example 123
37             // 2 * 12 + 2 = 26
38             // F(11) = result - count12   F(11)*10
39             // 123 12有2位 ,后面0 1 2 3   2 * 4 即 count12*(temp+1)
40             result = 2 * num + q + (result - count12) * 10 + count12 * (temp+1);
41 
42             if(N[i] == '1' || N[i] == '2') {
43                 count12++;
44             }
45             num = num * 10 + temp;
46             num = num % 20123;
47             result = result % 20123;
48         }
49         printf("%d
", result);
50     }
51     return 0;
52 }

主要的思想是分位来统计1和2的个数，求出前n-1位的值，再求出总共n位的值

对于个位而言，前面0 - (num-1)共有num个数, 每10个数有2个1和2,所以共有 2*num个数

前面是num，后面有q个2

对于前面的位而言,F(N-1) = result - count12, 每一个有10个各位，共有 10 * F(N-1)个

对于num， num中有count12个1,2 后面那位是temp , 0-temp有temp+1个，共有 count12 * (temp+1)个