【ABC233】 C - ProductをC++で解説

はじめに

　皆さんこんにちは！ C++で競プロ問題の解説をします！今回は ABC233 A, B です！

少しでも役に立ったらLGTMして頂けるとうれしいです！

わからないことなどあれば下のコメントやTwitterからお願いいたします!

C - Product

問題概要

$N$個の袋がある．袋$i$には$L_i$のボールが入っており，ボールには$a_{i, j}$が書かれている．
袋から$1$つずつボールを取り出したときの総積が$X$になるのは何通り？

制約

・$2 \leq N$
・$2 \leq L_i$
・$\prod^N_{i= 1} L_i \leq 10^5$
・$1 \leq a_{i, j} \leq 10^9$
・$1 \leq X \leq 10^{18}$
・入力はすべて整数

考察

ポイント

　全探索の方法を考えよう！

解説

$\prod^N_{i= 1} L_i \leq 10^5$よりすべての総乗を取っても十分間に合います．これより全探索の仕方を考えます．
　袋$L_i$ごとに値をとるのでグラフに表してみると，入力例1のとき

2 40
3 1 8 4
2 10 5

とみることができます．こうするとそれぞれの木の端までの総乗を求めればいいので**DFS(深さ優先探索)**で全探索することができます．

それでは実装していきましょう．

実装

DFSは関数を使って再帰で探索します．引数は今の深さの大きさvと総乗の値xです．v == Nの時に総乗の値が$X$の値とマッチしているかをみます．
　それ以外の時はxに$a_{i, j}$の値をかけます．$X$より値が大きくなったらcontinueするのを忘れないようにしましょう．

正解コード

# include <bits/stdc++.h>
using namespace std;
long long ans = 0, N, X;
vector<int> L;
vector<vector<long long>> G;

void dfs(long long v, long long x){
    if(v == N){
        if(x == X) ans++;
        return;
    }

    for(int l = 0; l < L[v]; l++){
        long long nx = x * G[v][l];
        if(nx > X) continue;
        dfs(v+1, nx);
    }
}

int main(){
    //入力
    cin >> N >> X;
    L.resize(N);
    G.resize(N);

    for(int i = 0; i < N; i++){
        cin >> L[i];
        for(int l = 0; l < L[i]; l++){
            int a;
            cin >> a;
            G[i].push_back(a);
        }
    }
    //xの初期値は 1
    dfs(0, 1);
    cout << ans << endl;
}