-3

我参加了 101 Hack June Challenge 比赛，但有两个问题我无法解决。谁能给我一些关于如何解决这两个问题的提示：

Q1。分配问题

Calvin 在学校有一项数学作业，他必须评估很多表达式。卡尔文决定不浪费太多时间。总体上有'M'表达式。通过查看 Susie 的答案，Calvin 发现所有问题的答案都形成了一个非递减序列。

他决定他所有的答案都将在 1 和“N”（包括）之间。他用长度为“M”的随机非递减序列填写答卷，其中每个元素都在 1 和“N”之间。

这是卡尔文真正问题开始的部分。他不想选择一个很大的 N 值，因为，他会有很多选择。此外，如果他选择了一个非常小的 N 值，很多答案会变得相等，老师会产生怀疑。

如果 x = max1 ≤ i ≤ N（频率 (i)），频率 (i) 是 i 在他选择的“M”值序列中出现的次数。Calvin 想要找出 x 的期望值。帮助他解决问题。

例如，如果 M = 3 & N = 3，则可能的序列为：

1 1 1 (x = 3)
1 1 2 (x = 2)
1 1 3 (x = 2)
1 2 2 (x = 2)
1 2 3 (x = 1)
1 3 3 (x = 2)
2 2 2 (x = 3)
2 2 3 (x = 2)
2 3 3 (x = 2)
3 3 3 (x = 3)

expected value of x = 2.2

输入格式

第一行包含一个整数 T，表示测试用例的数量。接下来是 T 行，每行包含 2 个数字，M 和 N 用于对应的测试用例。

约束

T ≤ 15
1 ≤ M ≤ 250
1 ≤ N ≤ 10^9

输出格式

输出 T 行，每行包含对应测试用例的答案。最多允许 10^-3 的误差。

样本输入

4
1 5
3 3
2 9
9 6

样本输出

1.0000000000
2.2000000000
1.2000000000
4.3146853147

Q2。GCD 无酒精鸡尾酒

义军同盟和银河帝国在恩多上空展开了一场史诗般的战斗。宏伟的设置有 d 维板，每个维度的长度为“N”，（即）N x N…（d 次）。每个单元格 (i1, i2, ...id) 上都写有 gcd (i1, i2, ...id)。

现在，游戏开始了。选择一个随机整数 L，第一个将每个数字的 L 次方求和并以 30000001 为模的第一人获胜。

Rebel Alliance 需要一些帮助并通知您。如果他们赢了，你会得到一百万美元。你能帮我吗？

输入格式

有几个测试用例。第一行包含测试用例 T 的数量。然后是 T 个测试用例。每个测试用例都以下列格式给出。N 和 d 在第一行中给出。Q 在第二行给出。接下来的 Q 行中的每一行都包含一个整数 L。

约束

0 <= T <= 10
1 <= N <= 107
1 <= d <= 1000
0 <= L <= 100
0 <= Q <= 50

输出格式

对于每个测试用例，输出 Q 行，表示答案。

样本输入

3
3 2
4
0
1
2
3
5 1
3
0
1
2
6 3
2
2
3

样本输出

9
12
20
42
5
15
55
421
975

这是网站上问题的链接：

Q1。https://www.hackerrank.com/contests/101june13/challenges/assignment

Q2。https://www.hackerrank.com/contests/101june13/challenges/gcd-mocktail

比赛已经结束，所以我想这不是在 Stackoverflow 上寻求帮助的作弊行为。

4

2 回答 2

1

对于第二季度：

让我们从计算每个值在这样一个数组中出现的次数开始：

1 - 每当位置互质时出现。这很难直接计算，所以让我们暂时忽略它。

2 - 当所有位置都是 2 的倍数时出现。有多少个数字组合[1, N]都是 2 的倍数，允许重复？第一个值有N / 2可能，所有其他d值也有同样多的可能性，所以(N / 2)^d可能性。但是，我们也计算了那些都是 LARGER 倍数的，这将产生更大的 GCD。所以我们必须从更大的倍数中减去那些形成的，即(N / 4)^d + (N / 6)^d + ...

k <= N- 可以同上推导。让num(k)这个值。

因此，将出现 1N^d - num(2) - num(3) - ...次。

所以你必须计算总和：

S = num(1) + num(2) * 2^L + num(3) * 3^L + ...

如果您直接实现它，这将给出一个O(N^2 * L)或O(N^2 log L)解决方案，这太慢了，因为N可以上升到10^7. 我们必须做得更好。

让我们写出S：

S =   N^d - num(2) - num(3) - ...
    + num(2) * 2^L + num(3) * 3^L + ...
  = N^d + num(2)(2^L - 1) + num(3)(3^L - 1) + ...
  = N^d + [(N / 2)^d - (N / 4)^d - ...](2^L - 1) 
        + [(N / 3)^d - (N / 6)^d - ...](3^L - 1)
        + [(N / 4)^d - (N / 8)^d - ...](4^L - 1)
        + ...

很多术语会重复自己，但到目前为止，我不知道从哪里开始。我会留下这个，以防它帮助任何人更进一步，如果有人发布完整的解决方案，我会删除它。

于 2013-06-30T12:50:13.990 回答
0

对于 Q1，想象一下，如果您知道该函数为您提供了在to范围内f(N, M, K)的非递减M整数序列最多可以重复的方式数。然后给你完全重复的数字。现在我们得到了准确的分布，给出了准确的答案。1NKf(N, M, K) - f(N, M, K-1)K

现在f(N, M, K)显然是0如果0 = K和0 < M。而且f(N, 0, 0)是琐碎的1。（只有一个空集。）加上这样一个事实，f(N, M, K) = f(N, M, K-1) + f(N-1, M-K, K)我们都准备好用动态规划来解决了。N（主要挑战是如果是十亿，你可能会超出浮点范围，并且M是 250...）

我不得不考虑Q2。我有一个想法如何做到这一点，但对我来说并不那么简单。

于 2013-06-30T08:13:24.537 回答