pds solution

#include <bits/stdc++.h>
 
#define ll long long
 
using namespace std;
 
int n;
ll re,pos,v,cur,curNxt,res;
ll dp[11][101][101][101];//digits,div,remain
int s[27];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("sodps.inp", "r", stdin);
	freopen("sodps.out", "w", stdout);
    cin >> n;
 
    for(int i = 1; i < 101; i++)
        dp[0][0][i][0] = 1;
 
    re = 0;
    for(pos = 0; pos < 11; pos++) {
        for(int v = 1; v < 10; v++)
        for(int su = 0; su <= (pos-1)*9; su++) {
            for(int md = 1; md < 101; md++)
            if (su+v == 0) dp[pos][0][md][0] = 1;
            else for(int rm = 0; rm < md; rm++) dp[pos][su+v][md][((pos == 1 ? 1 : rm)*v)%md] += dp[pos-1][su][md][rm];
        }
        for(int su = 1; su <= pos*9; su++) re += dp[pos][su][su][0];
        if (re >= n) break;
        else cur = re;
        int v = 0;
        for(int su = 0; su <= (pos-1)*9; su++) {
            for(int md = 1; md < 101; md++)
            if (su+v == 0) dp[pos][0][md][0] = 1;
            else for(int rm = 0; rm < md; rm++) dp[pos][su+v][md][((pos == 1 ? 1 : rm)*v)%md] += dp[pos-1][su][md][rm];
        }
    }
    ll psu = 0, pmt=1;
    for(int p = pos; p >= 1; p--)
        for(int v = (p==pos ? 1 : 0); v < 10; v++) {
            curNxt = cur;
            for(int su = 0; su <= (p-1)*9; su++) {
                int md = psu+su+v;
                for(int rm = 0; rm < md; rm++)
                    if (((p == 1 ? 1 : rm)*pmt*v)%md == 0) curNxt += dp[p-1][su][md][rm];
            }
            if (curNxt >= n) {
                res = res*10+v;
                psu += v;
                pmt *= v;
                break;
            }
            else cur = curNxt;
        }
 
    cout << res;
 
    return 0;
}