Programmazione Competitiva per sviluppatori .Net (Episodio 2)

Linguaggi
1

Visto il grande successo dell’episodio pilota, prosegue la serie sulla CP all’interno dell’architettura .Net, questa volta utilizzando il linguaggio F♯.

Anche questa volta condividiamo la nostra scelta per l’ambiente di sviluppo: abbiamo deciso di upgradare il nostro sistema a Windows 7 e di usare come IDE Visual Studio™ 2015 Professional Edition.

Poiché per la migliore esperienza è necessario aumentare al massimo il WEI, Windows Experience Index, questa volta l’OS Microsoft runna su una macchina reale (con solo una periferica non riconosciuta) con tanto di Ryzen 5 3600, 32 GB di RAM e AMD Radeon RX 570 8 GB. Questo ci ha permesso di ottenere 7.8/7.9 di WEI, niente male!

Ambiente di sviluppo aggiornato
Ambiente di sviluppo aggiornato1252×704 326 KB

Il problema di oggi è il seguente: F - Convolution, una diretta applicazione di NTT.

Breve lista dei vantaggi offerti da F♯ come linguaggio di programmazione:

  • Essendo F♯ (Fa diesis maggiore) la tonalità in cui viene intonato il “Va’ pensiero”, è impossibile non essere pervasi da un’ondata di patriottismo scrivendo in questo linguaggio.
  • F♯ è una potente combinazione di paradigmi funzionali e OOP: in questo linguaggio è possibile avere sia funzioni di prima classe, sia null reference exceptions.
  • Operatori di comparazione chiari come in VB.Net: = testa per uguaglianza, <> per disugugaglianza. L’assegnazione a variabile (possibile solo se questa è stata precedentemente dichiarata con mutable) si fa invece con <-.
  • Parola chiave rec per dichiarare le funzioni ricorsive, che possono così essere facilmente distinte dalle funzioni non ricorsive.
  • Operatori “pipe” (|> e <|) che, intuitivamente, pipano valori tra funzioni.
  • Presenza di uno unit type meno schizofrenico del void di C++.
  • Supporto per identificatori non ASCII (questo permette di esprimere il proprio patriottismo usando caratteri locali)
  • Gli operatori bitwise sono tutti da 3 caratteri: &&&, |||, ^^^, ~~~, >>> e <<<). Supponiamo sia perché >> era già usato dalla composizione di funzioni.
  • Si accede all’i-esimo elemento di un array con array.[i]. Non è chiaro cosa faccia il punto.
  • Funzione ignore per ignorare il valore di ritorno di una funzione evitando che il linter rompa.
  • Ambiti definiti solo dall’indentazione (come in Python), questo permette di risparmiare moltissimi caratteri.
  • Di default l’esecuzione inizia nell’ambito globale, ma questo comportamento può essere modificato aggiungendo a una funzione il tag [<EntryPoint>]. Questo compromesso accontenta tutti.

E finalmente ecco il codice:

open System

let P = 998244353L

let R = 646L
let IR = 208611436L

[<EntryPoint>]
let main _ =
    let [|N; M|] = Console.ReadLine().Split ' ' |> Seq.map int |> Seq.toArray
    let        A = Console.ReadLine().Split ' ' |> Seq.map int64 |> Seq.toArray
    let        B = Console.ReadLine().Split ' ' |> Seq.map int64 |> Seq.toArray

    let mutable RPow: int64 array = Array.zeroCreate <| 20
    let mutable IRPow: int64 array = Array.zeroCreate <| 20

    RPow.[0] <- R
    IRPow.[0] <- IR
    for j = 1 to 19 do
        RPow.[j] <- (RPow.[j - 1] * RPow.[j - 1]) % P
        IRPow.[j] <- (IRPow.[j - 1] * IRPow.[j - 1]) % P
        

    let mutable UnitàDItalia: int64 array = Array.zeroCreate <| (1<<<20)
    let mutable VivaVerdi: int64 array = Array.zeroCreate <| (1<<<20)

    let rec fft (start:int) (size:int) (step:int) (depth: int) =
        if size <> 1 then 
            fft start (size / 2) (step * 2) (depth + 1)
            fft (start + step) (size / 2) (step * 2) (depth + 1)
            let SpedizioneDeiMille = RPow.[depth]

            for j = 0 to size - 1 do
                VivaVerdi.[start + j * step] <- UnitàDItalia.[start + j * step]

            let mutable ω = 1L

            for j = 0 to size / 2 - 1 do
                UnitàDItalia.[start + j * step]            <- (VivaVerdi.[start + j * step * 2] + ω * VivaVerdi.[start + step + j * step * 2]) % P
                UnitàDItalia.[start + (j + size/2) * step] <- (VivaVerdi.[start + j * step * 2] - (ω * VivaVerdi.[start + step + j * step * 2] % P) + P) % P
                ω <- (ω * SpedizioneDeiMille) % P
            
    let rec ifft (start:int) (size:int) (step:int) (depth: int) =
        if size <> 1 then 
            ifft start (size / 2) (step * 2) (depth + 1)
            ifft (start + step) (size / 2) (step * 2) (depth + 1)
            let SpedizioneDeiMille = IRPow.[depth]

            for j = 0 to size - 1 do
                VivaVerdi.[start + j * step] <- UnitàDItalia.[start + j * step]

            let mutable ω = 1L

            for j = 0 to size / 2 - 1 do
                UnitàDItalia.[start + j * step]            <- (VivaVerdi.[start + j * step * 2] + ω * VivaVerdi.[start + step + j * step * 2]) % P
                UnitàDItalia.[start + (j + size/2) * step] <- (VivaVerdi.[start + j * step * 2] - (ω * VivaVerdi.[start + step + j * step * 2] % P) + P) % P
                ω <- (ω * SpedizioneDeiMille) % P
    

    for i = 0 to A.Length - 1 do
        UnitàDItalia.[i] <- A.[i]

    fft 0 (1<<<20) 1 0

    let mutable VàPensiero = Array.copy UnitàDItalia

    for i = 0 to B.Length - 1 do
        UnitàDItalia.[i] <- B.[i]

    for i = B.Length to UnitàDItalia.Length - 1 do
        UnitàDItalia.[i] <- 0L

    fft 0 (1<<<20) 1 0

    for i = 0 to (1<<<20) - 1 do
        UnitàDItalia.[i] <- UnitàDItalia.[i] * VàPensiero.[i]
    
    ifft 0 (1<<<20) 1 0
    let sb = new Text.StringBuilder()

    for i = 0 to (N + M - 2) do
        sb.AppendFormat("{0} ", (UnitàDItalia.[i] * 998243401L % P)) |> ignore

    Console.Write(sb.ToString())
    0
8 Mi Piace