题解：P17074 [ICPC 2017 Shenyang R] New Self-describing Sequence

· · 题解

妙妙 trick。相似题（更复杂）推荐：P14473。

性质

容易发现每次只会增加各位数字之和，这个东西很小，只有 200 左右。于是想到将每个数拆分成 1000x+y 的形式，这样加一次 x 只会加 1 或不变。

分析

我们尝试从高往低去确定每一位的答案是多少。那么我就要快速的知道从一个形如 \overline{x_1x_2\cdots x_c00\cdots0abc} 得到 \overline{x_1x_2\cdots x_cx_{c+1}0\cdots0a'b'c'} 需要多少步。即我要确定 x_{c+1} 的值。

我们通过从 1\sim 9 看当 x_{c+1} 每增加 1，步数总和是否超过 n。即我们要知道第 c+2 位每进一次位，需要多少步。

想想除了需要多少步，我们还需要知道哪些信息：设 f_{c,i,j} 表示中间有 i 个 0，前面的高位的数字和为 c，末尾三位为 j，到中间最高位的 0 发生一次进位，记录：

::::info[解释一下 x 和 sum 的含义] 假设当前位置的数为 a_p，经过 c 步后的位置的数为 a_q。那么 x=a_q-a_p，sum=\sum_{i=p+1}^q a_i-a_p(q-p)。

即可以理解为将 a_p 看作 0，即序列起点，第 q-p 项的值及前缀和。 ::::

接下来考虑转移。

首先考虑初状态，即 f_{c,0,j}，也就是后三位要发生进位，显然直接暴力跳即可。

接下来对于 f_{c,i,j}，我们需要将从低位数第 i+j 位为 0\sim 9 的情况均加进来，即需要第 i+j-1 位进位 10 次。

于是我们考虑合并两个状态，即在 f_{c,i,j} 后接上 f_{c+d,i-1,j'}（d 为第 i+j 位的值）。

假设两状态分别为 f_{c_1,i_1,j_1} 与 f_{c_2,i_2,j_2}。首先显然有 f_{c_1,i_1,j_1}\rightarrow z=j_2，否则无法接续。我们考虑新的四个量分别是什么：

然后就是求每一位的值了。借助前面预处理好的 dp 数组，我们可以很快的求出将一个高位进一位的一些信息。最后剩下 1000 以内的暴力跳即可，详见代码。

code

::::success[code]

#include<bits/stdc++.h>
#define ll long long
#define lll __int128
using namespace std;
const int mod=1e9+9;
int t;
ll n;
struct node{
    lll c,x,sum;
    int z;
    node operator +(const node &y)const{
        return {c+y.c,x+y.x,(sum+y.sum+x*y.c)%mod,y.z};
    }
}f[200][20][1000];
void out(lll x){
    if(!x) return;
    out(x/10);
    putchar(x%10+'0');
}
void write(node x){
    out(x.x);
    putchar(' ');
    out(x.sum);
    putchar('\n');
}
int digit(lll x){
    int cnt=0;
    while(x){
        cnt+=x%10;
        x/=10;
    }
    return cnt;
}
void init(){
    for(int c=0;c<200;c++){
        for(int i=0;i<1000;i++){
            if(!(i+c)) continue;
            int j=i;
            while(j<1000){
                int k=c+digit(j);
                j+=k;
                f[c][0][i].c++,f[c][0][i].x+=k,f[c][0][i].sum=(f[c][0][i].sum+f[c][0][i].x)%mod;
            }
            f[c][0][i].z=j%1000;
        }
    }
    for(int i=1;i<=17;i++){
        for(int c=0;c<200;c++){
            for(int j=0;j<1000;j++){
                f[c][i][j].z=j;
                for(int d=0;d<10&&c+d<200;d++){
                    f[c][i][j]=f[c][i][j]+f[c+d][i-1][f[c][i][j].z];
                }
            }
        }
    }
}
node work(ll n){
    node nw={1,1,1,1};
    int ds=0;
    for(int i=17;i>=0;i--){
        for(int j=1;j<10;j++){
            if(nw.c+f[ds][i][nw.z].c<=n){
                nw=nw+f[ds][i][nw.z];
                ds++;
            }
        }
    }
    while(nw.c<n){
        int xx=digit(nw.x);
        nw.c++,nw.x+=xx,nw.sum=(nw.sum+nw.x)%mod;
    }
    return nw;
}
int main(){
    init();
    cin>>t;
    for(int T=1;T<=t;T++){
        scanf("%lld",&n);
        printf("Case #%d: ",T);
        write(work(n));
    }
    return 0;
}

::::