非常有意思的一道题，为什么题解里面没有一个用递归做的，我们需要找到最小的 $n$ 位数的数位和为 $s1$ 且它乘 $d$ 以后的数位和为 $s2$。

我们考虑枚举它乘 $d$ 后的数，设计dp状态为 $f_{dep,d1,d2,lst}$ 表示还剩 $dep$ 位没填，该数的数位和还差 $d1$，$d$ 倍的该数的数位和还差 $d2$，模 $d$ 的余数为 $lst$。那么结束的状态就是 !d1&&!d2&&!lst 表示数位和恰好为 $s1,s2$ 且是 $d$ 的倍数，使用除法来推出它原本的数，详细见代码部分。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+5;
ll n,s1,s2,d,ans[N];
bitset<915> f[101][905][11];
void dfs(int dep,int d1,int d2,int lst){
	if(d1<0||d2<0||d1>dep*9||d2>dep*9) return ;
	if(dep==0){
		if(!d1&&!d2&&!lst){
			for(int i=n;i>=1;i--) cout<<ans[i];
			exit(0);
		}
		return ;
	}
	if(f[dep][d1][lst][d2]) return ;
	f[dep][d1][lst][d2]=1;
	for(int k=lst*10;k<lst*10+10;k++){
		int i=k/d,j=k%d;
		ans[dep]=i;
		dfs(dep-1,d1-i,d2-k%10,j);
	}
}
inline ll calc(ll x){
	ll res=0;
	while(x) res+=x%10,x/=10;
	return res;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
	cin>>n>>s1>>s2>>d;
	for(int i=1;i<=9;i++){
		for(int j=0;j<d;j++){
			ans[n]=i;
			dfs(n-1,s1-i,s2-calc(i*d+j),j);
		}
	}
	puts("-1");
	return 0;
}

开局先枚举原本的数的开头与模 $d$ 的余数，保证不包含前导零，时间复杂度 $O(10 \times KSP)$。