【UVa 10294】Arif in Dhaka (First Love Part 2)(Polya定理)

Description

click me
默默复制了vjudge的链接(逃

Solution

可以XJB乱模拟算的题目为什么要用群论
题中有两种置换:

  1. 旋转
    对于跨度为$i$的旋转,则有$(i,n)$个循环、每个循环有$\frac{n}{(i,n)}$个元素(对称性)。
    则旋转的不动点总数为:$$A=\sum_{i=0}^{n}t^{(i,n)}$$
  2. 翻转
    对于翻转,有两种情况
  • 偶数
    有两种对称轴:
    穿过珠子的形成$\frac{n}{2}-1$个长度为$2$的循环和$2$个长度为$1$的循环。
    不穿过珠子的形成$\frac{n}{2}$个长度为$2$的循环。
    两种对称轴各为$\frac{n}{2}$条。
    不动点总数为$$B=\frac{n}{2}(t^{\frac{n}{2}+1}+t^{\frac{n}{2}})$$
  • 奇数
    有$n$条对称轴,都形成了$\frac{n-1}{2}$个长度为$2$的循环和$1$个长度为$1$的循环。
    不动点总数为$$B=nt^{\frac{n+1}{2}}$$
    根据$Polya$定理,项链总数为$\frac{A}{n}$,手镯总数为$\frac{A+B}{2n}$。
    应该抄得跟LRJ一字不漏吧。。

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/****************************
* Au: Hany01
* Prob: UVa 10294 Arif in Dhaka (First Love Part 2)
* Date: Feb 1st, 2018
* Email: hany01@foxmail.com
****************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define rep(i , j) for (int i = 0 , i##_end_ = j; i < i##_end_ ; ++ i)
#define For(i , j , k) for (int i = (j) , i##_end_ = (k) ; i <= i##_end_ ; ++ i)
#define Fordown(i , j , k) for (int i = (j) , i##_end_ = (k) ; i >= i##_end_ ; -- i)
#define Set(a , b) memset(a , b , sizeof(a))
#define SZ(a) ((int)(a.size()))
#define ALL(a) a.begin(), a.end()
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define y1 wozenmezhemecaia
#ifdef hany01
#define debug(...) fprintf(stderr , __VA_ARGS__)
#else
#define debug(...)
#endif
inline void File() {
#ifdef hany01
freopen("uva10294.in" , "r" , stdin);
freopen("uva10294.out" , "w" , stdout);
#endif
}
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
inline int gcd(int x, int y) { return x ? gcd(y % x, x) : y; }
const int maxn = 53;
LL Pow[maxn], Ans1, Ans2;
int n, t;
int main()
{
File();
Pow[0] = 1;
while (scanf("%d%d", &n, &t) != EOF) {
For(i, 1, n) Pow[i] = Pow[i - 1] * t;
Ans1 = 0;
For(i, 1, n) Ans1 += Pow[gcd(i, n)];
Ans2 = (n & 1) ? Pow[(n >> 1) + 1] * n : (Pow[n >> 1] + Pow[(n >> 1) + 1]) * (n >> 1);
cout << Ans1 / n << ' ' << (Ans1 + Ans2) / (n << 1) << endl;
}
return 0;
}
Contents
  1. 1. Description
  2. 2. Solution
  3. 3. Source Code