Yasuho_Hirose's blog

By Yasuho_Hirose, history, 2 years ago, In English

i'm doing this question: The equation x1 + x2 + ... + xk = n, where x1, x2, x3, ..., xk are positive integer variables satisfying the constraint: xi > = ci > 0. Given n, k,c1 ,c2 ,,…,ck, count the number of ways satisfy modulo MOD. ie: x1+x2+x3=7, c1=1, c2=2, c3=3, MOD=100, number of ways is 3. It's a normal question, i now it's is f(n-(k-sum_of_all(c))-1,n-1)%MOD but modular inverse (O(nlogn) solution) only satify when MOD is a prime number. And another O(n^2) solutions can't pass the time limit. Please give me hints or somethings, thank you senpai <3.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use extended euclid alorithm for calculating inverse modulo.