自动搬运

查看原文

来自洛谷，原作者为

	XUAN— 扶摇直上九万里

搬运于2025-08-24 22:33:13，当前版本为作者最后更新于2021-11-07 09:59:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[COCI2015-2016#6]

SAN

题目大意

题目描述

给定一张表，规定第 $i$ 行 第一列 为 $i$ ( $A_{i1}=i$ ) 然后每一行进行递推 $A_{ij}=A_{i(j-1)}+rev(A_{i(j-1)})$

求表中 $x$ 以内的数有多少

思考

观察了题目，注意这句话 ： 有趣的是，表中的每个数字出现的次数是有限的

haha ,有趣的是，我们也发现在 $10^{10}$ 以内出现的在第二列的数也是有限的

$A_{ij}=A_{i(j-1)}+rev(A_{i(j-1)})$ 中 $A_{ij}$ 满足了什么性质？通过其计算方式可以发现 ，它的每一位应该关于中间位对称

即，如果它为七位数，那可以写作 $p_1p_2p_3p_4p_3p_2p_1$ ( $0<=p_i<=18$ ) 因此，我们完全可以通过搜索算出在第二列出现的数，以及次数（按照这个性质，所有在第二列后出现的数都一定是在第二列出现过的）

细节

想到了这里，此题基本结束了，但蒟蒻调了太久了，还是打算分享一下需要注意的细节

1. 如何统计在第二列出现的数的次数

若我们搜到一个数 $x=p_1p_2p_3p_2p_1$ ，那它以这种形态出现在表中的次数应为 $f_1 \times f_2 \times f_3$ ( $f_i$ 为 $p_i$ 的拆数方案数)

需要注意的是 其他位可以拆成 $p_i = x_1+x_2$ ( $0<=x_1<=9$ 且 $0<=x_2<=9$ ）

但是！！首位的加数 $x_1$ 不可以为零！！因为这样映射到的第一列的数是不合法的 $p_1=x_1+x_2$ ( $1<=x_1<=9$ 且 $0<=x_2<=9$ )

此外中间位 $p_3$ 只能拆成 $p_3=x+x$ ，因此必须是偶数，且 $f_3=1$

2. 搜索过程中一个数会被多次搜索

它是以不同形态被搜到的，每一种都必须要被记录，最后（次数）合并到一起

比如 $121$ ，第一次被搜到是 $11,11$ ($f=8(11=2+9,3+8,4+7,5+6...)$)

然后又会被搜到是 $1,2,1$ $f=1 \times 1(1=1+0,2=1+1)$

至此，$121$ 应该在第二列出现了$9$次了

为了这个合并操作，学习了个方便的 $STL$ ，去重：（返回去重后的元素个数）

Cnt_a=unique(a+1,a+1+cnt_a)-a-1;

3. 如何求第二列以后的数

以为一个数的后继是唯一的，那么它出现的多少次，它的后继就一定出现的多少次，那么一个数的出现次数就为它所有前继次数的和，那么就可以枚举所有第二列的数向后递推得到了

4. 注意还要加上在第一列出现的次数

Code

# define N 4000005
# define LL long long
const int p=10;
const LL M=1e10;
int q,tot=0;
LL L,R,f[N+5],a[N+5],pow_10[11],b[N+5],c[N+5];
inline LL rev(LL x)
{
 	LL ret=0;
	while(x)
	{
		ret=(ret*10)+x%p;
		x/=p;
	}
	return ret;
}
inline int find(LL x) // 二分查找 
{
	int l=0,r=tot,mid;
	while(l<r)
	{
		mid=(l+r+1)>>1;
		if(a[mid]<=x) l=mid;
		else r=mid-1;
	}
	return l;
}
inline LL calc(LL x)
{
	if(x==0) return 0;
	int pl=find(x);	
	return f[find(x)]+x; //注意加上第一列出现的次数（x） 
}
LL hh[2][20]={{1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1},{0,1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2,1}};// hh[1]:首位 ,hh[0]:非首位 
void dfs(int ed,int dep,LL s,LL t) 
{
	if(s>M) return ;
	if(dep==(ed+1>>1)) 
	{
		c[++tot]=t;
		b[tot]=a[tot]=s;
		return;
	}
	if((dep<<1|1)==ed)  // mid : i = x+x
	{
		for(LL i=(dep==0);i<=18;i++) 
			if(!(i&1))dfs(ed,dep+1,s+pow_10[dep]*i,t);
	}
	else
	{
		for(LL i=(dep==0);i<=18;++i)
			dfs(ed,dep+1,s+(pow_10[dep]+pow_10[ed-dep-1])*i,t*hh[dep==0][i]);
	}
	
}
inline void PreWork()
{
	pow_10[0]=1;
	for(int i=1;i<=10;++i) pow_10[i]=pow_10[i-1]*10LL;
	for(int i=1;i<=10;++i)
		dfs(i,0,0,1);
	sort(a+1,a+1+tot);
	int cnt=tot;
	tot=unique(a+1,a+1+tot)-a-1; // 去重 
	for(int i=1;i<=cnt;++i) 
	{
		int pos=find(b[i]);
		f[pos]+=c[i]; // 合并得到在第二列出现的总次数 
	}
	for(int i=1;i<=tot;++i)
	{	
		LL tmp=a[i]+rev(a[i]); //从第二列递推后列 
		if(tmp>M||tmp<0) continue;
		f[find(tmp)]+=f[i];	
	}
	for(int i=1;i<=tot;++i) f[i]+=f[i-1]; // 前缀和 
}
int main()
{
	PreWork();
	read(q);	
	while(q--)
	{
		read(L),read(R);L--;
		print(calc(R)-calc(L)),putchar('\n');
	}
	return 0;
}