結果

問題 No.1493 隣接xor
コンテスト
ユーザー 小野寺健
提出日時 2021-05-05 15:21:31
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,132 bytes
コンパイル時間 3,485 ms
コンパイル使用メモリ 78,988 KB
実行使用メモリ 118,216 KB
最終ジャッジ日時 2024-09-13 09:11:05
合計ジャッジ時間 8,014 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Collections;

public class No1498 {

	public static void main(String[] args) {
		final int M = 1000000007;
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		List<Integer> B = new ArrayList<Integer>();
		HashMap<Integer, List<Integer>> D = new HashMap<Integer, List<Integer>>();
		int P = 0;
		for (int i=0; i < N-1; i++) {
			P ^= scan.nextInt();
			B.add(P);
			if (D.containsKey(P)) {
				D.get(P).add(i);
			} else {
				List<Integer> l = new ArrayList<Integer>();
				l.add(i);
				D.put(P, l);
			}
		}
		scan.nextInt();
		scan.close();
		int[] dp = new int[N];
		dp[0] = 1;
		for (int i=0; i < N-1; i++) {
			for (List<Integer> v : D.values()) {
				int j = Collections.binarySearch(v, i);
				if (j < 0) {
					j = -j - 1;
				}
				if (j >= v.size()) {
					continue;
				}
				dp[v.get(j)+1] = (dp[v.get(j)+1] + dp[i]) % M;
			}
		}
		int cnt = 0;
		for (int i=0; i < N; i++) {
			cnt = (cnt + dp[i]) % M;
		}
		System.out.println(cnt);
	}

}
0