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

## 是O(XP)的Polya

Posted by JiangLY at 2005-07-25 18:48:08 on Problem 2154
In Reply To:我要吐血了，我O(XP)复杂度的PolTLE，请教怎样优化？（程序供参考） Posted by:JiangLY at 2005-07-25 18:47:26
```> 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
>   readln(t);
>   for ti:=1 to t do
>     begin
>       readln(m,p);
>       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:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator