Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 表示这题DP 30行搞定，不会排列组合也能做。

Posted by lydliyudong at 2011-07-23 17:26:23 on Problem 3252 and last updated at 2011-07-23 17:27:32
```f[i,j]表示二进制下一共i位，有j位是0的数的个数。
d[i,j]表示二进制下一共i位，有>=j位是0的数的个数。

∑d[i-1,(i+1)/2]（1<=i<=a-1），其中第一位必须是1。

var
f,d:array[0..32,0..32]of int64;
s,e,a,b,i,j,k,ans:longint;
function calc(s,a:longint):longint;
begin
calc:=0;
for i:=1 to a-1 do inc(calc,d[i-1,(i+1)>>1]);
k:=0;
for i:=a-2 downto 0 do
if (s>>i)and 1=1 then
begin
j:=(a+1)>>1-k-1;
if j<0 then j:=0;
inc(calc,d[i,j]);
end
else inc(k);
end;
begin
for i:=0 to 31 do f[i,0]:=1;
for i:=1 to 31 do
for j:=1 to i do
f[i,j]:=f[i-1,j]+f[i-1,j-1];
d[0,0]:=1;
for i:=1 to 31 do
for j:=i downto 0 do
d[i,j]:=d[i,j+1]+f[i,j];
inc(e);
while s>>a<>0 do inc(a);
while e>>b<>0 do inc(b);
writeln(calc(e,b)-calc(s,a));
end.```

Followed by: