Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 我要吐血了，我O(XP)复杂度的PolTLE，请教怎样优化？（程序供参考）

Posted by JiangLY at 2005-07-25 18:47:26 on Problem 2154
```var
m,i,j,p,t,ti,l:longint;
n,s,a,b:int64;
w:array[1..30000] of int64;
f:array[0..30000] of boolean;
flag:boolean;
begin
for ti:=1 to t do
begin
n:=m;
w[1]:=1 mod p;
l:=1;
fillchar(f,sizeof(f),false);
flag:=false;
repeat
inc(l);
w[l]:=(w[l-1]*(n mod p)) mod p;
j:=w[l];
if f[j] then
begin
flag:=true;
break;
end;
f[j]:=true;
until l=m;
if flag then
begin
dec(l);
for i:=1 to l do
if w[i]=w[l+1] then break;
for j:=i to l do w[j-i+1]:=w[j];
l:=l-i+1;
s:=w[((m-i) mod l+1)];
end
else s:=w[m];
if odd(n) then
begin
a:=1 mod p;
b:=(n-1) mod p;
s:=(s+a*b) mod p;
end
else
begin
a:=n mod p;
b:=(n div 2) mod p;
s:=(s+b) mod p;
b:=(n div 2-1) mod p;
s:=(s+(a mod p)*b) mod p;
end;
writeln(s);
end;
end.
```

Followed by: