tenshi_kanade's blog

By tenshi_kanade, 9 years ago, In English

258B - Little Elephant and Elections is driving me crazy!

I am getting WA in Test 3.

The problem statement states that the lucky digits in the Elephant's party must be strictly larger than the total number of lucky digits in all the other 6 parties. In that case, m = 47. Let Ci be the number of numbers with i lucky digits in the range [1, m]. For m = 47, C0 = 31, C1 = 14 and C2 = 2. Then the possible assignments are...

  • The elephant's party gets one of the 2 numbers from C2, then either one of the other 6 parties gets a number from C1 and the other 5 parties get numbers from C0, or all the 6 parties get numbers from C0. Then the assignments are 2 * 14 * 31 * 30 * 29 * 28 * 27 + 2 * 31 * 30 * 29 * 28 * 27 * 26 = 1631145600.
  • The elephant's party gets one of the numbers from C1, then all of the other 6 parties must get numbers from C0. In this case, the assignments are 14 * 31 * 30 * 29 * 28 * 27 * 26 = 7421712480.

This means the total number of correct assignments is 1631145600 + 7421712480 = 9052858080. This number modulo 109 + 7 is 52858017.

Then my question is: Where the hell is my reasoning wrong? Cause the answer seems to be 907362803.

I'll be grateful to any kind soul willing to enlighten me.

UPDATE: I figured it out. I was failing to consider the order of political parties. Thanks for opening my post anyway, and please don't downvote.

  • Vote: I like it
  • +13
  • Vote: I do not like it