//TLE //累積xorを取ると、部分列は何種類?に帰着される。普通にDP考えるとO(N^2 logN)なのだが、どう高速化しようか。 #include #include #include #define rep(i, n) for(i = 0; i < n; i++) using namespace std; void press(vector &a) { int i; vector sa; rep(i, a.size()) sa.push_back(a[i]); sort(sa.begin(), sa.end()); sa.erase(unique(sa.begin(), sa.end()), sa.end()); rep(i, a.size()) a[i] = lower_bound(sa.begin(), sa.end(), a[i]) - sa.begin(); } int count_subarray(vector a, int mod) { int i, j; int n = a.size(); vector dp(n + 1); vector> poses(n + 1); press(a); rep(i, a.size()) poses[a[i]].push_back(i); dp[0] = 1; rep(i, n) { //i番目以降で選ぶ rep(j, n) { //値jを選ぶ int iter = lower_bound(poses[j].begin(), poses[j].end(), i) - poses[j].begin(); if (iter >= poses[j].size()) continue; (dp[poses[j][iter] + 1] += dp[i]) %= mod; } (dp[n] += dp[i]) %= mod; //末尾にする } return dp[n]; } int main() { int n, i; cin >> n; vector a(n); rep(i, n) cin >> a[i]; vector ra(n + 1); ra[0] = 0; rep(i, n) ra[i + 1] = ra[i] ^ a[i]; vector rb(n - 1); rep(i, n - 1) rb[i] = ra[i + 1]; int mod = 1000000007; int ans = count_subarray(rb, mod); cout << ans << endl; return 0; }