【set去重】矩阵中不重复的数

一个m*n的矩阵。
该矩阵的第一列是a^b,(a+1)^b,…..(a + n – 1)^b
第二列是a^(b+1),(a+1)^(b+1),…..(a + n – 1)^(b+1)
…….
第m列是a^(b + m – 1),(a+1)^(b + m – 1),…..(a + n – 1)^(b + m – 1)
(a^b表示a的b次方)
下面是一个4*4的矩阵:
2^2=4, 2^3=8, 2^4=16, 2^5=32
3^2=9, 3^3=27, 3^4=81, 3^5=243
4^2=16, 4^3=64, 4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125
问这个矩阵里有多少不重复的数(比如4^3 = 8^2,这样的话就有重复了)
2^2=4, 2^3=8, 2^4=16, 2^5=32
3^2=9, 3^3=27, 3^4=81, 3^5=243
4^2=16, 4^3=64, 4^4=256, 4^5=1024
m = 4, n = 3, a = 2, b = 2。其中2^4与4^2是重复的元素。 继续阅读【set去重】矩阵中不重复的数

【概率期望】Island of Survival

You are in a reality show, and the show is way too real that they threw into an island. Only two kinds of animals are in the island, the tigers and the deer. Though unfortunate but the truth is that, each day exactly two animals meet each other. So, the outcomes are one of the following

a)If you and a tiger meet, the tiger will surely kill you.
b)If a tiger and a deer meet, the tiger will eat the deer.
c)If two deer meet, nothing happens.
d)If you meet a deer, you may or may not kill the deer (depends on you).
e)If two tigers meet, they will fight each other till death. So, both will be killed.

If in some day you are sure that you will not be killed, you leave the island immediately and thus win the reality show. And you can assume that two animals in each day are chosen uniformly at random from the set of living creatures in the island (including you).

Now you want to find the expected probability of you winning the game. Since in outcome (d), you can make your own decision, you want to maximize the probability. 继续阅读【概率期望】Island of Survival

【概率】Birthday Paradox

Sometimes some mathematical results are hard to believe. One of the common problems is the birthday paradox. Suppose you are in a party where there are 23 people including you. What is the probability that at least two people in the party have same birthday? Surprisingly the result is more than 0.5. Now here you have to do the opposite. You have given the number of days in a year. Remember that you can be in a different planet, for example, in Mars, a year is 669 days long. You have to find the minimum number of people you have to invite in a party such that the probability of at least two people in the party have same birthday is at least 0.5. 继续阅读【概率】Birthday Paradox

【概率DP】Just another Robbery

As Harry Potter series is over, Harry has no job. Since he wants to make quick money, (he wants everything quick!) so he decided to rob banks. He wants to make a calculated risk, and grab as much money as possible. But his friends – Hermione and Ron have decided upon a tolerable probability P of getting caught. They feel that he is safe enough if the banks he robs together give a probability less than P. 继续阅读【概率DP】Just another Robbery

【欧拉函数】Visible Lattice Points

Description

A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 ≤ x, y ≤ 5 with lines from the origin to the visible points.

Write a program which, given a value for the size, N, computes the number of visible points (x, y) with 0 ≤ x, y ≤ N. 继续阅读【欧拉函数】Visible Lattice Points