1
22
2016
0

【HNOI2008】【bzoj1004】【Burnside引理】【欧几里得算法】Cards

%%%峰哥ZYF

这题用的是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了 
 
    原理在哪里?
Category: 数学相关 | Tags: | Read Count: 136

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com