再帰関数を苦手としているので、練習しまとめる。
参考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のような再帰関数で解決する。



コメント