题意:

【ZJOI2017 Round1练习&BZOJ4767】D1T3 两双手(排列组合,DP)-LMLPHP

100%的数据:|Ax|,|Ay|,|Bx|,|By| <= 500, 0 <= n,Ex,Ey <= 500

思路:听说这是一道原题

只能往右或者下走一步且有禁止点的简化版是CF559C

然而这道题并没有这么简单

以下开始转化:

【ZJOI2017 Round1练习&amp;BZOJ4767】D1T3 两双手(排列组合,DP)-LMLPHP

转化后套用弱化版做法即可

 const mo=;
var fac,exf:array[..]of int64;
dp:array[..]of int64;
x,y:array[..]of longint;
ex,ey,sx,sy,ax,ay,bx,by:int64;
n,n1,i,j:longint;
u,v,eps:double; function fabs(x:double):double;
begin
if x< then exit(-x);
exit(x);
end; procedure swap(var x,y:longint);
var t:longint;
begin
t:=x; x:=y; y:=t;
end; procedure qsort(l,r:longint);
var i,j,mid1,mid2:longint;
begin
i:=l; j:=r; mid1:=x[(l+r)>>]; mid2:=y[(l+r)>>];
repeat
while (mid1>x[i])or((mid1=x[i])and(mid2>y[i])) do inc(i);
while (mid1<x[j])or((mid1=x[j])and(mid2<y[j])) do dec(j);
if i<=j then
begin
swap(x[i],x[j]);
swap(y[i],y[j]);
inc(i); dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end; function c(x,y:longint):int64;
begin
exit(fac[x]*exf[y] mod mo*exf[x-y] mod mo);
end; begin
assign(input,'hands.in'); reset(input);
assign(output,'hands.out'); rewrite(output);
readln(ex,ey,n1);
readln(ax,ay,bx,by);
fac[]:=; fac[]:=; exf[]:=; exf[]:=;
for i:= to do fac[i]:=fac[i-]*i mod mo;
for i:= to do exf[i]:=exf[mo mod i]*(mo-mo div i) mod mo;
for i:= to do exf[i]:=exf[i-]*exf[i] mod mo; eps:=1e-8;
v:=(ex*ay-ey*ax)/(bx*ay-by*ax);
u:=(ex*by-ey*bx)/(ax*by-ay*bx);
if (fabs(round(v)-v)>eps)or(fabs(round(u)-u)>eps) then
begin
writeln();
close(input);
close(output);
exit;
end
else begin inc(n); x[n]:=round(u); y[n]:=round(v); end;
for i:= to n1 do
begin
readln(sx,sy);
v:=(sx*ay-sy*ax)/(bx*ay-by*ax);
u:=(sx*by-sy*bx)/(ax*by-ay*bx);
if (fabs(round(v)-v)>eps)or(fabs(round(u)-u)>eps) then continue;
if (u<)or(v<) then continue;
if (u>x[])or(v>y[]) then continue;
inc(n); x[n]:=round(u); y[n]:=round(v);
end;
inc(n); x[n]:=; y[n]:=;
qsort(,n);
dp[]:=;
for i:= to n do
begin
dp[i]:=c(x[i]+y[i],x[i]);
for j:= to i- do
if (x[i]>=x[j])and(y[i]>=y[j]) then
dp[i]:=dp[i]-dp[j]*c(x[i]+y[i]-x[j]-y[j],x[i]-x[j]) mod mo;
dp[i]:=(dp[i] mod mo+mo) mod mo;
end;
writeln(dp[n]); close(input);
close(output);
end.
05-18 17:52