\( \begin{matrix} f(1) &=& 1\\ f(2) &=& 2\\ ...\\ f(9) &=& 9\\ f(10) &=& 10 &-& 9\\ f(11) &=& 11 &-& 9\\ ...\\ f(99) &=& 99 &-& 9\\ f(100) &=& 100 &-& 9 &-& 90\\ f(101) &=& 101 &-& 9 &-& 90\\ ...\\ f(999) &=& 999 &-& 9 &-& 90\\ f(1000) &=& 1000 &-& 9 &-& 90 &-& 900\\ f(1001) &=& 1001 &-& 9 &-& 90 &-& 900\\ ... \end{matrix} \)

以上の観察により、答えは \(N\) 以下の正整数の和から、

• \(10\) 以上の数が \(M\) 個あれば \(9M\) を引く
• \(100\) 以上の数が \(M\) 個あれば \(90M\) を引く
• \(1000\) 以上の数が \(M\) 個あれば \(900M\) を引く
• \(10000\) 以上の数が……

となります。Pythonなどの多倍長整数が使える言語を使うか、C++のACLに入っているmodintなどを使うと実装が容易です。

実装例(Python)

N=int(input())
ans=N*(N+1)//2

if N>=10: ans-=9*(N-9)
if N>=100: ans-=90*(N-99)
if N>=1000: ans-=900*(N-999)
if N>=10000: ans-=9000*(N-9999)
if N>=100000: ans-=90000*(N-99999)
if N>=1000000: ans-=900000*(N-999999)
if N>=10000000: ans-=9000000*(N-9999999)
if N>=100000000: ans-=90000000*(N-99999999)
if N>=1000000000: ans-=900000000*(N-999999999)
if N>=10000000000: ans-=9000000000*(N-9999999999)
if N>=100000000000: ans-=90000000000*(N-99999999999)
if N>=1000000000000: ans-=900000000000*(N-999999999999)
if N>=10000000000000: ans-=9000000000000*(N-9999999999999)
if N>=100000000000000: ans-=90000000000000*(N-99999999999999)
if N>=1000000000000000: ans-=900000000000000*(N-999999999999999)
if N>=10000000000000000: ans-=9000000000000000*(N-9999999999999999)
if N>=100000000000000000: ans-=90000000000000000*(N-99999999999999999)
if N>=1000000000000000000: ans-=900000000000000000*(N-999999999999999999)

print(ans%998244353)

実装例(C++)

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using mint=modint998244353;

int main(){
	long long N;
	cin >> N;
	mint ans=mint(N)*(N+1)/2;
	if(N>=10)ans-=mint(9)*(N-9);
	if(N>=100)ans-=mint(90)*(N-99);
	if(N>=1000)ans-=mint(900)*(N-999);
	if(N>=10000)ans-=mint(9000)*(N-9999);
	if(N>=100000)ans-=mint(90000)*(N-99999);
	if(N>=1000000)ans-=mint(900000)*(N-999999);
	if(N>=10000000)ans-=mint(9000000)*(N-9999999);
	if(N>=100000000)ans-=mint(90000000)*(N-99999999);
	if(N>=1000000000)ans-=mint(900000000)*(N-999999999);
	if(N>=10000000000)ans-=mint(9000000000)*(N-9999999999);
	if(N>=100000000000)ans-=mint(90000000000)*(N-99999999999);
	if(N>=1000000000000)ans-=mint(900000000000)*(N-999999999999);
	if(N>=10000000000000)ans-=mint(9000000000000)*(N-9999999999999);
	if(N>=100000000000000)ans-=mint(90000000000000)*(N-99999999999999);
	if(N>=1000000000000000)ans-=mint(900000000000000)*(N-999999999999999);
	if(N>=10000000000000000)ans-=mint(9000000000000000)*(N-9999999999999999);
	if(N>=100000000000000000)ans-=mint(90000000000000000)*(N-99999999999999999);
	if(N>=1000000000000000000)ans-=mint(900000000000000000)*(N-999999999999999999);
	cout << ans.val();
}

類題 ABC195C『Comma』