主页 / 问题 / 1604679
Accepted
user27630724
Asked:2025-01-13 01:01:45 +0800 CST2025-01-13 01:01:45 +0800 CST

DP锯齿。不靠记忆

  • 772

问题 F：斜坡序列

如果每个元素严格大于或严格小于其邻居，我们将其称为序列锯齿。给定数字n和k，确定由数字1, ..., k组成的长度为n的锯齿序列的数量。

输入格式

该程序接收两个自然数n和k作为输入，1 ≤ n ≤ 4000、1 ≤ k ≤ 4000。

结果格式

需要求出所需序列数除以10 9 +7的余数。

示例

输入数据 工作成果
3 3 10
20 3 35422

磷

def calculate_zigzag_patterns(length, max_value):
    if length == 1:
        return max_value

    increasing = [0] * (max_value + 1)
    decreasing = [0] * (max_value + 1)

    for index in range(1, max_value + 1):
        increasing[index] = 1
        decreasing[index] = 1

    for current_length in range(2, length + 1):
        new_increasing = [0] * (max_value + 1)
        new_decreasing = [0] * (max_value + 1)

        total_decreasing = 0
        for last_value in range(1, max_value + 1):
            total_decreasing += decreasing[last_value - 1]
            new_increasing[last_value] = total_decreasing

        total_increasing = 0
        for last_value in range(max_value, 0, -1):
            if last_value < max_value:
                total_increasing += increasing[last_value + 1]
            new_decreasing[last_value] = total_increasing

        increasing, new_increasing = new_increasing, increasing
        decreasing, new_decreasing = new_decreasing, decreasing

    final_result = sum(increasing[last_value] + decreasing[last_value] for last_value in range(1, max_value + 1))
    return final_result

length, max_value = map(int, input().split())
result = calculate_zigzag_patterns(length, max_value)
print(result % (10 ** 9 + 7))
python

3 个回答

  1. 表的大小很小并且不会通过内存，显然是因为您用长数字填充表并仅在最后取模余数。

    % 1000000007 每次添加时执行

    • 4
  2. Best Answer

    锯齿序列有齿向上和齿向下。它们的数量相同。问题中的代码将它们分开计数，您可以将其速度加快两倍。n = 1成为特殊情况。

    def n_seqs(n, k):
    if n == 1:
        return k
    mod = 10 ** 9 + 7 
    a = [1] * (k - 1)
    for _ in range(1, n):
        b = []
        s = 0
        for ai in a:
            s = (s + ai) % mod
            b.append(s)
        a = b[::-1]
    return 2 * sum(a) % mod


print(n_seqs(*map(int, input().split())))

    需要很少的内存。在最大尺寸下，时间几乎是一秒：

    $ time -p echo 4000 4000 | python sawlike.py
380392195
real 0.62
user 0.62
sys 0.00

    上面的代码对一端自由、另一端固定的序列进行计数：序列以某个值结束。让我们将n大约分成两半，计算序列“一半”的数量，并将左半部分乘以右半部分。这将使时间加倍。

    MOD = 10 ** 9 + 7 


def step(a):
    b = []
    s = 0
    for ai in a:
        s = (s + ai) % MOD
        b.append(s)
    return b[::-1]


def n_seqs(n, k):
    if n == 1:
        return k

    a = [1] * (k - 1)
    for _ in range((n - 1) // 2):
        a = step(a)
    l = a
    r = step(a) if n % 2 == 0 else a
    return 2 * sum(li * ri for li, ri in zip(l, r)) % MOD


print(n_seqs(*map(int, input().split())))

    $ time -p echo 4000 4000 | python sawlike.py
380392195
real 0.33
user 0.32
sys 0.00

    不幸的是，该方法无法扩展：如果我们考虑进一步的二分和分而治之，我们将需要两端固定的序列，并且有k 2个。这与将问题翻译成矩阵语言相同：step它描述了由矩阵表示的线性映射。通过快速将该矩阵求n-1次方即可解决该问题。矩阵大小k 2。时间会比k 2 log n差，内存会相同。我们已经有了一个带有内存k 的算法nk。这种优化是相反的；如果k < √n ，则效果很好。仍然希望矩阵表示是冗余的，并且可以组织对k中线性结构的计算。我没有想出这样的结构。

    k中的动力学没有起作用。

    我们可以挖掘生成函数：

    • k = 3给出序列3, 6, 10, 16, 26, ...。从第二个元素开始，这些是双斐波那契数。

    • k = 4给出序列4, 12, 28, 62, 140, ...。从第二个元素开始，这些是A077998 的双倍元素。

    • 2

  3. 我试图纠正作者的代码。我不知道它是否会按照限制工作。

    import os

def calculate_zigzag_patterns(length, max_value):
    MOD = 10**9 + 7

    if length == 1:
        return max_value

    increasing = [0] * (max_value + 1)
    decreasing = [0] * (max_value + 1)

    for index in range(1, max_value + 1):
        increasing[index] = 1
        decreasing[index] = 1

    for current_length in range(2, length + 1):
        new_increasing = [0] * (max_value + 1)
        new_decreasing = [0] * (max_value + 1)

        total_decreasing = 0
        for last_value in range(1, max_value + 1):
            total_decreasing = (total_decreasing + decreasing[last_value - 1]) % MOD
            new_increasing[last_value] = total_decreasing

        total_increasing = 0
        for last_value in range(max_value, 0, -1):
            if last_value < max_value:
                total_increasing = (total_increasing + increasing[last_value + 1]) % MOD
            new_decreasing[last_value] = total_increasing

        increasing, new_increasing = new_increasing, increasing
        decreasing, new_decreasing = new_decreasing, decreasing

    final_result = sum(increasing[last_value] + decreasing[last_value] for last_value in range(1, max_value + 1)) % MOD
    return final_result

length, max_value = 20, 3
result = calculate_zigzag_patterns(length, max_value)
print(result)

os.system("pause")
    • 1

相关问题