AtCoder JSC2019 Qual B Gelöst von Ruby und Python

Einführung

• AtCoder-Probleme * Verwenden Sie Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

AtCoder JSC2019 Qual B - Kleene Inversion Difficulty: 797

Dieses Thema, Summe aus Gleichheitsfolge + inversem Element Ruby Ich habe noch nie von "Stürzen" gehört, aber mal sehen, welche Art von "Stürzen" es zum Beispiel "1 3 2" sein wird.

Ein "1 3 2" ist "1", zwei nebeneinander "1 3 2 1 3 2" ist "4 + 1" und drei sind in einer Reihe "1 3 2 1 3 2 1 3 2" ist "7" Sie können sehen, dass es die Summe von + 4 + 1` und der Gleichheitsfolge ist. Die Formel für die Summe der Gleichheitsfolgen finden Sie unter * here *.

ruby.rb

n, k = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)
b = a + a
c = 0
(a.size - 1).times do |i|
  (i + 1).upto(a.size - 1) do |j|
    c += 1 if a[i] > a[j]
  end
end
d = 0
(b.size - 1).times do |i|
  (i + 1).upto(b.size - 1) do |j|
    d += 1 if b[i] > b[j]
  end
end
d -= c * 2
def modpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p & 1 == 1;
    n = n * n % mod
    p >>= 1
  end
  r
end
def modinv(n, mod)
  modpow(n, mod - 2, mod)
end
MOD = 1_000_000_007
ans = (k - 1) * d % MOD
ans += 2 * c
ans %= MOD
ans *= k
ans %= MOD
ans *= modinv(2, MOD)
ans %= MOD
puts ans

cal.rb

c = 0
(a.size - 1).times do |i|
  (i + 1).upto(a.size - 1) do |j|
    c += 1 if a[i] > a[j]
  end
end
d = 0
(b.size - 1).times do |i|
  (i + 1).upto(b.size - 1) do |j|
    d += 1 if b[i] > b[j]
  end
end
d -= c * 2

Hier werden der erste Term "c" und die Toleranz "d" berechnet.

wa.rb

ans = (k - 1) * d % MOD
ans += 2 * c
ans %= MOD
ans *= k
ans %= MOD
ans *= modinv(2, MOD)
ans %= MOD

Dies ist der offizielle Teil der Summe der Gleichheitsfolge, aber da es eine Division durch "2" gibt, ist es notwendig, das inverse Element zu finden. Python

python.py

n, k = map(int, input().split())
a = list(map(int, input().split()))
b = a + a
c = 0
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        if a[i] > a[j]:
            c += 1
d = 0
for i in range(len(b)):
    for j in range(i + 1, len(b)):
        if b[i] > b[j]:
            d += 1
d -= c * 2
def modpow(n, p, mod):
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
def modinv(n, mod):
    return modpow(n, mod - 2, mod)
MOD = 10 ** 9 + 7
ans = (k - 1) * d % MOD
ans += 2 * c
ans %= MOD
ans *= k
ans %= MOD
ans *= modinv(2, MOD)
ans %= MOD
print(ans)

Selbst mit "PyPy3 (2.4.0)" kann es so verwendet werden, wie es ist.

Zusammenfassung

• JSC2019 Qual B gelöst
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut

Referenzierte Site

• Summe von 4 gleichen Differenzen *