ACM – Uva10294 – 置换

点击量:36

项链和手镯。

项链的问题在于不可以翻转,因此少了一种置换,而手镯则可以反转。然后我们计算旋转的置换。

旋转的步长可以是0,i,2i…然后我们可以得出循环一共有n/gcd(i,n)个元素,因此,我们可以计算出一共有gcd(i,n)个循环。则不定点的个数为
$a = \Sigma t^{gcd(i,n)}$。

翻转。翻转奇数情况和偶数情况是不一样的,因为奇数情况会多一个不定点,这个不定点就是在轴上的点。剩余的不定点的个数就是$n/2$,总共不定点的个数就是$nt^{(n+1)/2}$。偶数的情况下,如果正好切在两个珠子上,那么循环长度为2的点有$n/2-1$个,长度为1的循环有2个,所以总共$n/2+1$个。如果没有切在珠子上,不定点的个数为$n/2$,和为$b = n/2*(t^{n/2+1} + t^{n/2})$。

然后我们可以计算出项链的个数$a/n$,手镯的个数$(a+b)/2n$

列出式子以后代码就方便了。记得求pow的时候可以顺手打表

/*=============================================================================
#
# Author: svtter - svtter@qq.com
#
# QQ : 57180160
#
# Last modified: 2015-05-03 18:48
#
# Filename: 10294.cpp
#
# Description: 
#
=============================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
#define CR printf("\n")
const double PI = acos(-1.0);
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a%b);
}
const int maxn = 60;
ll po[maxn];
int main()
{
#ifdef DEBUG
    // freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int n, t;
    ll ans, ans2;
    while(scanf("%d%d", &n, &t) != EOF && n)
    {
        po[0] = 1;
        ans = 0;
        for(int i = 1; i <= n; i++) po[i] = po[i-1] * t;
        for(int i = 0; i < n;i++) ans += po[gcd(i, n)];
        ans2 = ans;
        if(n & 1) ans2 += n*po[(n+1)/2];
        else ans2 += n/2*(po[n/2+1] + po[n/2]);
        printf("%lld %lld\n", ans/n, ans2/(2*n));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注