結果
問題 | No.1493 隣接xor |
ユーザー | 草苺奶昔 |
提出日時 | 2024-02-16 01:29:57 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 1,401 bytes |
コンパイル時間 | 16,903 ms |
コンパイル使用メモリ | 218,640 KB |
実行使用メモリ | 21,944 KB |
最終ジャッジ日時 | 2024-02-16 01:30:19 |
合計ジャッジ時間 | 21,039 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 1 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 163 ms
21,048 KB |
testcase_04 | AC | 162 ms
21,944 KB |
testcase_05 | AC | 162 ms
21,048 KB |
testcase_06 | AC | 164 ms
21,048 KB |
testcase_07 | AC | 163 ms
21,048 KB |
testcase_08 | AC | 163 ms
21,048 KB |
testcase_09 | AC | 163 ms
21,048 KB |
testcase_10 | AC | 162 ms
21,048 KB |
testcase_11 | AC | 164 ms
21,048 KB |
testcase_12 | AC | 157 ms
21,048 KB |
testcase_13 | AC | 109 ms
9,840 KB |
testcase_14 | AC | 68 ms
6,676 KB |
testcase_15 | AC | 2 ms
6,676 KB |
testcase_16 | AC | 2 ms
6,676 KB |
testcase_17 | AC | 1 ms
6,676 KB |
testcase_18 | AC | 1 ms
6,676 KB |
testcase_19 | AC | 1 ms
6,676 KB |
testcase_20 | AC | 82 ms
11,896 KB |
testcase_21 | AC | 92 ms
11,896 KB |
testcase_22 | AC | 63 ms
9,084 KB |
testcase_23 | AC | 83 ms
11,640 KB |
testcase_24 | AC | 149 ms
13,756 KB |
testcase_25 | AC | 69 ms
8,572 KB |
testcase_26 | AC | 102 ms
13,048 KB |
testcase_27 | AC | 42 ms
7,928 KB |
testcase_28 | AC | 138 ms
13,756 KB |
testcase_29 | AC | 104 ms
13,044 KB |
ソースコード
package main import ( "bufio" "fmt" "os" ) func main() { yuki1493() } const MOD int = 1e9 + 7 // https://yukicoder.me/problems/no/1493 // 给定一个长度为n的数组,每次可以将相邻的两个数换成xor // 问可以得到的数组的个数模1e9+7 func yuki1493() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n int fmt.Fscan(in, &n) nums := make([]int, n) for i := 0; i < n; i++ { fmt.Fscan(in, &nums[i]) } for i := 0; i < n-1; i++ { nums[i+1] ^= nums[i] } nums = nums[:n-1] res := CountSubSequence(nums, MOD) res = (res + 1) % MOD // 空集 fmt.Fprintln(out, res) } func CountSubSequence(seq []int, mod int) int { n := len(seq) dp := make([]int, n+1) dp[0] = 1 last := make(map[int]int32) for i, c := range seq { dp[i+1] = 2 * dp[i] % mod if v, ok := last[c]; ok { dp[i+1] -= dp[v] if dp[i+1] < 0 { dp[i+1] += mod } } last[c] = int32(i) } res := (dp[n] - 1) % mod if res < 0 { res += mod } return res } func CountSubSequenceString(seq string, mod int) int { n := len(seq) dp := make([]int, n+1) dp[0] = 1 last := make(map[rune]int32) for i, c := range seq { dp[i+1] = 2 * dp[i] % mod if v, ok := last[c]; ok { dp[i+1] -= dp[v] if dp[i+1] < 0 { dp[i+1] += mod } } last[c] = int32(i) } res := (dp[n] - 1) % mod if res < 0 { res += mod } return res }