mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 052 D - 9

解法

K の値に応じて場合分けします。

K が小さい場合は, 桁dp で解けます。よくある dp[桁][あまりの差][smallFlag] ってやつです。

K が大きい場合は, 各桁の和がせいぜい 100 であることを利用します。すると, 解の候補は i*K+j (i*K+j <= M, 0 <= j <= 100) を調べれば良いだけなので十分時間内に間に合います。

const int S = 100000;

int calc(ll x) {
	int ret = 0;
	while (x) {
		ret += x%10;
		x /= 10;
	}
	return ret;
}

// 桁, あまり, flag
ll dp[20][S][2];
int p10[20];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll K, M;
    cin >> K >> M;
    ll ans = 0;
    if (K >= S) {
    	for (int i = 0; i*K <= M; i++) {
    		for (int j = 0; j < 100 && i*K+j <= M; j++) {
    			ll tmp = i*K+j;
    			if (calc(tmp) == tmp%K) ans++;
    		}
    	}
    } else {
    	p10[0] = 1;
    	for (int i = 1; i < 20; i++) p10[i] = (p10[i-1]*10) % K;
    	string s = to_string(M);
    	int n = s.size();
    	dp[0][0][0] = 1;
    	for (int keta = 0; keta < n; keta++) for (int q = 0; q < K; q++) for (int flag = 0; flag < 2; flag++) {
    		if (!dp[keta][q][flag]) continue;
    		for (int i = 0; i < 10; i++) {
    			if (!flag && i > s[keta]-'0') continue; 
    			int nq = q;
    			nq += (i*p10[n-1-keta])-i;
    			nq %= K;
    			if (nq < 0) nq += K;
    			int nflag = flag;
    			if (i < s[keta]-'0') nflag = 1;
    			dp[keta+1][nq][nflag] += dp[keta][q][flag];
    		}
    	}
    	ans = dp[n][0][0]+dp[n][0][1];
    }
    cout << ans-1 << endl;
    return 0;
}