得30分的同学注意一下：判断4^i*5^j<=n时可能会爆int

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

1次 AC and 秒杀

爽！

和 炮兵阵地 差不多

ORZ oimaster！！

在您的代码指导下我终于AC了！

srO oimaster Orz

将4^i*5^j抽象成一个矩阵中的点(i,j)，然后这个矩阵中的数为0或1，要求不能存在相邻的1，用状态压缩DP解决。（注意4^i*5^j limit;

for (tmp = 1, n = 0; tmp

const

tt=100000000;

var

f :array[0..12,0..12000]of int64;

n,k,i,j,x,y,p,pos,t :longint;

s :int64;

begin

read(n);

k:=1;

i:=1;

while k*4y) then break else

begin

pos:=1 shl (i-1)-1;

while pos>=0 do

begin

for t:=0 to 1 shl (k-1)-1 do

if t and (not pos)=t then

if t and(not (pos shr 1))=t then

if t and(not(1 shl (i-1)))=t then

if t and(not(1 shl (i-2)))=t then

begin

inc(f[k,1 shl (i-1)+pos],f[k-1,t]);

f[k,1 shl (i-1)+pos]:=f[k,1 shl (i-1)+pos]mod tt;

end;

inc(f[k,1 shl (i-1)+pos]);

f[k,1 shl (i-1)+pos]:=f[k,1 shl (i-1)+pos]mod tt;

inc(s,f[k,1 shl (i-1)+pos]);

s:=s mod tt;

pos:=pos-1;

end;

end;

end;

writeln((s+1)mod tt);

end.

求助啊,改了很多天，最后一个数据还是过不了,只有一个过了,哪个人可以帮我看看吗,

DP压缩,加位运算......

const maxn=100000000;

two:array[1..12]of integer=(1,2,4,8,16,32,64,128,256,512,1024,2048);

var

k,n,lll:longint;

a:array[0..13,1..12]of int64;

f:array[1..13,1..1000]of int64;

can:array[0..1000]of longint;

function b(l,m:longint):boolean;

var i:longint;

begin

for i:=1 to 12 do

if (a[l,i]>n) and (two[i] and can[m]=two[i]) then exit(false);

exit(true);

end;

procedure init;

var i,j:longint;bb:boolean;

begin

k:=0;

fillchar(a,sizeof(a),0);

fillchar(f,sizeof(f),0);

fillchar(can,sizeof(can),0);

a[1,1]:=1;

for i:=1 to 12 do

a[13,i]:=99999999999999999;

for i:=2 to 12 do

a[1,i]:=a[1,i-1]*4;

for i:=2 to 12 do

for j:=1 to 12 do

a:=a*5;

for i:=1 to 2048-1 do

if i shr 1 and i=0 then

begin

inc(k);

can[k]:=i;

end;

for i:=1 to k do

if b(1,i) then f[1,i]:=1;

for i:=1 to 13 do

if a>n then

begin

lll:=i-1;

break;

end;

end;

procedure work;

var o,i,j,l:longint;ans:int64;bb:boolean;

begin

ans:=0;

for o:=2 to lll do

begin

for i:=1 to k do

if b(o,i) then

begin

f[o,i]:=1;

for j:=1 to k do

if (can[i] and can[j]=0) then

begin

f[o,i]:=(f[o,i]+f[o-1,j]) mod maxn;

end;

for l:=o-2 downto 1 do

for j:=1 to k do

f[o,i]:=(f[o,i]+f[l,j]) mod maxn;

end;

end;

for o:=1 to lll do

for i:=1 to k do

ans:=(ans+f[o,i]) mod maxn;

write((ans+1) mod maxn);

end;

begin

assign(input,'lastvs9.in');reset(input);

assign(output,'lastwar.out');rewrite(output);

read(n);

init;

work;

close(input);

close(output);

end.

这题老题。。另一个版本是不能取2的倍数和3的倍数的。。

映射i,j到平面坐标系，然后压行DP

一次AC

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

犯了去多小错

呃！！！~~~~~~~~~~~~~~~~

改过来就对了

交了6，7次

大家们要细心！！

位运算+状压DP

哈哈，太水了

为什么我看到这题会突然想起杨氏表~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

ac了

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

纠结，纠结，终于AC了 myself orz

这不是spoj上很老的题吗？

状态压缩dp~

m67的blog上有完全一样的题~

规律啊，哪位大牛提供一下

http://Nothing_sway.51.com

就这些数：

1,4,5,16,20,25,64,80,100,125,256,320,400,500,625,1024,1280,1600,2000,2500,3125,4096,5120,6400,8000,10000,12500,15625,16384,20480,25600,32000,40000,50000,62500,65536,78125,81920,102400,128000,160000,200000,250000,262144,312500,327680,390625,409600,512000,6

40000,800000,1000000,1048576,1250000,1310720,1562500,1638400,1953125,2048000,2560000,3200000,4000000,4194304

再进行符合条件的组合就可以

Var

a:array[1..64]of int64;

b,c:array[1..64]of boolean;

i,j,k,n,x,step,ss:longint;

ans:int64;

p,t:integer;

aa:array[0..64]of integer;

procedure out;

var

i,j:integer;

boo:boolean;

begin

inc(t);

boo:=true;

for i:=1 to p-1 do

for j:=1+i to p do

if (boo)and(((a[aa[i]] div a[aa[j]]=4)and(a[aa[i]] mod a[aa[j]]=0))

or((a[aa[i]] div a[aa[j]]=5)and(a[aa[i]] mod a[aa[j]]=0))

or((a[aa[j]] div a[aa[i]]=4)and(a[aa[j]] mod a[aa[i]]=0))

or((a[aa[j]] div a[aa[i]]=5)and(a[aa[j]] mod a[aa[i]]=0)))

then begin

dec(t);

boo:=false;

end;

end;

procedure sort(kk,p:integer);

var

i:integer;

begin

if kk>p then out

else

for i:=aa[kk-1]+1 to k do

begin

aa[kk]:=i;

sort(kk+1,p);

end

end;

Function ncf(x,y:longint):int64;

var

o,p:longint;

begin

if y=0

then exit(1);

o:=1;

for p:=1 to y do

o:=o*x;

exit(o);

end;

Begin

readln(n);

i:=0;

j:=0;

k:=0;

repeat

if ncf(4,i)*ncf(5,j)11;

for i:=1 to k-1 do

for j:=1+i to k do

if a[i]>a[j]

then begin

step:=a[i];

a[i]:=a[j];

a[j]:=step;

end;

ans:=1+k;

fillchar(c,sizeof(c),true);

for p:=1 to k do

sort(1,p);

writeln(t+1);

End.

超时25秒。。。。。答案没错。。。。。暴力，呵呵

很简单的状态压缩dp

把每个数放在以4，5的指数为横纵坐标的图中，便可找到规律

竟然来不及交，T-T

我的解题报告：

http://hi.baidu.com/qyjubriskxp

比赛时居然把

if(w>=13)

return 1;

中的13打成12...

这种比赛也就少10分,要是这是SRM不就被直接cha了么....