Submission #3401958

Source Code Expand

Copy
def extgcd(a, b)
    if b == 0
        {x: 1, y: 0, gcd: a}
    else
        prev = extgcd(b, a % b)
        {
            x: prev[:y],
            y: prev[:x] - (a / b) * prev[:y],
            gcd: prev[:gcd]
        }
    end
end

def inv_mod(num)
    hash = extgcd(num, MOD)
    hash[:x] % MOD
end


N = gets.to_i
A = [0] + gets.split.map(&:to_i)
MOD = 10**9+7

invsum = [0]
(1..N).each do |i|
    invsum[i] = (invsum[i-1] + inv_mod(i)) % MOD
end

ans = 0
(1..N).each do |i|
    ans = (ans + A[i] * (invsum[i] + invsum[N+1-i] - 1)) % MOD
end

(2..N).each do |i|
    ans = ans * i % MOD
end
puts ans

Submission Info

Submission Time
Task B - Removing Blocks
User betrue12
Language Ruby (2.3.3)
Score 600
Code Size 637 Byte
Status
Exec Time 750 ms
Memory 28360 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt
All 600 / 600 sample-01.txt, sample-02.txt, sample-03.txt, sample-01.txt, sample-02.txt, sample-03.txt, subtask01-01.txt, subtask01-02.txt, subtask01-03.txt, subtask01-04.txt, subtask01-05.txt, subtask01-06.txt, subtask01-07.txt, subtask01-08.txt, subtask01-09.txt, subtask01-10.txt, subtask01-11.txt, subtask01-12.txt, subtask01-13.txt
Case Name Status Exec Time Memory
sample-01.txt 6 ms 1788 KB
sample-02.txt 7 ms 1788 KB
sample-03.txt 7 ms 1788 KB
subtask01-01.txt 7 ms 1788 KB
subtask01-02.txt 544 ms 28356 KB
subtask01-03.txt 418 ms 14792 KB
subtask01-04.txt 546 ms 28360 KB
subtask01-05.txt 170 ms 9528 KB
subtask01-06.txt 294 ms 16780 KB
subtask01-07.txt 167 ms 9788 KB
subtask01-08.txt 727 ms 25996 KB
subtask01-09.txt 732 ms 25996 KB
subtask01-10.txt 723 ms 25996 KB
subtask01-11.txt 735 ms 25996 KB
subtask01-12.txt 750 ms 25996 KB
subtask01-13.txt 727 ms 25996 KB