恩爱的回文数

恩爱的回文数

题目描述

因为最近身边脱单的人太多了,于是 GBX 狂热的迷上了回文数。因为回文数看起来就像是一对恩爱狗站在一起,他希望自己将来也有那么一天(虽然并不可能)。这一天他突然想到一个问题,长度不大于 n 的自然数中有多少是回文数?因为数据很大,所以最后的结果请对 1000000007 取模。

输入

输入一个 T(T ≤ 100)表示 T 组数据。
对于每组数据输入一个整数 n(1 ≤ n ≤ 10^6 )。

输出

对于每组数据输出一个整数表示回文数的个数对 1000000007 取模的余数。

样例输入

2
1
2

样例输出

1019

思路：

n为1时，个数为10； n为2时，个数为19； n为3时，个数为19+90； n为4时，个数为109+90；

规律为3位数时为90，4位数时为90，5位数为900，6位数为 代码：

#include<stdio.h>
int main()
{int mod = 1000000007;int i,j,t,n,c;long long sum = 0,s;scanf("%d",&t);while(t--){s = 90;c = 0;scanf("%d",&n);if(n == 1){printf("10n");continue;}if(n == 2){printf("19n");continue;}sum = 19;for(i = 3;i <= n;i ++){if(c == 2) //用c来记录次数，每两次次数*10{s= (s*10)%mod;c = 1;}elsec++;sum = (sum+s) % mod;}printf("%lldn",sum%mod);}return 0;
}