PR

再帰関数 千本ノック

再帰関数を苦手としているので、練習しまとめる。

参考URL

ABC233 C問題 Product

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <atcoder/all>

#define INF (1LL<<30)

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true; }
    else return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true; }
    return false;
}

long long popcount(long long n) {
    long long ans = 0;
    for (int x = 0; x <= 60; x++) if (((n >> x) & 1) == 1) ans++;
    return ans;
}

struct TreeNode {
    std::vector<int> Children;
    bool IsVisited = false;
};

int main() {
    int N;
    long long X;
    std::cin >> N >> X;
    std::vector<std::vector<long long>> A(N, std::vector<long long>());
    for (int n = 0; n < N; n++) {
        int L;
        std::cin >> L;
        for (int l = 0; l < L; l++) {
            long long a;
            std::cin >> a;
            A[n].push_back(a);
        }
    }

    int ans = 0;
    auto func = [&](auto self, int n, long long s)->void {
        if (N <= n) {
            if (s == X) ans++;
            return;
        }

        for (int i = 0; i < A[n].size(); i++) {
            if (X < (s * A[n][i])) continue; //明らかに答えになりえないものはスキップ(オーバーフローして正解とご判定するのを防ぐ)
            self(self, n + 1, s * A[n][i]);
        }
        };

    func(func, 0, 1);
    std::cout << ans << std::endl;
}

DFSのような再帰関数で解決する。

スポンサーリンク

コメント

スポンサーリンク
タイトルとURLをコピーしました