tag:blogger.com,1999:blog-1953325079793449971.post9018580287490348447..comments2024-09-20T21:17:15.980+02:00Comments on Algorithms Weekly by Petr Mitrichev: TopCoder Open 2010 Algorithm Wildcard RoundPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-1953325079793449971.post-74517089681456269722010-10-17T10:52:36.699+02:002010-10-17T10:52:36.699+02:00I'm sorry I wasn't clear enough here :)
S...I'm sorry I wasn't clear enough here :)<br /><br />Suppose we're looking at the sum<br />combinations[n-k*r][r] over all r of form r=p*x+c, where c is fixed. This gets us:<br /><br />sum(combinations[n-k*(p*x+c)][p*x+c])=sum(combinations[n-k*p*x-k*c][p*x+c])=(by Lucas' theorem) sum(combinations[(n-k*c) div p-k*x][x]*combinations[(n-k*c) mod p][c])=sum(combinations[(n-k*c) div p-k*x][x])*combinations[(n-k*c) mod p][c].<br /><br />The second multiplier doesn't depend on x, and has both parameters less than p. The first multiplier, a sum, almost doesn't depend on c - more precisely, we have at most k such sums (since k*c is between 0 and k*p, so this gets reduced to between 0 and k when divided by p).<br /><br />You can take a look at bmerry's solution in the practice room for an implementation.Petr Mitrichevhttps://www.blogger.com/profile/00138130656174416711noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-51757223726739629842010-10-17T05:23:51.719+02:002010-10-17T05:23:51.719+02:0019:44 â€“ bmerry suggests we can avoid the matrix mu...<i>19:44 â€“ bmerry suggests we can avoid the matrix multiplication by grouping the râ€˜s which are the same modulo p and applying the above theorem about the number of combinations to each of those sums.</i><br /><br />Is it true? Even though the r have the same modulo p. Lucas' theorem does not just use the modulo of the number but the p-ary representation, I am not sure if the p-ary representations will be the same for any two different rs that are equal modulo p.vexoriannoreply@blogger.com