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: