Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎报名第四届北京大学游戏对抗邀请赛!

Re:表示这题DP 30行搞定,不会排列组合也能做。

Posted by God_Neptune_Poseidon at 2015-10-22 08:57:05 on Problem 3252
In Reply To:表示这题DP 30行搞定,不会排列组合也能做。 Posted by:lydliyudong at 2011-07-23 17:26:23
var
  a:array[0..31,0..31] of longint;
  b:array[0..31] of longint;
  a1,a2,j,i:longint;

function  solve(k:longint):int64;
var
  t,tt,i,j,temp:longint; ans:int64;
begin
  t:=1; tt:=0; ans:=0;
  while (k>0) do
    begin
      b[tt]:=k and 1;
      inc(tt); k:=k shr 1;
    end;
  for i:=tt-1 downto 1do
    for j:=(i+1) shr 1 to i-1 do ans:=ans+a[i-j-1,j];
  for i:=tt-2 downto 0 do
    if b[i]>0 then
      begin
        temp:=t-(tt-1-i-t)-1;
        j:=0;
        if (temp+i+1) div 2>0 then j:=(temp+i+1) div 2;
        while j<=i do
          begin
            ans:=ans+a[i-j,j];
            inc(j);
          end;
        inc(t);
      end;
  exit(ans);
end;

begin
  for i:=0 to 31 do
    for j:=0 to 31 do
     begin
       a[i,0]:=1; a[0,i]:=1;
     end;
  for i:=1 to 31 do
    for j:=1 to 31 do
      a[i,j]:=a[i-1,j]+a[i,j-1];
  readln(a1,a2);
  writeln(solve(a2+1)-solve(a1));
end.



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator