数据包：http://pan.baidu.com/s/1pJNSkL9
T1：
我们先直接用矩阵快速幂暴力
首先是0维,f1=1,f2=1
然后推出下一维的f1'和f2'
下一维的f1'和f2'其实就是f1+f2+f3+....+fn和f2+f3+f4+...+fn+1
所以f1'=sn,f2'=s(n+1)-f1
所以可以klogn求出答案
但是我们做了很多相同的事情，求sn和s(n+1)的时候求出来的矩阵是一样的
所以可以是logn+k的
但是既然是一样的其实f1,f2推到f1'和f2'是可以快速幂的
于是就变成了logn+logk的了
const
h=;
type
matrix=array[..,..]of int64;
const
d:matrix=((,,),(,,),(,,));
var
n,k:int64;
t:longint;
a,b,c:matrix; operator *(a,b:matrix)c:matrix;
var
i,j,k:longint;
begin
fillchar(c,sizeof(c),);
for i:= to do
for j:= to do
for k:= to do
c[i,j]:=(c[i,j]+a[i,k]*b[k,j])mod h;
end; procedure main;
var
i:longint;
begin
read(n,k);
b:=d;
fillchar(a,sizeof(a),);
for i:= to do
a[i,i]:=;
while n> do
begin
if n and = then a:=a*b;
b:=b*b;
n:=n>>;
end;
b:=a*d;
fillchar(c,sizeof(c),);
c[,]:=a[,];
c[,]:=a[,];
c[,]:=(b[,]-+h)mod h;
c[,]:=b[,];
fillchar(a,sizeof(a),);
for i:= to do
a[i,i]:=;
while k> do
begin
if k and = then a:=a*c;
c:=c*c;
k:=k>>;
end;
writeln((a[,]+a[,])mod h);
end; begin
read(t);
while t> do
begin
dec(t);
main;
end;
end.
T2：
首先有一个结论，那个函数是递增的
然后我们可以证明这样一个结论
假设现在sg最大为k，那么现在最后k+1个sg组成的集合一定是0...k
若现在P[m]>=k+1,那么显然sg[m]=k+1
若现在P[m]=k,那么sg[m]=sg[m-k]
可以用数学归纳法证明
又因为maxsg<=10^5
于是就维护这个sg的序列
T3：
又是合并的思想
首先我们想一下什么情况父亲会和儿子合并（首先把不可能有收益的儿子删掉，且按最低血量限制排序）
若合并之后血量最低限制不变就一定要合并
若父亲现在没有收益就一定要合并
用可并堆或者启发式合并维护
大概就是这样，具体看solution
const
maxn=;
inf=;
type
node=record
size,lc,rc,pay,gain:longint;
end;
var
first,next,last,d:array[..maxn*]of longint;
f:array[..maxn]of node;
n,t,time,tot:longint; procedure swap(var x,y:longint);
var
t:longint;
begin
t:=x;x:=y;y:=t;
end; procedure insert(x,y:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
end; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; function merge(a,b:longint):longint;
begin
if (a=) or (b=) then exit(a+b);
if f[b].pay<f[a].pay then swap(a,b);
f[a].rc:=merge(f[a].rc,b);
if f[f[a].rc].size>f[f[a].lc].size then swap(f[a].lc,f[a].rc);
f[a].size:=f[f[a].lc].size+f[f[a].rc].size+;
exit(a);
end; procedure dfs(x,fa:longint);
var
i:longint;
begin
i:=first[x];
d[x]:=;
while i<> do
begin
if last[i]<>fa then
begin
dfs(last[i],x);
d[x]:=merge(d[x],d[last[i]]);
end;
i:=next[i];
end;
while (d[x]<>) and ((f[x].pay>=f[d[x]].pay) or (f[x].gain-f[x].pay<=)) do
begin
if f[x].gain>=f[d[x]].pay then inc(f[x].gain,f[d[x]].gain-f[d[x]].pay)
else
begin
f[x].pay:=f[x].pay+f[d[x]].pay-f[x].gain;
f[x].gain:=f[d[x]].gain;
end;
d[x]:=merge(f[d[x]].lc,f[d[x]].rc);
end;
if f[x].gain-f[x].pay<= then d[x]:=
else d[x]:=merge(d[x],x);
end; procedure main;
var
i,x,y,hp:longint;
begin
fillchar(first,sizeof(first),);
tot:=;
read(n,t);
for i:= to n do
begin
read(f[i].gain);
if f[i].gain> then f[i].pay:=
else f[i].pay:=-f[i].gain;
if f[i].gain< then f[i].gain:=;
f[i].lc:=;
f[i].rc:=;
f[i].size:=;
end;
for i:= to n- do
begin
read(x,y);
insert(x,y);
insert(y,x);
end;
inc(n);
f[n].pay:=;
f[n].gain:=inf;
f[n].size:=;
f[n].lc:=;
f[n].rc:=;
insert(t,n);
insert(n,t);
dfs(,);
hp:=;
while d[]<> do
begin
if hp<f[d[]].pay then break;
inc(hp,f[d[]].gain-f[d[]].pay);
d[]:=merge(f[d[]].lc,f[d[]].rc);
end;
if hp>=inf then writeln('escaped')
else writeln('trapped');
end; begin
read(time);
while time> do
begin
dec(time);
main;
end;
end.