python - 加速完美掉期计算

问题描述

import sys

t=(int(sys.stdin.readline()))

for i in range(0,t):
    n=int(sys.stdin.readline())
    c=0
    s=n*(n+1)/2
    if s%2!=0:
        print(0)
    else:
        c=0
        i=-1
        a=[i for i in range(1,n+1)]
        h=s//2
        m=0
        s1=0
        for i in range(n-1,-1,-1):
            s1+=a[i]
            c+=1
            if s1==h:
                m=1
                break
            if s1>h:
                break
        if m==1:
            s1=((c+1)*(2+((c-1)-1)))//2+((n-c-1)*(2+((n-c-1)-1)))//2
            print(s1)
        else:
            print(c)

我是 python 新手，如何使用 for 循环编写此代码？我不想使用 for 循环，因为我收到 TLE 错误。提前致谢

这是问题：

N. 考虑序列 sequence=(1,2,…,N)。您应该选择此序列的两个元素并交换它们。

如果存在整数 o (1≤o<N) 使得结果序列的前 M 个元素的总和等于其最后 N−o 个元素的总和，则交换是完美的。找出完美互换的数量。

标签： pythonpython-3.xpython-2.7

我对这个问题很感兴趣，到目前为止发现了这个：

一个创建列表并真正交换元素的慢版本是这样的：

from itertools import combinations

def slow(N):

    found = 0
    for i, j in combinations(range(N), 2):

        lst = list(range(1, N + 1))
        lst[i], lst[j] = lst[j], lst[i]

        for m in range(1, N):
            a = m * (m + 1) // 2
            b = (N - m) * (N + m + 1) // 2
            if i < m <= j:
                a = a - i + j
                b = b - j + i

            assert a == sum(lst[:m])
            assert b == sum(lst[m:])

            if sum(lst[:m]) == sum(lst[m:]):
                found += 1

                if i < m <= j:
                    assert 2 * m * (m + 1) + 4 * j == N * (N + 1) + 4 * i
                else:
                    assert 2 * m * (m + 1) == N * (N + 1)

            else:
                if i < m <= j:
                    assert 2 * m * (m + 1) + 4 * j != N * (N + 1) + 4 * i
                else:
                    assert 2 * m * (m + 1) != N * (N + 1)
    return found

如您所见，我发现索引必须满足的标准才能使总和正确：

if i < m <= j:
    assert 2 * m * (m + 1) + 4 * j == N * (N + 1) + 4 * i
else:
    assert 2 * m * (m + 1) == N * (N + 1)

我还找到了计算总和的直接公式，m以及从以下开始的公式m：

a = m * (m + 1) // 2
b = (N - m) * (N + m + 1) // 2
if i < m <= j:
    a = a - i + j
    b = b - j + i

所有这些都可以使用一些基本的数学来计算。

从那开始，你可以做更多的数学运算，看看有两种情况需要考虑：

有一个m原始列表[1, 2, 3, ..., m, m+1, ..., N]的m总和等于列表其余部分的总和（例如N = 20; m = 14）。又是两种情况：
1. 所有不跨越m边界的交换都是有效的（有comb(m, 2) + comb((N - m), 2)）。
2. 当你分裂时，m-1你会发现更多的掉期；这次你必须m-1跨界交换。
在m这种情况下，计算自
```
m = - 1 + sqrt(1 + 2 * N * (N + 1)) / 2
```
在第一种情况下的计算m不是整数（即1 + 2 * N * (N + 1)不是完美的正方形）。然后m要考虑的是上面公式结果的下限（我使用int而不是math.floor）。再次为diff两个拆分之和的两个案例：
1. 区别是均匀的：有更多的交换需要越过m边界。
2. 差异很奇怪：没有额外的交换（交换总是会导致偶数差异）

这是代码：

from math import sqrt, comb

def fast(N):
    found = 0

    arg = (1 + 2 * N * (N + 1))
    sq = round(sqrt(arg))
    if sq ** 2 == arg and sq & 1:
        m = (-1 + sq) // 2
        found += comb(m, 2) + comb((N - m), 2)

        m -= 1
        found += N - m - 1
    else:
        m = int((-1 + sqrt(arg)) // 2)
        diff = ((m + 1 + N) * (N - m) - m * (m + 1)) // 2
        if diff & 1 == 0:
            found += N - m

    return found

python - 加速完美掉期计算 - 避免循环

问题描述

解决方案

推荐阅读