yukicoder : No.3277 Forever Monotonic Number

お手頃な難易度の問題。
https://yukicoder.me/problems/no/3277

問題

ある正整数nがmonotonicとは、nの10進数表記における数字の並びが昇順であることをいう。

d(n)は、nの各桁の総和とする。
ある正整数nがforever-monotonicとは、nをd(n)で置き換えることを繰り返しても、ずっとmonotonicであることをいう。

整数Nが与えられる。
10^N以上の整数で、forever-monotonicな最小値について、998244353で割った余りを答えよ。

解法

10^N以上の整数でmonotonicな最小値dは、111....111と(N+1)桁繰り返したものであり、d(x)はN+1となる。
d(x)は高々15桁なので、d(d(x))は150以下である。

そこで、あらかじめ150以下の整数に対し、forever-monotonicであるものを列挙しておく。
その後、d(y)がforever-monotonicとなるmonotonicなy≧xの最小値を求めよう。
下の桁からyをインクリメントしていき、そのつどより下の桁を調整することでd(y)がforever-monotonicなるようにすればよい。

yが定まったら、111....111に対し、下の桁から(y-x)だけインクリメントしていこう。(その際、各桁は9より大きくしてはならない)
すると、答えは111.....11x9999のように、prefixが1、suffixが9で間に1桁だけそれ以外の数字が入る場合もある、という値になる。
この値を998244353で割った余りを取ればよい。

int T;
ll N;
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


int ok[10100];

int ismono(int x) {
	int cur=9;
	while(x) {
		if(x%10>cur) return 0;
		cur=x%10;
		x/=10;
	}
	return 1;
}
int reduce(int x) {
	int cur=0;
	while(x) {
		cur+=x%10;
		x/=10;
	}
	return cur;
}
int reduce(string x) {
	int cur=0;
	FORR(c,x) cur+=c-'0';
	return cur;
}
	

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=10000;i++) {
		x=i;
		while(x>=10) {
			if(!ismono(x)) break;
			x=reduce(x);
		}
		ok[i]=ok[i-1]+(x<=9);
	}
	
	
	cin>>T;
	while(T--) {
		cin>>N;
		N++;
		string s=to_string(N);
		FOR(i,s.size()-1) if(s[i+1]<s[i]) {
			for(j=i+1;j<s.size();j++) s[j]=s[i];
		}
		
		while(ok[reduce(s)]-ok[reduce(s)-1]==0) {
			int cur=reduce(s);
			int add=0;
			for(i=s.size()-1;i>=0;i--) if(s[i]!='9') {
				string s2=s,s3=s;
				for(j=i;j<s.size();j++) {
					s2[j]=s[i]+1;
					s3[j]='9';
				}
				x=reduce(s2);
				y=reduce(s3);
				
				if(ok[y]-ok[x-1]) {
					s[i]++;
					for(j=i;j<s.size();j++) s[j]=s[i];
					break;
				}
			}
			if(i==-1) {
				s=string(s.size()+1,'1');
			}
		}
		ll N2=atoll(s.c_str());
		ll ret=(modpow(10,N)+mo-1)*modpow(9)%mo;
		ll d=(N2-N)/8;
		ret+=(modpow(10,d)+mo-1)*modpow(9)%mo*8%mo;
		ret+=modpow(10,d)*((N2-N)%8);
		ret%=mo;
		cout<<ret<<endl;

		
		
		
	}
}

まとめ

解法は割とすぐ思いつけたけど、詰めるのに手間取った。