首页 > 代码库 > 高维网络
高维网络
高维网络
【问题描述】
现在有一个 维的坐标网格，其中第 维坐标的范围是[0, ]。
在这个范围内建立一个有向图：我们把范围内的每个整点（每一维坐标均为
整数的点）当做图上的顶点。设点 (0,0, ? ,0), ( 1, 2, ? , )。
对于范围内的点( 1, 2, ? , )，它会向以下这些点（如果目标点在范围内）：
( 1 + 1, 2, ? , ), ( 1, 2 + 1, ? , ), ? , ( 1, 2, ? , + 1)连有向边。
现在从点 到点 会有若干条路径，路径的条数可以十分简单地算出。然而不幸的是，范围内有 个点被破坏了（点 和点 不会被破坏），其中第 个点的坐
标为( ,1, ,2, ? , , )。你需要算出从点 到点 剩余的路径条数。
由于答案可能很大，你只需要输出它对1,000,000,007取模的结果。
分析：
这个题只会80 分做法：
当n=1时判断结果，有断点为0，无断点为1；
当n=2或3 时，且a[i]的范围比较小时，dp；
当p=0时，用组合数公式。
代码实现：
program exam;
const
pz=1000000007;
var
i,j,k:longint;
d,p,x,y,z:longint;
pan:boolean;
ans,a1,a2,a3,sum:int64;
f2:array[-1..1000,-1..1000] of int64;
b2:array[-1..1000,-1..1000] of boolean;
t2:array[-1..1000,-1..1000] of int64;
f3:array[-1..100,-1..100,-1..100] of int64;
t3:array[-1..100,-1..100,-1..100] of int64;
b3:array[-1..100,-1..100,-1..100] of boolean;
a:array[1..10000] of longint;
function f(a,b:int64):int64;
var
t,y:int64;
begin
t:=1;
y:=a;
while b<>0 do
begin
if (b and 1)=1 then
t:=t*y mod pz;
y:=y*y mod pz;
b:=b shr 1;
end;
exit(t);
end;
function comb(n,m:int64):int64;
var
i,j:longint;
a1,b1:int64;
begin
a1:=1;
for i:=1 to m do
a1:=((a1 mod pz)*((n-i+1) mod pz)) mod pz;
b1:=1;
for i:=1 to m do
b1:=((b1 mod pz)*(i mod pz)) mod pz;
b1:=f(b1,pz-2);
a1:=((a1 mod pz)*(b1 mod pz)) mod pz;
exit(a1);
end;
function com(t,sum:int64):int64;
var
i,j:longint;
a1,b1:int64;
begin
a1:=1;
for i:=1 to sum do
a1:=((a1 mod pz)*(i mod pz)) mod pz;
b1:=1;
for j:=1 to t do
for i:=1 to a[j] do
b1:=((b1 mod pz)*(i mod pz)) mod pz;
b1:=f(b1,pz-2);
a1:=((a1 mod pz)*(b1 mod pz)) mod pz;
exit(a1);
end;
begin
assign(input,‘cube.in‘);
reset(input);
assign(output,‘cube.out‘);
rewrite(output);
readln(d,p);
pan:=false;
if d=1 then
begin
if p=0 then
writeln(‘1‘);
if p>0 then
writeln(‘0‘);
end;
if d=2 then
begin
for i:=1 to d do
begin
read(a[i]);
if a[i]>1000 then
pan:=true;
end;
if pan=false then
begin
for i:=1 to p do
begin
readln(x,y);
b2[x,y]:=true;
end;
t2[0,0]:=1;
for i:=0 to a[1] do
for j:=0 to a[2] do
begin
if (b2[i-1,j]=false) and (b2[i,j-1]=false) then
f2[i,j]:=f2[i-1,j] mod pz+f2[i,j-1] mod pz+t2[i,j] mod pz;
if (b2[i-1,j]=false) and (b2[i,j-1]=true) then
f2[i,j]:=f2[i-1,j] mod pz+0+t2[i,j] mod pz;
if (b2[i-1,j]=true) and (b2[i,j-1]=false) then
f2[i,j]:=0+f2[i,j-1] mod pz+t2[i,j] mod pz;
if (b2[i-1,j]=true) and (b2[i,j-1]=true) then
f2[i,j]:=0+0+t2[i,j] mod pz;
end;
writeln(f2[a[1],a[2]] mod pz);
end;
if (pan=true) and (p=0) then
begin
ans:=comb(a[1]+a[2],a[1]);
writeln(ans);
end;
end;
if d=3 then
begin
for i:=1 to d do
begin
read(a[i]);
sum:=sum+a[i];
if a[i]>100 then
pan:=true;
end;
if pan=false then
begin
fillchar(b3,sizeof(b3),true);
for i:=1 to p do
begin
readln(x,y,z);
b3[x,y,z]:=false;
end;
t3[0,0,0]:=1;
for i:=0 to a[1] do
for j:=0 to a[2] do
for k:=0 to a[3] do
begin
if (b3[i-1,j,k]=true) and (b3[i,j-1,k]=true) and (b3[i,j,k-1]=true) then
f3[i,j,k]:=f3[i-1,j,k] mod pz+f3[i,j-1,k] mod pz+f3[i,j,k-1] mod pz+t3[i,j,k] mod pz;
if (b3[i-1,j,k]=true) and (b3[i,j-1,k]=false) and (b3[i,j,k-1]=true) then
f3[i,j,k]:=f3[i-1,j,k] mod pz+0+f3[i,j,k-1] mod pz+t3[i,j,k] mod pz;
if (b3[i-1,j,k]=true) and (b3[i,j-1,k]=true) and (b3[i,j,k-1]=false) then
f3[i,j,k]:=f3[i-1,j,k] mod pz+f3[i,j-1,k] mod pz+0+t3[i,j,k] mod pz;
if (b3[i-1,j,k]=true) and (b3[i,j-1,k]=false) and (b3[i,j,k-1]=false) then
f3[i,j,k]:=f3[i-1,j,k] mod pz+0+0+t3[i,j,k] mod pz;
if (b3[i-1,j,k]=false) and (b3[i,j-1,k]=true) and (b3[i,j,k-1]=true) then
f3[i,j,k]:=0+f3[i,j-1,k] mod pz+f3[i,j,k-1] mod pz+t3[i,j,k] mod pz;
if (b3[i-1,j,k]=false) and (b3[i,j-1,k]=false) and (b3[i,j,k-1]=true) then
f3[i,j,k]:=0+0+f3[i,j,k-1] mod pz+t3[i,j,k] mod pz;
if (b3[i-1,j,k]=false) and (b3[i,j-1,k]=true) and (b3[i,j,k-1]=false) then
f3[i,j,k]:=0+f3[i,j-1,k] mod pz+0+t3[i,j,k] mod pz;
if (b3[i-1,j,k]=false) and (b3[i,j-1,k]=false) and (b3[i,j,k-1]=false) then
f3[i,j,k]:=0+0+0+t3[i,j,k] mod pz;
end;
writeln(f3[a[1],a[2],a[3]] mod pz);
end;
if (pan=true) and (p=0) then
begin
ans:=com(d,sum);
writeln(ans);
end;
end;
if (d>3) and (p=0) then
begin
for i:=1 to d do
begin
read(a[i]);
sum:=sum+a[i];
end;
ans:=com(d,sum);
writeln(ans);
end;
if (d>3) and (p<>0) then
writeln(‘0‘);
close(input);
close(output);
end.
高维网络