https://ac.nowcoder.com/acm/problem/20203

大佬原帖：

https://www.cnblogs.com/acceptedzhs/p/solution-p5261.html

%%%% tql 写了点注释

#include <iostream>
#include <bitset>
#include <algorithm>
#include <vector>
#define int long long

using namespace std;

const int N = 110, S = 1010;

int k, s, p, d;
bitset<S> f[N][S][11];

void Init()
{
	cin >> k >> s >> p >> d;
	f[0][0][0][0] = 1; // 定义起始状态合法
	
	// f[i][s][x][p-x], i+1<=k 
	for (int i=0;i < k;i ++ )
	{
		for (int ss=0;ss <= i*9;ss ++ )		// 枚举原数数位和
		{ 
			for (int x=0;x <= 9;x ++ ) 		// 枚举进位 x 
			{
				for (int j=(i==k-1);j <= 9;j ++ ) 	// 枚举放的数 j 
				{
				//	if (!j && i+1 == k) continue ;	// 前导零
					
					/*
						f[i+1][s+j][sum/10][p + sum%10] += f[i][s][x][p];
						最高位以前的0没有意义，所以可以用 bitset 直接异或
						如果不是？那么右移后多出长度<S>的部分会被看做零，这题没有意义，所以可以用bitset优化层 
                    	跳过枚举 p
						假设 sum%10  =3
						对于每一个 p∈[3, S]: f[][][][p] += f[][][][p - 3] 
						(题目给定后数为数不会超过 1000) 
						形如：(左边低位 
						f[p]	0111 0010 0110 0101 1000
						f[p-3]:	___1 0010 0110 0101 1000 000_ 是合法的 
						即 (0111 0010 0110 0101 1000) |= (1001 0011 0010 1100 0000)
							
						只需要考虑是否大于0即可，所以可以直接异或
					*/ 
					
					int sum = x + j * d;
					f[i+1][ss+j][sum/10] |= (f[i][ss][x] << (sum%10));
				}
			}
		}
	}
}

signed main()
{
	cin.tie(0) -> sync_with_stdio(0);

	/*
		f[i][s][x][p] 
    	从低到高第几位、原数的各数位和、原数乘D后第一位是什么、原数乘D后除了第一位后面数位的各数位和
		所以有 S = s, P = x+p
		
		枚举第i+1位的取值j，转移可以表示为
			f[i+1][s+j][(x+j*d)/10][p + (x+j*d)%10] += f[i][s][x][p]
		
		i+1, s+j 没什么好说的
		
		(x+j*d)/10 : 因为x是"原数*d"后，第i位的进位，
		假设原数为 [????] 那么原数*d可以表示为 x[????]
		考虑上第i+1位上放了j, 那么原数现在为 j[????]，乘上d就为 (j*d+x)[????]
		(j*d+x)可能为一位数，也可以为两位数，所以新的最高位的进位就是 放了j后又乘上d 最高位的进位
		即 (j*d+x)/10, 注意是除10向下取整不是模10, 假设 514 * 9 = 4626 最高位的进位是 (5*9=45)/10 = 4
		
		p+(x+j*d)%10 : 首先明确，p表示原数乘上d后，除了最高位(进位)后面各数位的和 
		记 DS(X) 表示X各数位的和，所以我们有 P = DS(num*d) = x + p, (没放j之前
		考虑第i+1放了j, 那么现在数再乘上d，除了最高位，后面的数位和可以计算
		(j*d + x)[????] -> (j*d+x)/10[(j*d+x)%10????] (这个数长成这样)
		所以就是 p + (j*d+x)%10
		 	
	*/

	Init();
	
	vector<int> ans(N); // 最多100位
	
	bool is = 0;
	for (int x=0;x <= 9 && !is;x ++ )
	{
		if (p-x >= 0 && f[k][s][x][p-x])
		{
			is = 1, p -= x;
			// "直接" 说明x合法且有解 
			// 第一次找到，则一定由解，则一定最小
			// 为什么一定有解？因为递推是从小到大递推，
			// 如果终点以后解，那么一定可以枚举出路径
			// 除了j，枚举这里就不需要考虑枚举是从小到大还是从大到小了 
			// 因为终点已经确定是最小了 
			
			
			// 从高到低, 从小到大枚举放的数 j 
			for (int i=k;i >= 1;i -- )
			{
				for (int j=(i==k);j <= 9;j ++ )
				{
					/*
						贪心策略
						从高位到低位，放的j从小到大，枚举
						最高位肯定不能是零 否则其他可以是0 
					*/
					
				//	if (!j && i == k) continue ; // 前导零
					
					for (int rx=0;rx <= 9;rx ++ )
					{
						int sum = rx + j*d, nowSum = s - j;
						
						if (nowSum < 0 || sum/10 != x) continue ;
						/*
							因为 f[i+1][s+j][sum/10][p + sum%10] += f[i][s][x][p];
							nowP = p - sum%10
						*/
						int nowP = p - sum%10;
						// f[i+1][s+j][sum/10][p + sum%10] += f[i][s][x][p]
						if (nowP < 0 || !f[i-1][nowSum][rx][nowP]) continue ;
			
						// 找到一个合法的路径 
                        // 因为推出 f[i-1] 合法，说明一定有起点
						// 不需要像递归搜索那样需要反悔 
						ans[i] = j, x = rx, s = nowSum, p = nowP; // 根据路径递推回去 
						
						goto anchor;
					}
				}
				
				anchor: ;
			}
		}
	}
	
	
	if (!is) return cout<<-1, 0;
	
	for (int i=k; i;i -- ) putchar(ans[i] + '0'); 
	
	return 0;
}