首页 > ACM题库 > HDU-杭电 > HDU 2901-Message-快速幂-[解题报告]HOJ
2014
02-21

HDU 2901-Message-快速幂-[解题报告]HOJ

Message

问题描述 :

When little Sascha grew up, she lost her bad habit of pronouncing words in ways that were most easy for her, but did not always match the correct-pronunciation. However, she never lost the linguistic creativity she used to show as a little girl. When the Earth Allied Forces (EAF) discovered she also had brilliant mathematical insights and a knack for puzzles and secret messages,she was immediately offered the position of Head of the EAF Intelligence Department.

Sascha’s current task is interpreting intercepted internal messages of the hostile Mars Feder-ation. Although Martian messages always consist of just one word, her task turns out not to be easy, as two factors in uence the content of the intercepted message:

a) Extraterrestrial environment conditions are so bad that errors can occur in intercepted messages, causing them to be quite obfuscated compared to the originally sent text. If such errors occur, the erroneous characters will be characters from the Martian alphabet, just as the original characters.

b) Furthermore, linguistic characteristics play an important role. In Martian, there are relations between two subsequent characters: for a given character, some characters are more likely predecessors than others (note that something similar occurs in English: for example, a `h’ in a word will more likely have been preceded by a ‘t’ than by a `q’).

Fortunately, probabilities that a received character y actually was sent as an original Martian character x is known for all alphabet characters, as well as the probabilities that a certain character xi occurs in a clean Martian word if it was preceded by a Martian character x(i-1).

Given all these probabilities, Sascha wants to nd the so-called maximum likelihood text for a received message, which is the most likely message the Martians originally sent. As senior pro-grammer in the EAF Intelligence Department, you must write a program for her, achieving this goal for several intercepted messages in several local Martian dialects.

To give a simple example, consider a local Martian alphabet only consisting of the characters ‘a’ and ‘b’ and let the receiving error probabilities and character succession probabilities be as shown in Table 2. If the intercepted message just consists of an `a’, this can either originally have been an `a’ or a `b’. With no previous characters available, only the error probabilities are considered: it then turns out that the maximum likelihood message is an `a’ as well, with probability 0.9.


Table 2: Example Receiving Error Probabilities (left) and Character Succession Probabilities(right).

To extend the example, if the intercepted message was `ab’, we also need the character succession probabilities. The probability that the original message was `aa’ is

p(received `a’ indeed was originally sent as `a’)

*p(received ‘b’ was originally sent as `a’) *p(character `a’ succeeds previous `a’)

= 0.9 * 0.1 * 0.8:

Similarly, the probability that the original message was `bb’, `ab’ or `ba’ are 0.1 * 0.9 * 0.95, 0.9* 0.9 * 0.05 and 0.1 * 0.1 *0.2, respectively. Hence, the maximum likelihood message now is `bb’. In all cases asked for, there will always be a unique maximum likelihood message.

输入:

The _rst line of input consists of the integer number n, the number of test cases;

Then, for each test case:

- An integer number a (0 < a < 30), which is the number of characters in the local Martian alphabet;

- A line containing the a unique characters c1; c2; ….. ; ca of the local Martian alphabet,separated by single spaces. Whitespace characters will not occur in the alphabet;
- a lines, specifying receiving error probabilities for the a alphabet characters in the orderin which they were presented. The ith line corresponds to the error probabilities for the original alphabet character ci and contains:

* a floating point numbers ei1; ei2; …..; eia, separated by single spaces. Number eij(0 <=eij <= 1) indicates the probability that an observed character cj originally was sent as the character ci (hence );

- a lines, specifying character succession probabilities for the a alphabet characters in theorder in which they were presented. The ith line corresponds to the character succession probabilities for cases where the original alphabet character ci was the immediate predecessor and contains:

* a floating point numbers si1; si2; …. ; sia, separated by single spaces. Number sij indicates the probability that a certain character cj has character ci as immediate predecessor (hence );

- An integer number w (0 < w < 50), indicating the number of intercepted messages in the local Martian alphabet specified;

- Then, for each intercepted message:

- A line containing the intercepted message. These messages are non-empty, case-sensitive and will not exceed 300 characters in length.

Given _oating point numbers never have more than 10 decimal numbers following the separator ‘.’

输出:

The _rst line of input consists of the integer number n, the number of test cases;

Then, for each test case:

- An integer number a (0 < a < 30), which is the number of characters in the local Martian alphabet;

- A line containing the a unique characters c1; c2; ….. ; ca of the local Martian alphabet,separated by single spaces. Whitespace characters will not occur in the alphabet;
- a lines, specifying receiving error probabilities for the a alphabet characters in the orderin which they were presented. The ith line corresponds to the error probabilities for the original alphabet character ci and contains:

* a floating point numbers ei1; ei2; …..; eia, separated by single spaces. Number eij(0 <=eij <= 1) indicates the probability that an observed character cj originally was sent as the character ci (hence );

- a lines, specifying character succession probabilities for the a alphabet characters in theorder in which they were presented. The ith line corresponds to the character succession probabilities for cases where the original alphabet character ci was the immediate predecessor and contains:

* a floating point numbers si1; si2; …. ; sia, separated by single spaces. Number sij indicates the probability that a certain character cj has character ci as immediate predecessor (hence );

- An integer number w (0 < w < 50), indicating the number of intercepted messages in the local Martian alphabet specified;

- Then, for each intercepted message:

- A line containing the intercepted message. These messages are non-empty, case-sensitive and will not exceed 300 characters in length.

Given _oating point numbers never have more than 10 decimal numbers following the separator ‘.’

样例输入:

1
2
a b
0.9 0.1
0.1 0.9
0.8 0.05
0.2 0.95
2
a
ab

样例输出:

a
bb

大部分解释来自:

http://hi.baidu.com/timer/item/ebc8c7ef908085215b2d6476

题意:

求 (1^b+ 2^b+ … + a^b) % a     

1≤a≤1000000000, 1≤b≤1000000000

思路:

a,b范围很大,直接算或者直接用快速幂取模肯定不行。

注意到题目条件:b一定是一个奇数。

观察原式,发现  [ c^b+(a-c)^b ] % a = 0 .

(证明:将 (a-c)^b 用二项式定理拆开即可)

于是这样就简单了:当a是奇数时,原式=0;当a是偶数时,原式=(a/2)^b % a .再快速幂取模即出解。

自己敲:

#include <cstdio>

using namespace std;

typedef long long ll;
int mod;
ll mypow(ll a, ll n)
{
    ll ret = 1;
    while(n)
    {
        if(n%2) ret = (ret*a)%mod;
        a = (a*a)%mod;
        n >>= 1;
    }
    return ret;
}
int cal(int a, int b)
{
    if(a&1) return 0;
    return mypow(a/2,b);
}
int main()
{
    int a,b;
    while(scanf("%d %d",&a,&b)==2)
    {
        mod = a;
        printf("%d\n",cal(a,b));
    }
}

目前还是图样…

解题参考:http://blog.csdn.net/iyundi/article/details/9903297


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

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

  3. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  4. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  5. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.