Uva10294 Arif in Dhaka (置换问题)

扯回正题，此题需要知道的是置换群的概念，这点在刘汝佳的书中写的比较详细，此处不多做赘述。此处多说一句的是第二种手镯的情况。在下图中“左图顺时针转1个位置”和“右图顺时针旋转5个位置”是相同的，所以在最终结果处需要(ans1+ans2)/2。

可以看刘汝佳白书，来看，这道题，burnside引理和polya定理的经典应用。

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #define ll long long

 using namespace std;

 int n,m;

 ll a[];

 int gcd(int a,int b)

 {

     return b?gcd(b,a%b):a;

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

         a[]=;

         for (int i=;i<=n;i++)

             a[i]=a[i-]*m;

         ll x=,y=;

         for (int i=;i<=n;i++)

             x+=a[gcd(i,n)];

         if (n%==) y=a[(n+)/]*n;

         else y=(a[n/]+a[n/+])*n/;

         printf("%lld %lld\n",x/n,(x+y)//n);

     }

 }

巴特西

Uva10294 Arif in Dhaka (置换问题)

最新文章

热门文章