Submission #49382578

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll N, dp[16][130][130][130][2];
int main() {
    cin >> N;
    // 初期化
    for (int s = 1; s <= 9 * 14; s++) dp[0][s][0][0][0] = 1;

    ll pow10 = 1;
    for (int d = 0; d < 15; d ++) {
        int n = N % 10;
        for (int s = 1; s <= 9 * 14; s++) {
            for (int i = 0; i <= 9 * 14; i++) {
                for (int j = 0; j < s; j++) {
                    for (int f = 0; f < 2; f++) {
                        for (int t = 0; t < 10; t++) {
                            if (i + t > s) break;
                            int nf = 2 * n < 2 * t + f;
                            dp[d + 1][s][i + t][(pow10 * t + j) % s][nf] += dp[d][s][i][j][f];
                        }
                    }
                }
            }
        }
        N /= 10;
        pow10 *= 10;
    }

    ll ans = 0;
    for (int s = 1; s <= 9 * 14; s++) ans += dp[15][s][s][0][0];
    cout << ans << '\n';
}

Submission Info

Judge Result