数位dp练习

1. 求前$n$个数中有多少数位和为$x$的数

ll dfs(int len, int sum, bool z, bool lim) {
	if (sum>x) return 0;
	if (!len) return sum==x;
	if (!lim&&!z&&~dp[len][sum]) return dp[len][sum];
	ll ans = 0;
	int mx = lim?a[len]:9;
	REP(i,0,mx) ans+=dfs(len-1,sum+i,z&&!i,lim&&i==mx);
	return !lim&&!z?dp[len][sum]=ans:ans;
}

ll solve(char *s) {
	int len = strlen(s);
	REP(i,1,len) a[i]=s[len-i]-'0';
	return dfs(len,0,1,1);
}

int main() {
	scanf("%s%d", s, &x);
	memset(dp,-1,sizeof dp);
	printf("%lld
", solve(s));
}

2. 求第$k$个数位和为$x$的数.

const int N = 30;
ll dp[N][N], sum[N][N];
int main() {
	dp[0][0] = 1;
	REP(i,0,N-1) sum[0][i] = 1;
	REP(i,1,N-1) {
		REP(j,0,N-1) dp[i][j] = sum[i-1][j]-(j>=10?sum[i-1][j-10]:0);
		REP(j,0,N-1) sum[i][j] = (j?sum[i][j-1]:0)+dp[i][j];
	}
	ll x, k;
	scanf("%lld%lld", &k, &x);
	ll ans = 0;
	PER(i,1,N-1) {
		int j = 0;
		while (dp[i-1][x-j]<k) k-=dp[i-1][x-j++];
		x -= j;
		ans = ans*10+j;
	}
	printf("%lld
", ans);
}