[POJ1286&POJ2154&POJ2409]Polya定理

Polya定理

　　L=1/|G|*(m^c(p1)+m^c(p2)+...+m^c(pk))

　　G为置换群大小

　　m为颜色数量

　　c（pi）表示第i个置换的循环节数

　　如置换（123）（45）（6）其循环节数为3

-------------------------------------------------------------------------------------------

　POJ1286&POJ2409

　　都是简单的处理串珠子的问题。

　　题目中隐藏着3种不同的置换类别。

　　1.旋转

　　　　注意不需要顺时针和逆时针分开考虑因为顺时针旋转k位等同于逆时针旋转（n-k）位。

　　　　另外当旋转了k位时的循环节数为gcd(k,n) 这个略加脑补也可得出。

　　2.翻转（对称）

　　　　需要分n的奇偶分开讨论

　　　　当n为奇数时

　　　　　　只有一种对称，即以每颗珠子与中心的连线所在的直线为对称轴。这个时候循环节数为（n+1）/2。

　　　　当n为偶数时

　　　　　　有两种对称，一种同奇数时的情况，但是此时相对的两颗珠子所成的直线为同一条

　　　　　　所以循环节数为n/2+1，情况的数量也要减少一半。

　　　　　　另一种是以两颗珠子连线的中点与中心连线所在的直线为对称轴。这种情况的循环节数为n/2，情况也是n/2种。

　　这两道题的数据范围都很小，所以直接这样处理就可以了。

program poj1286;

var i,n:longint;

    tot,sum:int64;

    w:array[-..]of int64;

function gcd(x,y:longint):longint;

begin

    if y= then exit(x) else exit(gcd(y,x mod y));

end;

begin

    w[]:=;

    for i:= to  do w[i]:=w[i-]*;

    readln(n);

    while n<>- do

    begin

                if n= then

                begin

                        writeln();

                        readln(n);

                        continue;

                end;

        tot:=;sum:=w[n];

        for i:= to n- do

        begin

            inc(tot);

            inc(sum,w[gcd(i,n)]);

        end;

        if odd(n) then

        begin

            inc(tot,n);

            inc(sum,w[(n+) >> ]*n);

        end else

        begin

            inc(tot,n >> );

            inc(sum,w[n >> +]*n >> );

            inc(tot,n >> );

            inc(sum,w[n >> ]*n >> );

        end;

        writeln(sum div tot);

        readln(n);

    end;

end.

program poj2409;

var m,n,tot,sum:int64;

    i:longint;

function w(x:longint):int64;

var i:longint;

begin

    w:=;

    for i:= to x do w:=w*m;

end;

function gcd(x,y:longint):longint;

begin

        if y= then exit(x) else exit(gcd(y,x mod y));

end;

begin

    readln(m,n);

    while (m<>)or(n<>) do

    begin

        tot:=;sum:=;

        for i:= to n do

        begin

            inc(tot);

            inc(sum,w(gcd(i,n)));

        end;

        if odd(n) then

        begin

            inc(tot,n);

            inc(sum,w((n+) >> )*n);

        end else

        begin

            inc(tot,n >> );

            inc(sum,w(n >> )* n >> );

            inc(tot,n >> );

            inc(sum,w(n >> +)* n >> );

        end;

        writeln(sum div tot);

        readln(m,n);

    end;

end.

----------------------------------------------------------------------------------

POJ2154

　　感觉非常坑啊...

　　首先觉得这道题挺好的...数据范围非常大

　　由于用到gcd的统计所以自然而然想到了欧拉函数

　　然后套一下应该就出来了...

　　但是为什么我做了这么久...

　　有几个需要注意的地方

　　1.最后除以|G|在这里也就是n的步骤由于在取模意义下所以会出错，但是很神奇的发现快速幂的底数也都是n（大概这也是题目中长度和颜色数相同的意图吧），只要将次数-1就可以了。

　　2.直接这样会TLE，欧拉函数的求解还需要用欧拉线筛来优化。即用已有的质因子来求phi。过程很简单就不多提了。

　　值得一提的是最后一次TLE到AC的跨越仅仅是因为一个变量的类型。即ans变量改成longint就可以过了。

　　再一次印证了张老师几年前提到的”空间会影响时间“

　　另外在这道题中，正巧将前几天学的欧拉函数和欧拉线筛都运用了起来，感觉非常不错。

program poj2154;

const maxn=trunc(sqrt());

var t,test,n,tt:longint;

    vis:array[-..maxn]of boolean;

    p:array[-..maxn]of longint;

procedure build;

var i,j:longint;

begin

        fillchar(vis,sizeof(vis),true);

        p[]:=;

        for i:= to maxn do

        begin

                if vis[i] then

                begin

                        inc(p[]);p[p[]]:=i;

                end;

                for j:= to p[] do

                begin

                        if i*p[j]>maxn then break;

                        vis[i*p[j]]:=false;

                        if i mod p[j]= then break;

                end;

        end;

end;

function phi(x:longint):longint;

var i,ans,tem:longint;

begin

        ans:=x;tem:=x;

    for i:= to p[] do if tem>=p[i]*p[i] then

                //刚开始写成了tem>=p[i]就失去了优化的意义TAT

    begin

                if x mod p[i]= then ans:=ans div p[i]*(p[i]-);

                    //在ans是longint的情况下先乘后除会爆

                while x mod p[i]= do x:=x div p[i];

    end else break;

    if x<> then ans:=ans div x*(x-);

                    //这里也涉及到运算顺序的问题

    exit(ans mod tt);

end;

function mul(a,b:longint):longint;

var ans,w:int64;

begin

    ans:=;w:=a mod tt;

    while b<> do

    begin

        if b and = then ans:=(ans*w) mod tt;

        w:=(w*w) mod tt;

        b:=b >> ;

    end;

    exit(ans);

end;

function solve:longint;

var i:longint;

    ans:int64;

begin

    ans:=;

    for i:= to trunc(sqrt(n)) do if n mod i= then

    begin

        ans:=(ans+phi(n div i)*mul(n,i-)) mod tt;

        if i*i<>n then ans:=(ans+phi(i)*mul(n,n div i-)) mod tt;

    end;

    exit(ans);

end;

begin

    readln(test);

        build;

        for t:= to test do

    begin

        readln(n,tt);

        writeln(solve);

    end;

end.

巴特西

[POJ1286&POJ2154&POJ2409]Polya定理

最新文章

热门文章