ivplay's blog

By ivplay, 7 years ago, In English

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2767

I am stuck on this problem. I can't formulate the recurrence relation exactly. Can anybody help me to formulate the recurrence relation,please? I can think of three state recurrence f(n,k,largest) = how many was we can express n as sum of k distinct integers where none of the integers is greater than largest. If somehow I could compress the last state(largest) by a and k , I could use matrix exponentiation. But how can I eliminate this state?

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