#689877 (Go) No.1239 Multiplication -2

• 問題: No.1239 Multiplication -2
• ユーザー: sgsw
• 提出日時: 2021-08-14 14:54:19
• 言語: Go (1.22.1)
• 結果: 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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	1 ms; 6,820 KB
testcase_02	AC	1 ms; 6,820 KB
testcase_03	AC	2 ms; 6,820 KB
testcase_04	AC	1 ms; 6,816 KB
testcase_05	AC	2 ms; 6,820 KB
testcase_06	AC	1 ms; 6,816 KB
testcase_07	AC	1 ms; 6,820 KB
testcase_08	AC	1 ms; 6,820 KB
testcase_09	AC	0 ms; 6,816 KB
testcase_10	AC	1 ms; 6,820 KB
testcase_11	AC	1 ms; 6,816 KB
testcase_12	AC	1 ms; 6,816 KB
testcase_13	AC	1 ms; 6,816 KB
testcase_14	AC	1 ms; 6,816 KB
testcase_15	AC	55 ms; 18,508 KB
testcase_16	AC	100 ms; 28,288 KB
testcase_17	AC	185 ms; 54,528 KB
testcase_18	AC	182 ms; 54,528 KB
testcase_19	AC	207 ms; 54,016 KB
testcase_20	AC	208 ms; 54,656 KB
testcase_21	AC	178 ms; 53,248 KB
testcase_22	AC	164 ms; 49,536 KB
testcase_23	AC	132 ms; 38,656 KB
testcase_24	AC	124 ms; 36,096 KB
testcase_25	AC	55 ms; 26,368 KB
testcase_26	AC	98 ms; 34,688 KB
testcase_27	AC	51 ms; 15,616 KB
testcase_28	AC	159 ms; 46,848 KB
testcase_29	AC	169 ms; 50,688 KB
testcase_30	AC	69 ms; 22,144 KB
testcase_31	AC	116 ms; 32,384 KB
testcase_32	AC	190 ms; 53,248 KB
testcase_33	AC	131 ms; 37,632 KB
testcase_34	AC	123 ms; 35,072 KB
testcase_35	AC	58 ms; 18,176 KB
testcase_36	AC	52 ms; 16,384 KB

ソースコード

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
}