HNOI2008Cards

看了一下polya和burnside定理，感觉还行（就是不会证……）

这题用的是burnside

ans=在每个置换群下不动的方案数之和除以置换数

这题有个难点在取模

关于对p（p为素数）取模（涉及到了除法），我总结了两种方法：

已知x mop p=y，要求x/z mod p=？

大体思路是利用乘法逆，将/z转换成*z的逆元即可

一、利用费马小定理

z^p-1 mod p=1

所以z的逆元=power_mod（z,p-2,p）

二、利用拓展欧几里德算法，即exgcd（z，p，x，y）

while x<0 do inc(x,p)

事实上，这也是乘法逆的思想

exgcd（z，p，x，y）这实际上是在解同余方程zx mod p=1

x不就是z的逆元吗

但是当p不是素数时，应该怎么办呢？

在做noi2002robot的时候，我运用了一种特殊的方法，最后需要求x>>1 mod p=?

我在过程中始终对p取模，到最后感觉做不下去了

后来我灵机一动，想到了多取一位在过程中mod 10p

这样最后输出的时候再mod p 答案就正确了

不知道这样的方法能否应用在更广泛的地方……

ps:刚才试了一下此题

在过程中一直对m*p取模，最后ans div m 再对p取模，竟然AC了

原理在哪里？

代码：

神牛Green Clouds 的代码（费马小定理）：

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std ;

 const int maxn =;

 int sr , sb , sg , m , mod , f[ maxn ][ maxn ][ maxn ], a[ maxn *], n ;

 bool used[ maxn *];

 int v[ maxn *], cnt , ans =;

 void update(int&num ,int val ){

     ( num += val )%= mod ;

 }

 int power(int val ,int times ){

     int rec =;

     for(; times ; times >>=){

         if( times &)( rec *= val )%= mod ;

         ( val *= val )%= mod ;

     }

     return rec ;

 }

 int main(  ){

     scanf("%d%d%d%d%d",&sr ,&sb ,&sg ,&m ,&mod );

     n = sr + sb + sg ;

     for(int w =; w ++< m +;){

         if( w < m +)for(int i =; i ++< n ;)scanf("%d", a + i );

         else for(int i =; i ++< n ;) a[ i ]= i ;

         memset( used ,false,sizeof( used ));

         cnt =;

         for(int i =; i ++< n ;)if(! used[ i ]){

             v[++ cnt ]=;

             for(int j = i ;! used[ j ]; j = a[ j ]){

                 ++ v[ cnt ], used[ j ]=true;

             }

         }

         memset( f ,,sizeof( f ));

         f[][][]=;

         for(int h =; h ++< cnt ;){

             for(int i = sr ; i >=;-- i ){

                 for(int j = sb ; j >=;-- j ){

                     for(int k = sg ; k >=;-- k ){

                         if( i >= v[ h ])update( f[ i ][ j ][ k ], f[ i - v[ h ]][ j ][ k ]);

                         if( j >= v[ h ])update( f[ i ][ j ][ k ], f[ i ][ j - v[ h ]][ k ]);

                         if( k >= v[ h ])update( f[ i ][ j ][ k ], f[ i ][ j ][ k - v[ h ]]);

                     }

                 }

             }

         }

         update( ans , f[ sr ][ sb ][ sg ]);

     }

     ( ans *=power( m +, mod -))%= mod ;

     printf("%d\n", ans );

     return ;

 }

exgcd：

 var s1,s2,s3,n,m,p,ans,i,j,x,y:longint;

     a:array[..,..] of longint;

     f:array[..,..,..] of longint;

 function mo(x:longint):longint;

  begin

    mo:=x mod (p);

  end;

 procedure init;

  begin

    readln(s1,s2,s3,m,p);

    n:=s1+s2+s3;

    for i:= to m do

     for j:= to n do

      read(a[i,j]);

    inc(m);

    for i:= to n do a[m,i]:=i;

  end;

 function dp(x:longint):longint;

  var i,j,k,tot,y,h,num:longint;

      v:array[..] of boolean;

      d:array[..] of longint;

  begin

    tot:=;

    fillchar(v,sizeof(v),false);

    for i:= to n do

     if not(v[i]) then

      begin

        num:=;

        v[i]:=true;

        y:=i;

        while a[x,y]<>i do

         begin

          y:=a[x,y];

          v[y]:=true;

          inc(num);

         end;

        inc(tot);

        d[tot]:=num;

      end;

    fillchar(f,sizeof(f),);

    f[,,]:=;

    for h:= to tot do

     for i:=s1 downto  do

      for j:=s2 downto  do

       for k:=s3 downto  do

        begin

         if i>=d[h] then f[i,j,k]:=mo(f[i,j,k]+f[i-d[h],j,k]);

         if j>=d[h] then f[i,j,k]:=mo(f[i,j,k]+f[i,j-d[h],k]);

         if k>=d[h] then f[i,j,k]:=mo(f[i,j,k]+f[i,j,k-d[h]]);

        end;

    exit(f[s1,s2,s3]);

    end;

 procedure exgcd(a,b:longint;var x,y:longint);

  var t:longint;

  begin

  if a= then begin x:=;y:=;exit;end;

  exgcd(b,a mod b,x,y);

  t:=x;x:=y;y:=t-(a div b)*x;

  end;

 procedure main;

  begin

    ans:=;

    for i:= to m do

     ans:=mo(ans+dp(i));

    exgcd(m,p,x,y);

    while x< do inc(x,p);

    writeln((ans*x) mod p);

  end;

 begin

   init;

   main;

 end.

m*p：

 var s1,s2,s3,n,m,p,ans,i,j,x,y:longint;

     a:array[..,..] of longint;

     f:array[..,..,..] of longint;

 function mo(x:longint):longint;

  begin

    mo:=x mod (m*p);

  end;

 procedure init;

  begin

    readln(s1,s2,s3,m,p);

    n:=s1+s2+s3;

    for i:= to m do

     for j:= to n do

      read(a[i,j]);

    inc(m);

    for i:= to n do a[m,i]:=i;

  end;

 function dp(x:longint):longint;

  var i,j,k,tot,y,h,num:longint;

      v:array[..] of boolean;

      d:array[..] of longint;

  begin

    tot:=;

    fillchar(v,sizeof(v),false);

    for i:= to n do

     if not(v[i]) then

      begin

        num:=;

        v[i]:=true;

        y:=i;

        while a[x,y]<>i do

         begin

          y:=a[x,y];

          v[y]:=true;

          inc(num);

         end;

        inc(tot);

        d[tot]:=num;

      end;

    fillchar(f,sizeof(f),);

    f[,,]:=;

    for h:= to tot do

     for i:=s1 downto  do

      for j:=s2 downto  do

       for k:=s3 downto  do

        begin

         if i>=d[h] then f[i,j,k]:=mo(f[i,j,k]+f[i-d[h],j,k]);

         if j>=d[h] then f[i,j,k]:=mo(f[i,j,k]+f[i,j-d[h],k]);

         if k>=d[h] then f[i,j,k]:=mo(f[i,j,k]+f[i,j,k-d[h]]);

        end;

    exit(f[s1,s2,s3]);

    end;

 procedure main;

  begin

    ans:=;

    for i:= to m do

     ans:=mo(ans+dp(i));

    writeln((ans div m) mod p);

  end;

 begin

   init;

   main;

 end.

巴特西

HNOI2008Cards

最新文章

热门文章