学步园

题目描述：

给定正整数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

CSDN论坛上搜到的一种解法，另外《编程之美》上也讲过这个题目。

C++代码：

#include <iostream>
#include <string>
using namespace std;

const int MOD = 20123;
int pow(int n, int exp)
{
	if(exp == 0)
		return 1;
	int t = pow(n * n % MOD, exp / 2);
	if(exp % 2 == 1)
		t = t * n % MOD;
	return t;
}
int pnm(int b, int e, int n)
{
	return n * pow(b, e) % MOD;
}
void Add(int& r, int v)
{
	r = (r + v) % MOD;
}
int judge(int digit)
{
	switch(digit)
	{
	case 1:
	case 2:
		return 1;
	default:
		return 0;
	}
}
int main()
{
	string num;
	int x[10];
	x[0] = judge(0);
	for(int i=1;i<10;i++)
		x[i] = x[i-1] + judge(i);
	while(cin>>num)
	{
		int cnt = 0;
		int result = 0;
		int len = num.size();
		for(int i=0;i<len;i++)
		{
			int digit = num[i] - '0';
			if(i < len-1)
				Add(result, pnm(10, len-2-i, x[9]*digit*(len-1-i)));
			if(digit > 0)
				Add(result, pnm(10, len-1-i, x[digit-1]));
			Add(result, pnm(10, len-1-i, cnt*digit));
			cnt += judge(digit);
		}
		Add(result, cnt);
		cout<<result<<endl;
	}
	return 0;
}