首页 > ACM题库 > HDU-杭电 > HDU 2865-Birthday Toy-最小生成树-[解题报告]HOJ
2014
02-17

HDU 2865-Birthday Toy-最小生成树-[解题报告]HOJ

Birthday Toy

问题描述 :

AekdyCoin loves toys. It is AekdyCoin’s Birthday today and he gets a special “Toy”.
The “Toy” is in bulk and AekdyCoin has to make one by him. Let’s assume that the “Toy” has N small white beads and one Big bead .If someone want to make a “Toy”, he (or she) must always puts the Big bead in center, and then connect the other N small beads around it by using N sticks with equal length, and then the N small beads must be connected by N sticks with equal length, and it could be seen as a regular polygon. Figure 1 shows a “Toy” with 8 small white beads and one big white bead.

Now AekdyCoin has C kinds of available color, say blue, green, yellow, pink …etc. He wants to color these beads, but he thinks that must be too boring and stupid. So he colors these beads with one role: any adjacent beads couldn’t have same color. Figure 2 shows a legal situation, and Figure 3 shows an illegal situation.


It seems that the “Toy” becomes more interesting for AekdyCoin right now; however, he wants to color the big bead in center. Of course, he should follow the role above.

Now AekdyCoin begins to play with the “Toy”, he always colors the big beads and then the other small beads. He should color under the rule above. After several minutes, AekdyCoin finally makes a perfect “Toy”. Figure 4 shows a situation that is under the color rule.


AekdyCoin now want to know the different method to color the “Toy” whit at most K color. (“Toy” contains N small beads and one big bead.)
But, no, the problem is not so easy .The repetitions that are produced by rotation around the center of the circular necklace are all neglected. Figure 5 shows 8 “Toy”, they are regard as one method.


Now AekdyCoin will give you N and K, he wants you to help him calculate the number of different methods, because the number of method is so huge, so AekdyCoin just want you to tell him the remainder when divided by M.
In this problem, M = 1,000,000,007.

输入:

The input consists of several test cases.(at least 1000)
Every case has only two integers indicating N, K
(3<=N<=10^9, 4<=K<=10^9)

输出:

The input consists of several test cases.(at least 1000)
Every case has only two integers indicating N, K
(3<=N<=10^9, 4<=K<=10^9)

样例输入:

3 4
3 5
3 17
162 78923

样例输出:

8
40
19040
19469065

HDU_2865

    由于有相同颜色不能相邻这一限制,我们就需要用dp去计算burnside引理中的C(f)了。

    按常规套路来,先将N的约数找到,接着对于每个任意约数R,就可以找到循环节数量为R的置换数了,然后需要用dp计算出对于有R个循环节的置换下的“不动方案”的数量。

    首先,中间的圆圈的颜色是任意的,而且对于每种颜色而言“不动方案”的数量是一致的,也就是说中间的圆圈有K个颜色可选,而我们只需要计算任意一个情况就可以了,最后乘K就是总数。

    接下来小圆圈就剩下K-1个颜色可选了,而我们需要计算长度为R的一串珠子的合法方案数,所谓合法就是相邻的珠子不能同色,以及首尾珠子不能同色。这时第1个珠子有K-1个颜色可选,而且对于其选择任意一种颜色,最终的结果都是一样的,所以我们只需计算其中一种情况,最后乘以K-1就可以了。

    比如我第1个珠子选了黄色,那么在dp的时候就可以用f[i][1]表示第i个珠子是黄色的合法方案数,f[i][0]表示第i个珠子不是黄色的合法方案数,那么不难得到f[i][1]=f[i-1][0],f[i][0]=(K-3)*f[i-1][0]+(K-2)*f[i-1][1],最后的合法方案数就是f[R][0],由于N比较大,我们可以用二分矩阵的方法加速求解过程。

    到此,C(f)已经计算出来了,接下来的工作就是求N的逆元并计算最终的结果了。

    另外推荐一个讲解得很详细的用dp计算Burnside中C(f)的一篇文章:http://hi.baidu.com/billdu/item/62319f2554c7cac9a5275a0d

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXD 40010
#define MOD 1000000007
using namespace std;
int N, K, isprime[MAXD], prime[MAXD], P, d[MAXD], D;
struct Matrix
{
    long long a[2][2];
    void init()
    {
        memset(a, 0, sizeof(a));
    }
}unit, mat;
Matrix multiply(Matrix &x, Matrix &y)
{
    int i, j, k;
    Matrix z;
    z.init();
    for(i = 0; i < 2; i ++)
        for(j = 0; j < 2; j ++)
        {
            for(k = 0; k < 2; k ++)
                z.a[i][j] += x.a[i][k] * y.a[k][j];
            z.a[i][j] %= MOD;
        }
    return z;
}
void prepare()
{
    int i, j, k = 40000;
    memset(isprime, -1, sizeof(isprime));
    P = 0;
    for(i = 2; i <= k; i ++)
        if(isprime[i])
        {
            prime[P ++] = i;
            for(j = i * i; j <= k; j += i)
                isprime[j] = 0;
        }
}
void divide(int n)
{
    int i;
    D = 0;
    for(i = 1; i * i <= n; i ++)
        if(n % i == 0)
        {
            d[D ++] = i;
            if(n / i != i)
                d[D ++] = n / i;
        }
    sort(d, d + D);
}
int euler(int n)
{
    int i, x, ans;
    ans = x = n;
    for(i = 0; i < P && prime[i] * prime[i] <= n; i ++)
        if(x % prime[i] == 0)
        {
            ans = ans / prime[i] * (prime[i] - 1);
            while(x % prime[i] == 0)
                x /= prime[i];
        }
    if(x > 1)
        ans = ans / x * (x - 1);
    return ans;
}
void powmod(Matrix &unit, Matrix &mat, int n)
{
    while(n)
    {
        if(n & 1)
            unit = multiply(mat, unit);
        n >>= 1;
        mat = multiply(mat, mat);
    }
}
void exgcd(long long a, long long b, long long &x, long long &y)
{
    if(b == 0)
        x = 1, y = 0;
    else
        exgcd(b, a % b, y, x), y -= x * (a / b);
}
void solve()
{
    int i, j;
    long long x, y, ans = 0, n;
    divide(N);
    for(i = 0; i < D; i ++)
    {
        n = euler(N / d[i]);
        unit.init();
        unit.a[1][0] = 1;
        mat.a[0][0] = K - 3, mat.a[0][1] = K - 2, mat.a[1][0] = 1, mat.a[1][1] = 0;
        powmod(unit, mat, d[i] - 1);
        ans = (ans + ((n * K % MOD) * (K - 1) % MOD) * unit.a[0][0] % MOD) % MOD;
    }
    exgcd(N, MOD, x, y);
    x = (x % MOD + MOD) % MOD;
    ans = ans * x % MOD;
    printf("%lld\n", ans);
}
int main()
{
    prepare();
    while(scanf("%d%d", &N, &K) == 2)
    {
        solve();
    }
    return 0;
}

解题参考:http://www.cnblogs.com/staginner/archive/2012/05/17/2506040.html


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  3. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  4. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }