anyone can help me at this problem? i can't understand the editorial's solution with fenwick tree.

Hi, this is my first blog and i apologize first of all for my English :/

recently i solved a problem and i was able to learn a little trick that i would like to share.

given an integer n that means the number of groups(this groups have a number ai of things inside him), count the number of combinations of the elements of these groups. you can choose between place or don't place an element of a group.

Example:

three groups and 2,1 and 3 at the first,second and third groups respectively

n = 3
groups = [ {ball,apple}, {pineapple}, {pen} ]

the task is, how many combinations are possible with these elements using only one or no element from each group? the answer...

• []
• [ball]
• [apple]
• [pineapple]
• [pen]
• [ball, pineapple]
• [ball, pen]
• [apple, pineapple]
• [apple, pen]
• [pineapple, pen]
• [ball, pineapple,pen]
• [apple, pineapple, pen]

12 in total

this can be easily calculated, using combinatorics.

the first question is, how many combinations can we have for each set, the answer is the number of elements of the group + 1 (this one means not using the element). in the example above, we have 3, 2 and 2 combinations respectively for the each group of the array.

to calculate the number of combinations, of these groups, we need multiply the combinations of each group. that is, the answer to the array above is.

3 * 2 * 2 = 12

thanks for read. I hope this helps for the next contests :D