//累積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(a.size()); rep(i, a.size()) sa[i] = a[i]; sort(sa.begin(), 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); //dp[i] = (a[0],…,a[i-1])の部分列は何種類あるか vector last(n + 1); //last[num]:値numに関する最新のdp値. //より正確には、dp[i]を計算する時点で、dp[j] = num (j < i)なる最大のjにおけるdp[j]を持つ. int lastSum = 0; press(a); dp[0] = 1; for (i = 1; i <= n; i++) { lastSum += (dp[i - 1] - last[a[i - 1]] + mod) % mod; lastSum %= mod; last[a[i - 1]] = dp[i - 1]; dp[i] = lastSum + 1; 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; }