Блог пользователя pulkitmehta

Автор pulkitmehta, история, 8 лет назад, По-английски

Hello !

I have been trying to solve a problem but I am not able to solve it.

Problem Statement : Find the number of strings of length “N” made up of only 3 characters – a, b, c such that “a” occurs at least “min_a” times and at most “max_a” times, “b” occurs at least “min_b” times and at most “max_b” times and “c” occurs at least “min_c” times and at most “max_c” times. Note that all permutations of same string count as 1, so “abc” is same as “bac”.

Constraints

1<=T<=1000 1<=N<=10^9 1<=min_a<= max_a<=10^9 1<=min_b<= max_b<=10^9 1<=min_c<= max_c<=10^9

Problem Link on spoj : LINK

Please provide some hints !

Thanks !

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

If I understand problem statement correct, you are asked to find number of integer solutions of equation a + b + c = n with limitations on a, b and.c.

First, let’s solve the problem when there are no upper limit for variables. We can transform equation to a1 + b1 + c1 = n1, where a1 = a - amin, a1 ≥ 0, b1 = b - bmin, b1 ≥ 0, c1 = c - cmin, c1 ≥ 0, n1 = n - amin - bmin - cmin. There are C(n1 + 2, 2) ways to choose nonnegative values for a1, b1, c1.

Now notice that you can solve original equation using inclusion-exlusion principle.