In this HackerRank Bead Ornaments problem solution, All beads are distinct, even if they have the same color. Two ornaments are considered different if two beads are joined by a thread in one configuration, but not in the other. How many different ornaments can be formed using this algorithm? Return the answer modulo 10 to power 9 plus 7.
Problem solution in Python.
#!/bin/python3 import os import sys from functools import reduce from operator import mul # # Complete the beadOrnaments function below. # def beadOrnaments(b): return int((reduce(mul, map(lambda x: x ** (x - 1), b), 1) * (sum(b) ** (len(b) - 2))) % ((10 ** 9) + 7)) if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') t = int(input()) for t_itr in range(t): b_count = int(input()) b = list(map(int, input().rstrip().split())) result = beadOrnaments(b) fptr.write(str(result) + 'n') fptr.close()
Problem solution in Java.
import java.math.*; import java.util.*; public class Solution { static Scanner in; static int n; static final BigInteger two = new BigInteger("2"); static BigInteger [] numWays = new BigInteger[32]; static BigInteger [] freqs = new BigInteger[10]; static BigInteger [] cumfreqs = new BigInteger[1024]; static BigInteger [] memo = new BigInteger[1024]; static int [] count = new int[1024]; public static BigInteger getWays (int mask) { if (memo[mask].compareTo(BigInteger.ZERO) > 0) return memo[mask]; BigInteger ans = BigInteger.ZERO; for (int mask1 = 1; mask1 < mask; mask1 ++) { if ((mask1 & mask) != mask1) continue; int mask2 = mask - mask1; ans = ans.add(getWays(mask1).multiply(getWays(mask2).multiply(cumfreqs[mask1].multiply(cumfreqs[mask2])))); } ans = ans.divide(two.multiply(new BigInteger(Integer.toString(count[mask])).subtract(BigInteger.ONE))); return memo[mask] = ans; } public static void solve () { n = in.nextInt(); for (int i = 0; i < (1 << n); i ++) memo[i] = BigInteger.ZERO; for (int i = 0; i < n; i ++) { int k = in.nextInt(); memo[1 << i] = numWays[k]; freqs[i] = new BigInteger(Integer.toString(k)); } for (int i = 0; i < (1 << n); i ++) { cumfreqs[i] = BigInteger.ZERO; count[i] = 0; for (int j = 0; j < n; j ++) { if (((i >> j) & 1) > 0) { cumfreqs[i] = cumfreqs[i].add(freqs[j]); count[i] ++; } } } System.out.println(getWays((1 << n) - 1).mod(new BigInteger("1000000007")).toString()); } public static void main (String [] args) { in = new Scanner(System.in); numWays[0] = BigInteger.ZERO; numWays[1] = numWays[2] = BigInteger.ONE; for (int i = 3; i < 32; i ++) numWays[i] = new BigInteger(Integer.toString(i)).pow(i - 2); int nC = in.nextInt(); for (int i = 0; i < nC; i ++) solve(); } }
Problem solution in C++.
#include "cassert" #include "iostream" #include "algorithm" #include "vector" const int MOD = 1000000007; int bitcount(int mask) { int cnt = 0; while(mask > 0) { mask &= mask-1; ++cnt; } return cnt; } long long pow(int a, int n) { if (n < 0) { return pow(pow(a, MOD - 2), -n); } if (n == 0) { return 1; } if (n == 1) { return a; } long long res = pow(a, n/2); res = res * res % MOD; if (n & 1) { res = res * a % MOD; } return res; } long long total_ways_dp(const std::vector<int>& beads) { int n = beads.size(), ALL = (1<<n) - 1; std::vector<int> beads_sum(1<<n); std::vector<long long> ways(1<<n); // // dp[mask] = sum{dp[submask_a] * dp[submask_b] * beads[mask_a] * beads[mask_b]} for (int mask = 1; mask <= ALL; ++mask) { int k = 0, m = bitcount(mask), submask = (mask-1)&mask; while(k < n && (mask&(1<<k)) == 0) { ++ k; } beads_sum[mask] = beads_sum[submask] + beads[k]; // only consider the last node! if (m == 1) { // single node ways[mask] = pow(beads[k], beads[k] - 2); } else { for (int mask_a = (mask-1)&mask, mask_b; mask_a > 0; mask_a = (mask_a-1) & mask) { mask_b = mask - mask_a; ways[mask] = (ways[mask] + ways[mask_a] * ways[mask_b] % MOD * beads_sum[mask_a] * beads_sum[mask_b]) % MOD; } // overcount // ways[mask] /= 2(m-1); ways[mask] = ways[mask] * pow(2*(m-1), MOD-2) % MOD; } } return ways[ALL]; } int main() { int T, n; for (std::cin >> T; T-- && std::cin >> n; ) { std::vector<int> beads(n); for (auto& e : beads) { std::cin >> e; } std::cout << total_ways_dp(beads) << std::endl; } return 0; }
Problem solution in C.
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #define M 1000000007 int main() { int t,n,i; scanf("%d",&t); while(t--) { long long res=1,s=0,b,a; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%lld",&b); s+=b; for(a=1;a<b-(n==1);a++)res=(res*b)%M; } for(i=2;i<n;i++)res=(res*s)%M; printf("%lldn",res); } return 0; }
How do you solve this problem using JavaScript? At least, what is the mathematical formula for getting the number of output?