8
29
2013
0

【BZOJ3260】跳【费马小定理】

数学题,略蛋疼。可以证明最优的方案一定是先沿着较长边走,然后再走较短边。这样的话答案就是1+n+C1n+C2n+1+...+Cmn+m。然后由于答案是取模一个指数num,那么对于一个组合a/b,由费马小定理a/b mod num=a*b^(num-2) mod num。那么答案就可以用快速幂求得。这样时间复杂度就是mlogm,由于m是较短边,那么m<=1000000,而由于快速幂太慢,我开始T了好久,后来用位运算瞎搞搞A了。

 

program p3260;
	const
		num=1000000007;
	var
		n,m,k1,k2,tot:int64;
		i,j:longint;
	function quick(k1,k2:int64):int64;
		var	
			k,i:int64;
		begin
			k:=k1; i:=1;
			while k2>0 do begin
				if k2 and 1>0 then
					i:=i*k mod num;
				k:=k*k mod num; k2:=k2 shr 1;
			end;
			exit(i);
		end;
	begin
		readln(n,m);
		if n<m then begin k1:=m; m:=n; n:=k1; end; n:=n mod num;
		tot:=n+1; k1:=1; k2:=1;
		for i:=1 to m do begin
			k1:=k1*i mod num;
			k2:=k2*(n+i) mod num;
			tot:=((tot+quick(k1,num-2)*k2) mod num);
		end;
		writeln(tot);
	end.
Category: 费马小定理 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com