#689877 (Go) No.1239 Multiplication -2

• 問題: No.1239 Multiplication -2
• ユーザー: sgsw
• 提出日時: 2021-08-14 14:54:19
• 言語: Go (1.22.1)
• 結果: AC
• 実行時間: 244 ms / 2,000 ms
• コード長: 1,846 bytes
• コンパイル時間: 14,884 ms
• コンパイル使用メモリ: 222,016 KB
• 実行使用メモリ: 54,656 KB
• 最終ジャッジ日時: 2024-04-15 12:49:00
• 合計ジャッジ時間: 19,949 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	3 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	60 ms; 17,536 KB
testcase_16	AC	114 ms; 28,288 KB
testcase_17	AC	193 ms; 54,528 KB
testcase_18	AC	228 ms; 54,528 KB
testcase_19	AC	244 ms; 54,144 KB
testcase_20	AC	241 ms; 54,656 KB
testcase_21	AC	187 ms; 53,376 KB
testcase_22	AC	217 ms; 49,664 KB
testcase_23	AC	153 ms; 38,656 KB
testcase_24	AC	144 ms; 36,096 KB
testcase_25	AC	62 ms; 26,368 KB
testcase_26	AC	116 ms; 34,560 KB
testcase_27	AC	59 ms; 15,616 KB
testcase_28	AC	200 ms; 46,848 KB
testcase_29	AC	221 ms; 50,688 KB
testcase_30	AC	91 ms; 22,272 KB
testcase_31	AC	136 ms; 32,384 KB
testcase_32	AC	216 ms; 53,248 KB
testcase_33	AC	147 ms; 37,632 KB
testcase_34	AC	138 ms; 35,072 KB
testcase_35	AC	67 ms; 18,176 KB
testcase_36	AC	62 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
}