not understanding this problem

[CodeMonkey2000]

Actually I think there is a formula, and I think it is something like:

{2^(n-1)^2 + n^[(n+1)%2] }%98777

[Tony]

n = 1
{2^(n-1)^2 + n^[(n+1)%2] }%98777
{2^(1-1)^2 + 1^[(1+1)%2] }%98777
{2^(0)^2 + 1^[(2)%2] }%98777
{1 + 1^[0] }%98777
= 2

But there is only 1 possibility

[*]

[Analysis Mode]

special case?

[saltpro15]

I don't like this question I'm trying a shortest-path one now, i'll let you guys work on this one :p

[DanielG]

codemonkey, how did you come up with the formula? or, if you found it, where did you find it?

[bbi5291]

Actually, CodeMonkey2000's formula is very close... work out some small cases, and you should see a pattern emerge it's not an excessively difficult problem, at least it is very easy to code.

[CodeMonkey2000]

DanielG @ Sun Apr 12, 2009 9:26 am wrote:

codemonkey, how did you come up with the formula? or, if you found it, where did you find it?

2^(n-1)^2 is the number of (n-1) matrices you can have.The last column and last row needs to be fixed to accommodate the restrictions, and there are n ways if n is even and 0 ways if n is odd. The last part should be n*[(n+1)%2], that was a typo; my bad That formula will give you 17 solutions when N=3

I was trying to do the problem last night, and tried to find a DP solution, but instead found a possible formula. It made sense to me last night .

{2^(n-1)^2 + n*[(n+1)%2] }%98777 I think this is right, though I don't feel like coding up the solution, or signing up to the judge to verify. Someone should code a brute force solution, and verify the formula.

[bbi5291]

I thought it was clear from my previous post that this formula, while close, is not quite correct.