jiry_2's Blog

先画成一个堆，然后就可以YY出递推式F[I]=F[I*2]*F[I*2+1]*C(C[I]-1,C[I*2])，C[I]是指以I为根的子树的节点个数，然后只需要把阶乘预处理出来，然后用逆元瞎搞搞就水过了。

program p2111;
	var
		c:array[0..2000000] of longint;
		x,num:array[0..2000000] of int64;
		i,j,n,q:longint;
	function quick(k1,k2:int64):int64;
		var
			i,j,tot:int64;
		begin
			i:=k2; j:=k1; tot:=1;
			while i<>0 do begin
				if i and 1=1 then
					tot:=tot*j mod q;
				i:=i shr 1; j:=j*j mod q;
			end;
			exit(tot);
		end;
	function dfs(k1:longint):int64;
		begin
			if num[c[k1]]<>-1 then exit(num[c[k1]]);
			if (c[k1]<=1) then begin
				num[c[k1]]:=1; exit(1);
			end;
			num[c[k1]]:=x[c[k1]-1]*quick(x[c[k1*2]],q-2) mod q*quick(x[c[k1]-1-c[k1*2]],q-2) mod q;
			num[c[k1]]:=num[c[k1]]*dfs(k1*2) mod q*dfs(k1*2+1) mod q;
			exit(num[c[k1]]);
		end;
	begin
		readln(n,q);
		fillchar(c,sizeof(c),0);
		fillchar(x,sizeof(x),0);
		for i:=n downto 2 do begin
			inc(c[i]);
			inc(c[i div 2],c[i]);
		end;
		inc(c[1]);
		fillchar(num,sizeof(num),-1);
		x[0]:=1; 
		for i:=1 to n do 
			x[i]:=x[i-1]*i mod q;
		writeln(dfs(1));
	end.