結果

問題 No.1239 Multiplication -2
ユーザー sgsw
提出日時 2021-08-14 14:54:19
言語 Go
(1.23.4)
結果
AC  
実行時間 208 ms / 2,000 ms
コード長 1,846 bytes
コンパイル時間 11,751 ms
コンパイル使用メモリ 220,612 KB
実行使用メモリ 54,656 KB
最終ジャッジ日時 2024-10-05 09:02:40
合計ジャッジ時間 14,643 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var wg = bufio.NewScanner(os.Stdin)

const (
	inf            = int(1e18)
	initialBufSize = int(1e6)
	maxBufSize     = int(1e6)
	mod            = 998244353
)

var buf []byte = make([]byte, initialBufSize)

func Isin(x int, array []int) bool {
	for _, v := range array {
		if x == v {
			return true
		}
	}
	return false
}

func main() {
	n := nextInt()
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = nextInt()
	}

	// exception n = 1
	if n == 1 {
		if a[0] == -2 {
			fmt.Printf("%d\n", 1)
		} else {
			fmt.Printf("%d\n", 0)
		}
		return
	}

	D := []int{-2, -1, 1, 2}
	dp := make([]map[int]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = map[int]int{}
	}
	//dp[i][val] := i番目までで最後がvalの確率
	if Isin(a[0], D) {
		dp[1][a[0]] = modInv(2, mod)
	}
	for i := 2; i <= n; i++ {
		num := a[i-1]
		if Isin(num, D) {
			if i < n {
				dp[i][num] = modInv(4, mod)
				for prenum, prob := range dp[i-1] {
					if Isin(prenum*num, D) {
						dp[i][prenum*num] += prob * modInv(2, mod)
						dp[i][prenum*num] %= mod
					}
				}
			} else {
				dp[i][num] = modInv(2, mod)
				for prenum, prob := range dp[i-1] {
					if Isin(prenum*num, D) {
						dp[i][prenum*num] += prob
						dp[i][prenum*num] %= mod
					}
				}
			}

		} else {
			for _, d := range D {
				dp[i][d] = 0
			}
		}
	}
	final_ans := 0
	for i := 1; i <= n; i++ {
		final_ans += dp[i][-2]
		final_ans %= mod
	}
	fmt.Printf("%d\n", final_ans)
}

func modInv(a, modulo int) int {
	b := modulo
	u, v := 1, 0
	for b > 0 {
		t := a / b
		a, b = b, a-t*b
		u, v = v, u-t*v
	}
	u %= modulo
	if u < 0 {
		u += modulo
	}
	return u
}

func init() {
	wg.Split(bufio.ScanWords)
	wg.Buffer(buf, maxBufSize)
}

func nextInt() int {
	wg.Scan()
	i, e := strconv.Atoi(wg.Text())
	if e != nil {
		panic(e)
	}
	return i
}
0