ABC114 C問題 : 755

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n;
const array<int, 3> add = {3, 5, 7};

int Solve(ll x, char flag) {
    if (n < x) return 0;

    int res = (flag == 7);
    for (int i = 0; i < 3; ++i)
        res += Solve(10 * x + add[i], flag | (1 << i));
    return res;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cin >> n;
    cout << Solve(0, 0) << endl;;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

// dp[i][j][k][l] := i: 上位 i 桁目まで決定，j: 数字を自由に選べるか,
//                   k: 数字を書き込んだか，l: {3,5,7} を選んだかのflag
//                   としたときの753数の数
int dp[11][2][2][8];

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    string n;
    cin >> n;

    int len = n.size();
    dp[0][0][0][0] = 1;
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                for (int l = 0; l < 8; ++l) {
                    if (!dp[i][j][k][l]) continue;

                    if (j == 1) { // [0, 9] から数字を選べる
                        if (k == 0) // 数字をまだ書き込んでいない
                            dp[i + 1][1][0][0] += dp[i][j][k][l]; // nothing

                        dp[i + 1][1][1][l | 1] += dp[i][j][k][l]; // +3
                        dp[i + 1][1][1][l | 2] += dp[i][j][k][l]; // +5
                        dp[i + 1][1][1][l | 4] += dp[i][j][k][l]; // +7
                    }
                    else { // [0, d] から数字を選べる
                        int d = (int)(n[i] - '0');

                        if (k == 0) // 数字をまだ書き込んでいない
                            dp[i + 1][1][0][0] += dp[i][j][k][l]; // nothing

                        if (d == 3) dp[i + 1][0][1][l | 1] += dp[i][j][k][l]; // +3
                        if (3 < d) dp[i + 1][1][1][l | 1] += dp[i][j][k][l]; // +3
                        if (d == 5) dp[i + 1][0][1][l | 2] += dp[i][j][k][l]; // +5
                        if (5 < d) dp[i + 1][1][1][l | 2] += dp[i][j][k][l]; // +5
                        if (d == 7) dp[i + 1][0][1][l | 4] += dp[i][j][k][l]; // +7
                        if (7 < d) dp[i + 1][1][1][l | 4] += dp[i][j][k][l]; // +7
                    }
                }
            }
        }
    }

    int ans = dp[len][0][1][7] + dp[len][1][1][7];
    cout << ans << endl;

    return 0;
}