単に回文を数えるだけだが、桁DPが面倒だったので暴力的な解法に頼ってしまった。

solution

埋め込み。$O(N)$。

愚直に$1$から$N$まで全て試すことを考える。 $10^9+1$の倍数だけ考えればよいので$10^9$個程試すだけでよい。 そのまま実装すると$10$分程度かかるが、埋め込みをすれば間に合う。

implementation

#include <iostream>
#include <algorithm>
#include <sstream>
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

constexpr ll k = 1000000001;
extern const int table[];
constexpr ll width = k * 1000000;
string str(ll n) {
    ostringstream oss;
    oss << n;
    return oss.str();
}
int main() {
    ll n; cin >> n;
    ll i = 0;
    while (i + width <= n) i += width;
    int cnt = table[i / width];
    i += k;
    for (; i <= n; i += k) {
        string s = str(i);
        string t = s; whole(reverse, t);
        if (s == t) ++ cnt;
    }
    cout << cnt << endl;
    return 0;
}

const int table[] = {
0,1998,2998,3998,4998,5998,6998,7998,8998,9998,10998,11098,11198,11298,11398,
11498,11598,11698,11798,11898,11998,12098,12198,12298,12398,12498,12598,12698,
12798,12898,12998,13098,13198,13298,13398,13498,13598,13698,13798,13898,13998,
14098,14198,14298,14398,14498,14598,14698,14798,14898,14998,15098,15198,15298,
15398,15498,15598,15698,15798,15898,15998,16098,16198,16298,16398,16498,16598,
16698,16798,16898,16998,17098,17198,17298,17398,17498,17598,17698,17798,17898,
17998,18098,18198,18298,18398,18498,18598,18698,18798,18898,18998,19098,19198,
19298,19398,19498,19598,19698,19798,19898,19998,20098,20198,20298,20398,20498,
20598,20698,20798,20898,20998,21098,21198,21298,21398,21498,21598,21698,21798,
21898,21998,22098,22198,22298,22398,22498,22598,22698,22798,22898,22998,23098,
23198,23298,23398,23498,23598,23698,23798,23898,23998,24098,24198,24298,24398,
24498,24598,24698,24798,24898,24998,25098,25198,25298,25398,25498,25598,25698,
25798,25898,25998,26098,26198,26298,26398,26498,26598,26698,26798,26898,26998,
27098,27198,27298,27398,27498,27598,27698,27798,27898,27998,28098,28198,28298,
28398,28498,28598,28698,28798,28898,28998,29098,29198,29298,29398,29498,29598,
29698,29798,29898,29998,30098,30198,30298,30398,30498,30598,30698,30798,30898,
30998,31098,31198,31298,31398,31498,31598,31698,31798,31898,31998,32098,32198,
32298,32398,32498,32598,32698,32798,32898,32998,33098,33198,33298,33398,33498,
33598,33698,33798,33898,33998,34098,34198,34298,34398,34498,34598,34698,34798,
34898,34998,35098,35198,35298,35398,35498,35598,35698,35798,35898,35998,36098,
36198,36298,36398,36498,36598,36698,36798,36898,36998,37098,37198,37298,37398,
37498,37598,37698,37798,37898,37998,38098,38198,38298,38398,38498,38598,38698,
38798,38898,38998,39098,39198,39298,39398,39498,39598,39698,39798,39898,39998,
40098,40198,40298,40398,40498,40598,40698,40798,40898,40998,41098,41198,41298,
41398,41498,41598,41698,41798,41898,41998,42098,42198,42298,42398,42498,42598,
42698,42798,42898,42998,43098,43198,43298,43398,43498,43598,43698,43798,43898,
43998,44098,44198,44298,44398,44498,44598,44698,44798,44898,44998,45098,45198,
45298,45398,45498,45598,45698,45798,45898,45998,46098,46198,46298,46398,46498,
46598,46698,46798,46898,46998,47098,47198,47298,47398,47498,47598,47698,47798,
47898,47998,48098,48198,48298,48398,48498,48598,48698,48798,48898,48998,49098,
49198,49298,49398,49498,49598,49698,49798,49898,49998,50098,50198,50298,50398,
50498,50598,50698,50798,50898,50998,51098,51198,51298,51398,51498,51598,51698,
51798,51898,51998,52098,52198,52298,52398,52498,52598,52698,52798,52898,52998,
53098,53198,53298,53398,53498,53598,53698,53798,53898,53998,54098,54198,54298,
54398,54498,54598,54698,54798,54898,54998,55098,55198,55298,55398,55498,55598,
55698,55798,55898,55998,56098,56198,56298,56398,56498,56598,56698,56798,56898,
56998,57098,57198,57298,57398,57498,57598,57698,57798,57898,57998,58098,58198,
58298,58398,58498,58598,58698,58798,58898,58998,59098,59198,59298,59398,59498,
59598,59698,59798,59898,59998,60098,60198,60298,60398,60498,60598,60698,60798,
60898,60998,61098,61198,61298,61398,61498,61598,61698,61798,61898,61998,62098,
62198,62298,62398,62498,62598,62698,62798,62898,62998,63098,63198,63298,63398,
63498,63598,63698,63798,63898,63998,64098,64198,64298,64398,64498,64598,64698,
64798,64898,64998,65098,65198,65298,65398,65498,65598,65698,65798,65898,65998,
66098,66198,66298,66398,66498,66598,66698,66798,66898,66998,67098,67198,67298,
67398,67498,67598,67698,67798,67898,67998,68098,68198,68298,68398,68498,68598,
68698,68798,68898,68998,69098,69198,69298,69398,69498,69598,69698,69798,69898,
69998,70098,70198,70298,70398,70498,70598,70698,70798,70898,70998,71098,71198,
71298,71398,71498,71598,71698,71798,71898,71998,72098,72198,72298,72398,72498,
72598,72698,72798,72898,72998,73098,73198,73298,73398,73498,73598,73698,73798,
73898,73998,74098,74198,74298,74398,74498,74598,74698,74798,74898,74998,75098,
75198,75298,75398,75498,75598,75698,75798,75898,75998,76098,76198,76298,76398,
76498,76598,76698,76798,76898,76998,77098,77198,77298,77398,77498,77598,77698,
77798,77898,77998,78098,78198,78298,78398,78498,78598,78698,78798,78898,78998,
79098,79198,79298,79398,79498,79598,79698,79798,79898,79998,80098,80198,80298,
80398,80498,80598,80698,80798,80898,80998,81098,81198,81298,81398,81498,81598,
81698,81798,81898,81998,82098,82198,82298,82398,82498,82598,82698,82798,82898,
82998,83098,83198,83298,83398,83498,83598,83698,83798,83898,83998,84098,84198,
84298,84398,84498,84598,84698,84798,84898,84998,85098,85198,85298,85398,85498,
85598,85698,85798,85898,85998,86098,86198,86298,86398,86498,86598,86698,86798,
86898,86998,87098,87198,87298,87398,87498,87598,87698,87798,87898,87998,88098,
88198,88298,88398,88498,88598,88698,88798,88898,88998,89098,89198,89298,89398,
89498,89598,89698,89798,89898,89998,90098,90198,90298,90398,90498,90598,90698,
90798,90898,90998,91098,91198,91298,91398,91498,91598,91698,91798,91898,91998,
92098,92198,92298,92398,92498,92598,92698,92798,92898,92998,93098,93198,93298,
93398,93498,93598,93698,93798,93898,93998,94098,94198,94298,94398,94498,94598,
94698,94798,94898,94998,95098,95198,95298,95398,95498,95598,95698,95798,95898,
95998,96098,96198,96298,96398,96498,96598,96698,96798,96898,96998,97098,97198,
97298,97398,97498,97598,97698,97798,97898,97998,98098,98198,98298,98398,98498,
98598,98698,98798,98898,98998,99098,99198,99298,99398,99498,99598,99698,99798,
99898,99998,100098,100198,100298,100398,100498,100598,100698,100798,100898,
100998,101098,101198,101298,101398,101498,101598,101698,101798,101898,101998,
102098,102198,102298,102398,102498,102598,102698,102798,102898,102998,103098,
103198,103298,103398,103498,103598,103698,103798,103898,103998,104098,104198,
104298,104398,104498,104598,104698,104798,104898,104998,105098,105198,105298,
105398,105498,105598,105698,105798,105898,105998,106098,106198,106298,106398,
106498,106598,106698,106798,106898,106998,107098,107198,107298,107398,107498,
107598,107698,107798,107898,107998,108098,108198,108298,108398,108498,108598,
108698,108798,108898,108998,109098,109198,109298,109398,109498,109598,109698,
109798,109898
};

埋め込み対象

#include <iostream>
#include <algorithm>
#include <sstream>
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
string str(ll n) {
    ostringstream oss;
    oss << n;
    return oss.str();
}
int main() {
    ll n = 1000000000000000000;
    int cnt = 0;
    for (ll i = 1000000001; i < n; i += 1000000001) {
        string s = str(i);
        string t = s; whole(reverse, t);
        if (s == t) ++ cnt;
        if ((i / 1000000001) % 1000000 == 0) cout << i << ' ' << cnt << endl;
    }
    return 0;
}