In this HackerRank Counting, the Ways problem solution Little Walter likes playing with his toy scales. He has N types of weights. The Ith weight type has weight Ai. There are infinitely many weights of each type.
Recently, Walter defined a function, F(X), denoting the number of different ways to combine several weights so their total weight is equal to X. Ways are considered to be different if there is a type that has a different number of weights used in these two ways.
Problem solution in Python.
MOD = 10**9 + 7 def lcm(lst): ans = 1 for x in lst: ans = ans*x//gcd(ans, x) return ans def gcd(a,b): if a<b: a, b = b, a while b > 0: a, b = b, a%b return a def getsoltable(a, m, MOD=MOD): soltable = [1] + [0] * (len(a)*m-1) for x in a: oldsoltable = soltable soltable = list(soltable) for i in range(x, len(soltable)): soltable[i] = (oldsoltable[i] + soltable[i - x]) % MOD return soltable def countsols(const, soltable, lcm): offset = const % lcm pts = soltable[offset::lcm] assert len(pts) == len(a) coef = polycoef(pts) return polyval(coef, const//lcm) def polycoef(pts): coef = [] for x, y in enumerate(pts): fact = descpower = 1 for i, c in enumerate(coef): y -= descpower*c//fact descpower *= x - i fact *= i + 1 coef.append(y) return coef def polyval(coef, x): ans = 0 fact = descpower = 1 for i, c in enumerate(coef): ans += c * descpower * pow(fact, MOD-2, MOD) descpower = descpower * (x - i) % MOD fact *= i + 1 return ans % MOD n = int(input()) a = [1] + [int(fld) for fld in input().strip().split()] L, R = [int(fld ) for fld in input().strip().split()] m = lcm(a) soltable = getsoltable(a, m) print((countsols(R, soltable, m) - countsols(L-1, soltable, m)) % MOD)
Problem solution in Java.
import java.io.*; import java.math.*; import java.text.*; import java.util.*; import java.util.regex.*; public class Solution { static int MOD = 1000000007; static int N; static int[] arr; static List<Integer> listS; static int[] pSum; static int[] frec; static int sizePS; static int maxS = 100010; static int[][] memo = new int[60][maxS]; static void init() { listS = new ArrayList<Integer>(); for (int s = 1; s < (1 << N); s++){ int x = 0; for (int t = 0; t < N; t++) { if ((s & (1 << t)) > 0) { x += arr[t]; } } listS.add(x); } Collections.sort(listS); sizePS = listS.size(); pSum = new int[sizePS]; frec = new int[sizePS]; int last = listS.get(0); pSum[0] = last; frec[0] = 1; int index = 0; for(int k = 1;k < sizePS;k++) { int next = listS.get(k); if(next == last) { frec[index]++; } else { last = next; pSum[++index] = next; frec[index] = 1; } } sizePS = index+1; } static int countWays(long l, long r) { init(); int aR = recCalc(r, 0); memo = new int[60][maxS]; return (aR + MOD - recCalc(l-1, 0)) % MOD; } private static int recCalc(long l, int pos) { if(l == 0) { return 0; } int ans = 0; if((ans = memo[pos][(int) (l%maxS)]) >= 1) { return ans-1; } ans = recCalc(l/2, pos+1); for(int k = 0;k < sizePS;k++) { int a = pSum[k]; if(l >= a) { int pa = 1+recCalc((l-a)/2, pos+1); ans = (int) ((ans + (long)frec[k] * pa) % MOD); }else { break; } } memo[pos][(int) (l%maxS)] = ans+1; return ans; } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) throws IOException { BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); N = scanner.nextInt(); scanner.skip("(rn|[nru2028u2029u0085])*"); arr = new int[N]; String[] arrItems = scanner.nextLine().split(" "); scanner.skip("(rn|[nru2028u2029u0085])*"); for (int arrItr = 0; arrItr < N; arrItr++) { int arrItem = Integer.parseInt(arrItems[arrItr]); arr[arrItr] = arrItem; } String[] lr = scanner.nextLine().split(" "); scanner.skip("(rn|[nru2028u2029u0085])*"); long l = Long.parseLong(lr[0]); long r = Long.parseLong(lr[1]); int result = countWays(l, r); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); bufferedWriter.close(); scanner.close(); } }
Problem solution in C++.
#include <bits/stdc++.h> using namespace std; const long long MOD = 1e9 + 7; int n; int a[10]; long long L, R; const int N = 202000; int dp0[N]; int dp1[N]; inline void add(int &x, int y) { x += y; if (x >= MOD) x -= MOD; } long long solve(long long v) { bitset<62> s(v); memset(dp0, 0, sizeof(dp0)); dp0[0] = 1; for (int k = 0; k < 62; k++) { for (int i = 0; i < n; i++) { for (int j = N - a[i] - 1; j >= 0; j--) { add(dp0[j + a[i]], dp0[j]); } } if (s[k]) { add(dp0[0], dp0[1]); for (int i = 1; i < N - 1; i++) { dp0[i] = dp0[i + 1]; } } memset(dp1, 0, sizeof(dp1)); for (int i = 0; i < N; i++) { add(dp1[(i + 1) / 2], dp0[i]); } swap(dp0, dp1); } return dp0[0]; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; cin >> L >> R; int ans = solve(R) - solve(L - 1); if (ans < 0) ans += MOD; cout << ans << endl; }