恩爱的回文数_牛客博客

题目描述

因为最近身边脱单的人太多了,于是 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位数为900.....

代码：

#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("10\n");
			continue;
		}
		if(n == 2)
		{
			printf("19\n");
			continue;
		}
		sum = 19;
		for(i = 3;i <= n;i ++)
		{
			if(c == 2) //用c来记录次数，每两次次数*10
			{
				s= (s*10)%mod;
				c = 1;
			}
			else
				c++;
			sum = (sum+s) % mod;
		}
		printf("%lld\n",sum%mod);
	}
	return 0;
}