HackerRank Bead Ornaments problem solution

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;
}