Product of Products of elements of all subsequences of length k of an array

Question

I have been given an array of length of n. I have to find the product of products of elements of all subsequences of length k.

For e.g

Array -> [1,2,3,4] n=4,k=2

Subsequences -> {1,2} {1,3} {1,4} {2,3} {2,4} {3,4}

Products -> 2 3 4 6 8 12

Product of products 2*3*4*6*8*12 = 13824

It can be done easily if n & k are small but I am not able to get the result when 1<=n<=2000, 1<=k<=n. The answer can be too large so we can give the answer modulo 1000000007. Can someone tell me how to do it for large n & k?

In your example: 13824 = 1 ** 3 * 2 ** 3 * 3 ** 3 * 4 ** 3 (** means to the power of) — Thomas Sablik, Jul 12 '18 at 07:29
@user202729 Welcome to the question. it's change since I posted the first comment. The closing sentence added, it has merit (and plenty of duplicates, [such as this one](https://stackoverflow.com/questions/12235008/how-to-find-muliplication-of-large-numbers-modulo-100000007) ). — WhozCraig, Jul 12 '18 at 07:57
@WhozCraig the link tells how to multiply two big numbers modulo a prime..but how to multiply 2*2*2*......2 , 123456789561234563141515 times modulo a prime which can not be stored in any data type? — Rahul Asnani, Jul 12 '18 at 08:37

Thomas Sablik · Answer 1 · 2018-07-12T07:42:47.447

1

Product of products means the same as product: (a_1 * a_2) * (a_3 * a_4) = a_1 * a_2 * a_3 * a_4.

Product of products of subsequences can be efficiently calculated with power: (a_1 * a_2) * (a_1 * a_3) * (a_2 * a_3) = a_1 * a_1 * a_2 * a_2 * a_3 * a_3 = a_1 ** 2 * a_2 ** 2 * a_3 ** 2

Find n the number of subsequences, containing the first element. Then calculate each element (a_i ** n = a'_i) to the power of n. Then calculate the product of all a'_i.

Also for (a * a * a) % b = ((((a* a) % b) * a) % b)

and

(a *b )%c = ((a%c) * (b%c))%c

edited Jul 12 '18 at 07:42

answered Jul 12 '18 at 07:34

Thomas Sablik

16,127
7
34
62

I tried to do it that way,the power will be (n-1)C(k-1) (combinations).But when n & k are too large, the power will be too large to handle. – Rahul Asnani Jul 12 '18 at 07:41
As Yksisarvinen said: (a*b)%c = ((a%c) * (b%c))%c – Thomas Sablik Jul 12 '18 at 07:44
OK! Let's say n=2000 & k=1000 so number of subsequences containing the first element will be (1999)C(999) (fixing the first element and selecting other k-1 elements). Now this power can not be stored in any standard data type. Now? – Rahul Asnani Jul 12 '18 at 07:55
You have to calculate the power by yourself: (2000 * 2000 * 2000 * 2000) % 1000000007 = ((8000000000 % 1000000007) * 2000) % 1000000007 = (999999951 * 2000) % 1000000007 = 999888007 – Thomas Sablik Jul 12 '18 at 08:07
I know the use of modulus. I have to multiply 2000, (1999)C(999) times but how do I get (1999)C(999) (nCr)as it is too large. – Rahul Asnani Jul 12 '18 at 08:18

score 1 · Accepted Answer · answered Jul 12 '18 at 08:45

More hints:

Fermat's little theorem states (with ^ denotes explanation)

n^(p-1) ≡ 1 (mod p) for all prime p and n coprime with p.

Therefore, n^x ≡ n^(x mod (p-1)) (mod p)

Now use Pascal's triangle or anything that may help computing x mod (p-1).

Product of Products of elements of all subsequences of length k of an array

2 Answers2