Official

C - Product Editorial by sugarrr


DFS (深さ優先探索) で解くことができます。

DFS は初めのうちは実装が難しいかもしれないので、下に示した実装例も参考にしてください。

また、計算途中のオーバーフローに気をつけましょう。

C++ による解答例

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

ll ans = 0;
ll n,x;
vector<vector<ll>>a;
void dfs(ll pos,ll seki){
    if(pos==n){
        if(seki == x)ans++;
        return;
    }
    for(ll c:a[pos]){
        if(seki>x/c)continue;
        dfs(pos+1,seki*c);
    }
}

signed main(){
    cin>>n>>x;
    a.resize(n);
    for(ll i=0;i<=n-1;i++){
        ll L;cin>>L;
        a[i].resize(L);
        for(ll j=0;j<=L-1;j++)cin>>a[i][j];
    }
    dfs(0,1);
    cout<<ans<<endl;
    return 0;
}

posted:
last update: