AtCoder JSC2019 Qual B - Kleene Inversion Difficulty: 797
This theme, sum of arithmetic progression + inverse element
Ruby
I've never heard of inversions, but let's see what kind ofinversionsfor example 1 3 2.
| K | 3 | 2 | 1 | total |
|---|---|---|---|---|
| 132 | 1 | 1 | ||
| 132 132 | 4 | 1 | 5 | |
| 132 132 132 | 7 | 4 | 1 | 12 |
One 1 3 2 is 1, two side by side 1 3 2 1 3 2 is 4 + 1, and three are lined up1 3 2 1 3 2 1 3 2is 7 You can see that it is the sum of + 4 + 1 and arithmetic progression.
For the formula of the sum of arithmetic progressions, refer to * 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
The first term c and the tolerance d are calculated here.
wa.rb
ans = (k - 1) * d % MOD
ans += 2 * c
ans %= MOD
ans *= k
ans %= MOD
ans *= modinv(2, MOD)
ans %= MOD
It is the formula part of the sum of arithmetic progressions, but since there is division by 2, it is necessary to find the inverse element.
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)
Even with PyPy3 (2.4.0), it could be used as it is.
| Ruby | Python | PyPy3 | |
|---|---|---|---|
| Code length(Byte) | 621 | 676 | 676 |
| Execution time(ms) | 948 | 1903 | 322 |
| memory(KB) | 1916 | 3188 | 41692 |
Referenced site
Recommended Posts