bzoj1485: [HNOI2009]有趣的数列

传送门 显然当奇数位确定下来是，要么有确定解，要么无解。 于是我们可以脑补出一个dp F[I][J]：前i个奇数位位，末位是j的方案数。 暴力求解后发现是卡特兰数（呵呵呵呵） 我们可以将一个奇数项的数看成入栈，偶数项的数看成出栈，则每一个合法的出栈入栈序对应一个合法解。（自己yy） 这样就OK了 注：可以用质因数分解避免求乘法逆元。

uses math; var a,b,p:array [0..2000005] of longint; n,pp,i,j,x:longint; ans:int64; begin read(n,pp); for i:=2 to n*2 do begin if a[i]=0 then begin inc(p[0]); p[p[0]]:=i; a[i]:=p[0]; end; for j:=1 to p[0] do if (i*p[j]<=n*2) then a[i*p[j]]:=j else break; end; for i:=n+1 to n*2 do begin x:=i; while x<>1 do begin inc(b[a[x]]); x:=x div p[a[x]]; end; end; for i:=1 to n+1 do begin x:=i; while x<>1 do begin dec(b[a[x]]); x:=x div p[a[x]]; end; end; ans:=1; for i:=1 to p[0] do for j:=1 to b[i] do ans:=ans*p[i] mod pp; write(ans); end.