首页 > 代码库 > poj 2409 Let it Bead Polya计数
poj 2409 Let it Bead Polya计数
旋转能够分为n种置换,相应的循环个数各自是gcd(n,i),个i=0时不动,有n个
翻转分为奇偶讨论,奇数时有n种置换,每种有n/2+1个
偶数时有n种置换,一半是n/2+1个,一半是n/2个
啃论文,PPT,各种书好久才看懂Polya定理,近期做数学题做的严重怀疑自己的智商。
#include <iostream> #include <cstdio> #include <cstdlib> #include<algorithm> #include<map> #include<cstring> using namespace std; typedef long long ll; ll gcd(ll a,ll b) {return a%b==0?b:gcd(b,a%b);} ll quickpow(ll m,ll n) { ll ans=1; while(n) { if(n&1) ans=ans*m; n=(n>>1); m=m*m; } return ans; } int main() { ll c,n; while(~scanf("%lld%lld",&c,&n)) { if(c+n==0) break; ll ans=quickpow(c,n); for(int i=1;i<n;i++) ans+=quickpow(c,gcd(n,i)); if(n&1) ans+=n*quickpow(c,n/2+1); else ans+=(n/2*quickpow(c,n/2+1)+n/2*(quickpow(c,n/2))); printf("%lld\n",ans/(2*n)); } return 0; }
poj 2409 Let it Bead Polya计数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。