题解：关注 small_lemon_qwq 谢谢喵

· · 题解

考虑不打表。

另一种非打表但是需要点脑子的做法见这里。

令 n=X。

注意到，从 70 报数报到 79，每报一次数报数的方向就反一下，那么实际相当于报数的方向不变，并且报 80 的人就是报 70 的人，所以可以考虑直接将其优化掉，遇到非个位出现 7 直接将它变成 8，但是注意变成 8 不要超过了 n。

这样运算量就大概是 9^8\times10\times9=3874204890\approx4\times10^9，显然无法通过，考虑优化检查是否存在为 7 的位这一步。

这个题解启发我们可以用高精度动态求检查是否存在为 7 的位，但我们不仅要判断是否存在为 7 的位，还要求出这个为 7 的位。我的做法是开一个栈存储所有为 7 的位，动态更新这个栈，查询时直接返回栈顶（如果有）。前面这句话过时了，我的新做法可以看代码。

考虑计算运算量，9^8\times10+111111111=541578321\approx5\times10^8，其中 111111111 是高精度进位次数，卡一下午常就过了。

补一下时间复杂度，设 V=10^9，那么时间复杂度就是 \operatorname{O}(9^{\lg(V)}+\frac{V}{10})，好吧，还是 \operatorname{O}(V)。

#include<bits/stdc++.h>
using namespace std;
#define if_1(x) if(__builtin_expect((x),1))
#define if_0(x) if(__builtin_expect((x),0))
int T,n,x,d=1,p[10]{1};
uint8_t cnt,c[10]{1},t;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=9;i++)p[i]=p[i-1]*10;
    for(int i=1;i<=n;){
        x+=d;
        (i%7==0||c[t]==7)&&(d=~d+1);
        if_0(t&&c[t]==7){
            if_1(i+p[t]<=n){
                i+=p[t],++c[t];
            }else{
                ((n-i)&1)&&(x+=d);
                break;
            }
            x-=(d=~d+1);
            continue;
        }
        ++i;
        int j(0);
        while(c[j]==9)c[j++]=0;
        (++c[j])==7&&(t=j);
    }
    cout<<(x%1337+1336)%1337+1;
    return 0;
}