vector<vector<int64_t>> sequence = {
  {1,1,1,1,1,1,1,1,1,1,1,1},
  {1,0,2,0,4,0,8,0,16,0,32,0},
  {1,2,6,14,37,92,236,596,1517,3846,9770,24794}, // next is 62953
  {1,0,14,0,154,0,1696,0,18684,0,205832,0}, // next is 2267544
};

The solution is a linear recurrence. Output is multiplied by 2.

Edited by author 16.01.2020 16:32

can any1 tell me what is solution for 4x4,4x5 and 4x6, also some hints would be nice :D
Thanks

Can any one please help me to solve it?

Please, give me test 12. Very need.

I spend two long nights to solve this problem. NICE problem! :)
Now, maybe I understand what is "profil dp". I think it is such dp when you are coding each possible position in problem by some rule and then try to find dependence between them.

Good Luck for All ;)

What is the answer for test 3x5

There are exists tests with m=10^9 ( for example, test #6), but in problem's statement m<10^9. Please correct problem's statement or remove these tests.

On the 6th test(((
why???const
  c=1000000000;
var
  n,m:longint;
  i,j:longint;
  d:longint;
  boo:boolean;
  answer:array[2..5,2..10000000] of byte;
begin
read(n,m);
if (n mod 2 =1) and (m mod 2 =1) then
  begin
   answer[n,m]:=0;
   boo:=true;
  end;
 if n>m then
     begin
      d:=n;
      n:=m;
      m:=d;
     end;
 if n=2 then
        answer[n,m]:=2
        else
           if ((n=3)  and (m mod 2=1)) then
                                         begin
                                          answer[n,m]:=0;
                                         end
                                      else
                                        if ((n=3)  and (m mod 2=0)) then
                                            begin
                                              answer[n,m]:=4;
                                            end



      else
        if (n>3) and (boo<> true)then
           begin
            for i:=2 to m do
             begin
               answer[2,i]:=2;
             end;
              for i:=2 to n do
               begin
                 answer[i,2]:=2;
               end;
              for i:=3 to n do
                for j:=3 to m do
                begin
                  if (i mod 2 =1) and (j mod 2=1) then
                        begin
                         answer[i,j]:=0
                        end
                                                  else
                        begin
                        answer[i,j]:=2*(answer[i-1,j]+answer[i,j-1]);
                         if i=j then
                         begin
                          answer[i,j]:=answer[i,j]-answer[i,j-1];
                         end
                       end;
                end;
           end;
 write(answer[n,m]);
end.

Edited by author 12.08.2006 19:01