SAN

· · 题解

[COCI2015-2016#6]

SAN

题目大意

题目描述

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

求表中 x 以内的数有多少

思考

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

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

即，如果它为七位数，那可以写作 $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
  1. 搜索过程中一个数会被多次搜索

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

比如 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;
  1. 如何求第二列以后的数

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

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

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;
}