math - 如何在排列组合中处理这类问题？
问题描述
海拔高度
爱丽丝和鲍勃去了山上。他们这几天一直在爬上爬下，N回到家时非常疲惫。
爱丽丝只记得他们在米高的地方开始了他们的旅程，他们在米的高度
H1结束了他们的流浪H2
。Bob 只记得他们每天都会将海拔高度改变A、B或C米。如果他们i当天的高度是x，那么他们当天的高度i + 1可以是x + A，，x + B或x + C。
现在，鲍勃想知道他们可以通过多少种方式完成他们的旅程。当且仅当存在爱丽丝和鲍勃在第一次旅程中当天覆盖的高度与爱丽丝和鲍勃在第二次旅程中当天覆盖的高度不同的一天时，两次旅程才被认为是不同的。
Bob 让 Alice 告诉她完成旅程的方法数量。Bob 需要您的帮助来解决这个问题。
输入格式
第一行也是唯一一行包含 6 个整数N, H1, H2, A, B，C分别代表 Alice 和 Bob 已经徘徊的天数、他们开始旅程的高度、完成旅程的高度以及三个可能的高度变化。
输出格式
打印答案模10**9 + 7。
约束
1 <= N <= 10**5
-10**9 <= H1, H2 <= 10**9
-10**9 <= A, B, C <= 10**9
样本输入
2 0 0 1 0 -1
样本输出
3
解释
只有 3 种可能的旅程—— (0, 0), (1, -1), (-1, 1)。
笔记
这个问题最初来自hackerearth 比赛，现已关闭。更正了示例输入和输出的解释。
解决方案
这是我在 Python 3 中的解决方案。
这个问题可以从它的 6 个输入参数简化为只有 4 个参数。不需要开始和结束高度——两者的差异就足够了。此外，如果我们对总海拔变化进行相应的更改，我们可以更改每日海拔变化 A、B 和 C，并得到相同的答案。例如，如果我们将 A、B 和 C 中的每一个都加 1，我们可以将 N 加到高度变化中：在 N 天内每天增加 1 米意味着总共增加 N 米。我们可以通过将每天的海拔变化“归一化”，使 A 最小，然后从每个海拔变化中减去 A，并从总海拔变化中减去 N * A。这意味着我们现在需要添加一堆 0 和另外两个值（我们称它们为 D 和 E）。D 不大于 E。
我们现在有一个更简单的问题：取 N 个值，每个值是 0、D 或 E，因此它们总和为一个特定的总数（假设为 H）。这与使用最多 N 个等于 D 或 E 的数字相同，其余为零。
我们可以使用数学，特别是Bezout 的恒等式，看看这是否可能。更多的数学可以找到执行此操作的所有方法。一旦我们知道有多少个 0、D 和 E，我们就可以使用多项式系数来找出这些值可以重新排列的方式。把所有这些加起来，我们就有了答案。
此代码查找完成旅程的方式总数，并仅在最后取模 10**9 + 7。这是可能的，因为 Python 使用大整数。我在测试中发现的最大结果是输入值100000 0 100000 0 1 2，它在取模之前产生一个 47,710 位的数字。这在我的机器上需要 8 秒多一点。
这段代码比必要的要长一点，因为我为这个问题做了一些比必要的更通用的例程。我这样做是为了可以在其他问题中使用它们。为了清楚起见，我使用了许多评论。
# Combinatorial routines -----------------------------------------------
def comb(n, k):
"""Compute the number of ways to choose k elements out of a pile of
n, ignoring the order of the elements. This is also called
combinations, or the binomial coefficient of n over k.
"""
if k < 0 or k > n:
return 0
result = 1
for i in range(min(k, n - k)):
result = result * (n - i) // (i + 1)
return result
def multcoeff(*args):
"""Return the multinomial coefficient
(n1 + n2 + ...)! / n1! / n2! / ..."""
if not args: # no parameters
return 1
# Find and store the index of the largest parameter so we can skip
# it (for efficiency)
skipndx = args.index(max(args))
newargs = args[:skipndx] + args[skipndx + 1:]
result = 1
num = args[skipndx] + 1 # a factor in the numerator
for n in newargs:
for den in range(1, n + 1): # a factor in the denominator
result = result * num // den
num += 1
return result
def new_multcoeff(prev_multcoeff, x, y, z, ag, bg):
"""Given a multinomial coefficient prev_multcoeff =
multcoeff(x-bg, y+ag, z+(bg-ag)), calculate multcoeff(x, y, z)).
NOTES: 1. This uses bg multiplications and bg divisions,
faster than doing multcoeff from scratch.
"""
result = prev_multcoeff
for d in range(1, ag + 1):
result *= y + d
for d in range(1, bg - ag + 1):
result *= z + d
for d in range(bg):
result //= x - d
return result
# Number theory routines -----------------------------------------------
def bezout(a, b):
"""For integers a and b, find an integral solution to
a*x + b*y = gcd(a, b).
RETURNS: (x, y, gcd)
NOTES: 1. This routine uses the convergents of the continued
fraction expansion of b / a, so it will be slightly
faster if a <= b, i.e. the parameters are sorted.
2. This routine ensures the gcd is nonnegative.
3. If a and/or b is zero, the corresponding x or y
will also be zero.
4. This routine is named after Bezout's identity, which
guarantees the existences of the solution x, y.
"""
if not a:
return (0, (b > 0) - (b < 0), abs(b)) # 2nd is sign(b)
p1, p = 0, 1 # numerators of the two previous convergents
q1, q = 1, 0 # denominators of the two previous convergents
negate_y = True # flag if negate y=q (True) or x=p (False)
quotient, remainder = divmod(b, a)
while remainder:
b, a = a, remainder
p, p1 = p * quotient + p1, p
q, q1 = q * quotient + q1, q
negate_y = not negate_y
quotient, remainder = divmod(b, a)
if a < 0:
p, q, a = -p, -q, -a # ensure the gcd is nonnegative
return (p, -q, a) if negate_y else (-p, q, a)
def byzantine_bball(a, b, s):
"""For nonnegative integers a, b, s, return information about
integer solutions x, y to a*x + b*y = s. This is
equivalent to finding a multiset containing only a and b that
sums to s. The name comes from getting a given basketball score
given scores for shots and free throws in a hypothetical game of
"byzantine basketball."
RETURNS: None if there is no solution, or an 8-tuple containing
x the smallest possible nonnegative integer value of
x.
y the value of y corresponding to the smallest
possible integral value of x. If this is negative,
there is no solution for nonnegative x, y.
g the greatest common divisor (gcd) of a, b.
u the found solution to a*u + b*v = g
v " "
ag a // g, or zero if g=0
bg b // g, or zero if g=0
sg s // g, or zero if g=0
NOTES: 1. If a and b are not both zero and one solution x, y is
returned, then all integer solutions are given by
x + t * bg, y - t * ag for any integer t.
2. This routine is slightly optimized for a <= b. In that
case, the solution returned also has the smallest sum
x + y among positive integer solutions.
"""
# Handle edge cases of zero parameter(s).
if 0 == a == b: # the only score possible from 0, 0 is 0
return (0, 0, 0, 0, 0, 0, 0, 0) if s == 0 else None
if a == 0:
sb = s // b
return (0, sb, b, 0, 1, 0, 1, sb) if s % b == 0 else None
if b == 0:
sa = s // a
return (sa, 0, a, 1, 0, 1, 0, sa) if s % a == 0 else None
# Find if the score is possible, ignoring the signs of x and y.
u, v, g = bezout(a, b)
if s % g:
return None # only multiples of the gcd are possible scores
# Find one way to get the score, ignoring the signs of x and y.
ag, bg, sg = a // g, b // g, s // g # we now have ag*u + bg*v = 1
x, y = sg * u, sg * v # we now have a*x + b*y = s
# Find the solution where x is nonnegative and as small as possible.
t = x // bg # Python rounds toward minus infinity--what we want
x, y = x - t * bg, y + t * ag
# Return the information
return (x, y, g, u, v, ag, bg, sg)
# Routines for this puzzle ---------------------------------------------
def altitude_reduced(n, h, d, e):
"""Return the number of distinct n-tuples containing only the
values 0, d, and e that sum to h. Assume that all these
numbers are integers and that 0 <= d <= e.
"""
# Handle some impossible special cases
if n < 0 or h < 0:
return 0
# Handle some other simple cases with zero values
if n == 0:
return 0 if h else 1
if 0 == d == e: # all step values are zero
return 0 if h else 1
if 0 == d or d == e: # e is the only non-zero step value
# If possible, return # of tuples with proper # of e's, the rest 0's
return 0 if h % e else comb(n, h // e)
# Handle the main case 0 < d < e
# --Try to get the solution with the fewest possible non-zero days:
# x d's and y e's and the rest zeros: all solutions are given by
# x + t * bg, y - t * ag
solutions_info = byzantine_bball(d, e, h)
if not solutions_info:
return 0 # no way at all to get h from d, e
x, y, _, _, _, ag, bg, _ = solutions_info
# --Loop over all solutions with nonnegative x, y, small enough x + y
result = 0
while y >= 0 and x + y <= n: # at most n non-zero days
# Find multcoeff(x, y, n - x - y), in a faster way
if result == 0: # 1st time through loop: no prev coeff available
amultcoeff = multcoeff(x, y, n - x - y)
else: # use previous multinomial coefficient
amultcoeff = new_multcoeff(amultcoeff, x, y, n - x - y, ag, bg)
result += amultcoeff
x, y = x + bg, y - ag # x+y increases by bg-ag >= 0
return result
def altitudes(input_str=None):
# Get the input
if input_str is None:
input_str = input('Numbers N H1 H2 A B C? ')
# input_str = '100000 0 100000 0 1 2' # replace with prev line for input
n, h1, h2, a, b, c = map(int, input_str.strip().split())
# Reduce the number of parameters by normalizing the values
h_diff = h2 - h1 # net altitude change
a, b, c = sorted((a, b, c)) # a is now the smallest
h, d, e = h_diff - n * a, b - a, c - a # reduce a to zero
# Solve the reduced problem
print(altitude_reduced(n, h, d, e) % (10**9 + 7))
if __name__ == '__main__':
altitudes()
这是我针对主要问题的一些测试例程。这些适用于pytest。
# Testing, some with pytest ---------------------------------------------------
import itertools # for testing
import collections # for testing
def brute(n, h, d, e):
"""Do alt_reduced with brute force."""
return sum(1 for v in itertools.product({0, d, e}, repeat=n)
if sum(v) == h)
def brute_count(n, d, e):
"""Count achieved heights with brute force."""
if n < 0:
return collections.Counter()
return collections.Counter(
sum(v) for v in itertools.product({0, d, e}, repeat=n)
)
def test_impossible():
assert altitude_reduced(0, 6, 1, 2) == 0
assert altitude_reduced(-1, 6, 1, 2) == 0
assert altitude_reduced(3, -1, 1, 2) == 0
def test_simple():
assert altitude_reduced(1, 0, 0, 0) == 1
assert altitude_reduced(1, 1, 0, 0) == 0
assert altitude_reduced(1, -1, 0, 0) == 0
assert altitude_reduced(1, 1, 0, 1) == 1
assert altitude_reduced(1, 1, 1, 1) == 1
assert altitude_reduced(1, 2, 0, 1) == 0
assert altitude_reduced(1, 2, 1, 1) == 0
assert altitude_reduced(2, 4, 0, 3) == 0
assert altitude_reduced(2, 4, 3, 3) == 0
assert altitude_reduced(2, 4, 0, 2) == 1
assert altitude_reduced(2, 4, 2, 2) == 1
assert altitude_reduced(3, 4, 0, 2) == 3
assert altitude_reduced(3, 4, 2, 2) == 3
assert altitude_reduced(4, 4, 0, 2) == 6
assert altitude_reduced(4, 4, 2, 2) == 6
assert altitude_reduced(2, 6, 0, 2) == 0
assert altitude_reduced(2, 6, 2, 2) == 0
def test_main():
N = 12
maxcnt = 0
for n in range(-1, N):
for d in range(N): # must have 0 <= d
for e in range(d, N): # must have d <= e
counts = brute_count(n, d, e)
for h, cnt in counts.items():
if cnt == 25653:
print(n, h, d, e, cnt)
maxcnt = max(maxcnt, cnt)
assert cnt == altitude_reduced(n, h, d, e)
print(maxcnt) # got 25653 for N = 12, (n, h, d, e) = (11, 11, 1, 2) etc.
推荐阅读
- scala - 为什么我无法在 EMR 上的 Spark scala 中打开本地文件
- python - Odoo 12 我无法更改计算字段的值
- javascript - Angularjs 中的格式 /Date(-226612800000)/
- c# - 在不导致 429 错误（请求太多）的情况下发出 API 请求的有效方法？
- docker - 通过摘要拉取 docker 镜像
- asp.net-mvc - 需要检查预订的天数
- javascript - OnClick 在 js 创建的按钮上不起作用
- r - 如何在R中制作四分之一圆极坐标图？
- grammar - J 编程语言 (E)BNF
- prometheus - Grafana 多值变量和 PromQL 查询标签过滤器