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.

HackerRank Bead Ornaments problem solution


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()

{"mode":"full","isActive":false}


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

{"mode":"full","isActive":false}


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

{"mode":"full","isActive":false}


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("%lld\n",res);
    }
    return 0;
}

{"mode":"full","isActive":false}