首页 > ACM题库 > HDU-杭电 > HDU 4048-Zhuge Liang’s Stone Sentinel Maze-计算几何-[解题报告]HOJ
2015
04-16

HDU 4048-Zhuge Liang’s Stone Sentinel Maze-计算几何-[解题报告]HOJ

Zhuge Liang’s Stone Sentinel Maze

问题描述 :

Raining

Zhuge Liang was a chancellor of the state of Shu Han during the Three Kingdoms period of Chinese history. He is often recognized as the greatest and most accomplished strategist of his era. He was so smart that his name also means “wise man” in Chinese.

One of Zhuge Liang’s achievements in legend is the Stone Sentinel Maze. It was an array of rocks and boulders built to defend against enemies. The formation was located on Yufu Shore by the Yangtze River near present-day Baidicheng, Chongqing, China, where supposed ruins of the array exist.

In chapter 84 of the historical novel Romance of the Three Kingdoms, as Lu Xun neared Baidicheng, he felt a strong enemy presence in the area and alerted his army to a possible ambush. He sent scouts ahead, who reported that the region was deserted except for some scattered piles of rocks. The bewildered Lu Xun asked a local, who told him that qi ("energy") started emerging from the area after Zhuge Liang arranged the rocks there. Lu Xun personally inspected the area and decided that the array was only a petty display of deception. Hence, Lu Xun led a few horsemen with him into the maze, and as he was about to exit, there was a strong gust of wind. At that moment, dust storms overshadowed the sky and the rocks appeared to become valleys; mountainous piles of dirt emerged and the roar of thunder rocked the skies while the waves of the nearby Yangtze River sounded like the clashing of swords and beating of war drums…

After the research on the Stone Sentinel Maze, scientists find some regulations. The rocks have m different kinds of weight (1<=m<=10,000). The weight of a rock is a positive integer not exceeding 10,000. There are n (3<=n<=100,000) rocks placed on a circle with equal spacing and the greatest common divisor of their weight is 1. They want to know in how many ways the rocks can be placed like that.

Notice:
1. Multiple rocks with the same weight can be placed on the circle.
2. If a solution will be the same as another one by rotation, these two solutions should be consider as the same.
3. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10,007.

输入:

The input begins with a line containing an integer T, the number of test cases.
For each case, the first line begins with two integers — the above mentioned m and n. Then m lines follow, each containing a positive integer representing rock weight. It is guaranteed that these m integers are different.

输出:

The input begins with a line containing an integer T, the number of test cases.
For each case, the first line begins with two integers — the above mentioned m and n. Then m lines follow, each containing a positive integer representing rock weight. It is guaranteed that these m integers are different.

样例输入:

2
2 3
2
3
3 3
6
10
15

样例输出:

2
2

题意:给出m种不同重量的石子, 每一种石子的个数无穷多。从中选出N个石子,排成一个环,使得环上的石子重量的最大公约数为1. 旋转同构视为相同方案。

解法:问题转化为从m种数中找出n(循环节个数)个最大公约数为1的数字的排列数,于是想到找补集:满足最大公约数为2的充分必要条件是所选的数都能被2整除,满足最大公约数为3的充分必要条件是所选的数都能被3整除,满足最大公约数为6的方案被重复计算了,于是要容斥原理解决。

       即对于m个数,msqrt(m)时间内统计这m个数中能被i整除的个数nn[i]然后对于n’, 假设g[i] = cnt[i] ^n,那么g[i]就是长度为N’的,最大公约数为i倍数的方案数。容斥时注意剪枝。

       题目中n可能于模数10007相同,此时不存在乘法逆元,因此不能通过乘法逆元除n,要将模数乘以n,然后在模意义下做二进制模乘以防溢出(貌似与Rho-Pollard有关,没仔细研究)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Main{
    int p[] = new int[2300], nn[] = new int[20010];
    void build() {
        boolean vis[] = new boolean[20010];
        int cnt = 0;
        p[0] = 1;
        for (int i = 2; i < 20010; i++)
            if (!vis[i]) {
                p[++cnt] = i;
                int j = i;
                while (j < 20010) {
                    vis[j] = true;
                    j += i;
                }
            }
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(
            new InputStreamReader(System.in)));

    int nextInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }

    int prime[] = new int[10010], count[] = new int[10010], cnt;
    void divide(int n) {
        cnt = 0;// 质因子数目
        int mx = (int) (Math.sqrt(n) + 3);
        if (n < mx)
            mx = n;
        for (int i = 2; i < mx; i++) {
            if (n == 1)
                break;
            if (n % i == 0) {
                prime[++cnt] = i;
                count[cnt] = 0;
                while (n % i == 0) {
                    n /= i;
                    count[cnt]++;
                }
            }
        }
        if (n != 1) {
            prime[++cnt] = n;
            count[cnt] = 1;
        }
    }

    long pow(long x, long p) {
        long ans = 1;
        while (p > 0) {
            if ((p & 1) == 1)
                ans = muti_mod(ans,x);
            p >>= 1;
            x = muti_mod(x,x);// x*x can be long even x is int
        }
        return ans;
    }

    long muti_mod(long a, long b)
    {
        long n=mod;
        long exp = a % n, res = 0;
        while (b>0)
        {
            if ((b & 1)==1)
            {
                res += exp;
                if (res > n)
                    res -= n;
            }
            exp <<= 1;
            if (exp > n)
                exp -= n;

            b >>= 1;
        }
        return res;
    }

    long get(int now, int sum, long k) {
        long ans = pow(nn[sum], k);
        for (int i = now + 1; p[i]*sum<=mx; i++)
            if (nn[p[i]*sum] >0)
                ans = (ans - get(i, sum * p[i], k) + mod)% mod;
        return ans;
    }

    long ans, mx;
    void dfs(int now, long value, long euler) {
        if (now == cnt + 1) {// value是n的因子
            long temp = get(0, 1, n / value);
            ans = (ans + euler * temp) % mod;
            return;
        }
        dfs(now + 1, value, euler);
        long temp = prime[now];
        for (int i = 1; i <= count[now]; i++) {
            dfs(now + 1, value * temp, muti_mod(euler * (prime[now] - 1),
                    (temp / prime[now]) ));
            temp = muti_mod(prime[now],temp);
        }
    }

    long polya() {
        ans = 0;
        divide(n);
        dfs(1, 1, 1);
        ans/=n;
        mod/=n;
        ans%=mod;
        ans+=mod;
        ans%=mod;
        return ans;
    }

    int m, n;
     int mod ;
    void run() throws IOException {
        int cas = nextInt();
        build();
        while (cas-- > 0) {
            m = nextInt();
            n = nextInt();
            mod= 10007*n;
            Arrays.fill(nn, 0);
            mx = -1;
            for (int i = 0; i < m; i++) {
                int x = nextInt();
                if (x > mx)
                    mx = x;
                int j;
                for (j = 1; j * j < x; j++)
                    if (x % j == 0) {
                        nn[j]++;
                        nn[x / j]++;
                    }
                if (j * j == x)
                    nn[j]++;
            }
            System.out.println(polya());
        }
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/kksleric/article/details/7821750


  1. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  2. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

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