首页 > 代码库 > SDOI 2010 and SXOI 2014 地精部落 (递推)
SDOI 2010 and SXOI 2014 地精部落 (递推)
用E[i,j]表示共有i个数字,以1..j开头且一开始下降的方案数的总和。则我们有:
E[i,j]:=E[I,J-1]+E[i-1,i-j]
我们先来证明上升与下降的方案是一一对应的。
事实上,若有a1,a2,a3,……,an 为满足要求的一个序列(上升或下降),
则我们构造新数列,n+1-a1,n+1-a2,n+1-a3,……,n+1-an 这个数列也满足要求(下降或上升)。
而且这种对应是一一对应的,其正确性是显然的。
令f[i,j]表示共i个数字,以j开头的下降的方案数
令g[i,j]表示共i个数字,以j开头的上升的方案数
则我们有f[i,j]:=g[i,i+1-j](因为它们是一一对应的)。
所以f[i,j]=g[i-1,j-1]+g[i-1,j-2]+……+g[i-1,1]
=f[i-1,i-j+1]+f[i-1,i-j+2]+……+f[i-1,i-1]
=E[i-1,i-1]-E[i-1,i-j]
于是E[i,j]:=E[i,j-1]+f[i,j]=E[i,j-1]+E[i-1,i-1]-E[i-1,i-j];
var i,j,n,p,x:longint; f:array[0..1,0..4500] of longint; begin readln(n,p); f[1,1]:=1;x:=1; for i:=2 to n do begin x:=1-x; for j:=1 to i do begin f[x,j]:=f[x,j-1]+f[1-x,i-j]; if f[x,j]>=p then dec(f[x,j],p); end; end; if n=1 then writeln(1) else writeln(f[n mod 2,n]*2 mod p); end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。