1391 - 函数求值
时间限制 : 1 秒
内存限制 : 32 MB
给定正整数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的值
题目输入
题目输出
输入/输出样例
输入格式
10 10
输出格式
3 3
C++解答
#include<stdio.h> #include<string.h> #define M 20123 int main() { int f[128]; char str[128]; int d[128]; int f1[128]; int i,j,n,r; for(f[0]=i=1;i<128;i++) f[i]=f[i-1]*10%M; for(f1[0]=0,i=1;i<128;i++) f1[i]=(f1[i-1]+i*f[i-1])%M; while(scanf("%s",str)!=EOF) { n=strlen(str); for(i=n-1;i>=0 && str[i]=='9';i--) str[i]='0'; if (i>=0) str[i]++; else { str[n]='0',str[n+1]='\0'; str[0]='1',n++; } r=0;d[n]=0; for(i=n-1;i>=0;i--) d[i]=(d[i+1]+(str[i]-'0')*f[n-1-i])%M; for(i=0;i<n;i++) { r=(r+(str[i]-'0')*f1[n-1-i]*2)%M; if (str[i]>'2') r=(r+f[n-1-i]*2)%M; else if (str[i]>'1') r=(r+f[n-1-i]+d[i+1])%M; else if (str[i]=='1') r=(r+d[i+1])%M; } printf("%d\n",r); } return 0; }