//多测试数据 #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <vector> using namespace std; using i64 = long long; typedef pair<int, int> PII; //模数 template<const int T> struct ModInt { const static int mod = T; int x; ModInt(int x = 0) : x(x % mod) {} ModInt(long long x) : x(int(x % mod)) {} int val() { return x; } ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); } ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); } ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); } ModInt operator / (const ModInt &a) const { return *this * a.inv(); } bool operator == (const ModInt &a) const { return x == a.x; }; bool operator != (const ModInt &a) const { return x != a.x; }; void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; } void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; } void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; } void operator /= (const ModInt &a) { *this = *this / a; } friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); } friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); } friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);} friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;} friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;} friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;} ModInt pow(long long n) const { ModInt res(1), mul(x); while(n){ if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } ModInt inv() const { int a = x, b = mod, u = 1, v = 0; while (b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if (u < 0) u += mod; return u; } }; using mint = ModInt<1000000007>; //01字典树 struct Trie{ vector<vector<int>> trie; vector<int> tag; const int mod = 1e9 + 7; int cnt; Trie(){} //n为整数数目,31为int范围 Trie(int n){ cnt = 0; trie.assign(n * 31, vector<int>(2)); tag.assign(n * 31, 0); } void insert(int x, int v){ int idx = 0; for(int i = 30; i >= 0; i--){ if(!trie[idx][(x >> i) & 1]){ trie[idx][(x >> i) & 1] = ++cnt; } idx = trie[idx][(x >> i) & 1]; tag[idx] = (tag[idx] + v) % mod; } } i64 query(int x, int k){ i64 ret = 0; int idx = 0; for(int i = 30; i >= 0; i--){ int e = (x >> i) & 1; if((k >> i) & 1){ ret = (ret + tag[trie[idx][e]]) % mod; idx = trie[idx][1 - e]; } else { idx = trie[idx][e]; } if(!idx) return ret; } return (ret + tag[idx]) % mod; } }; const int MAXN = 2e5 + 5; vector<mint> pow2(MAXN), invpow2(MAXN); inline void init(){ pow2[0] = 1; for(int i = 1; i < MAXN; i++){ pow2[i] = pow2[i - 1] * 2; } invpow2[MAXN - 1] = pow2[MAXN - 1].inv(); for(int i = MAXN - 2; i >= 0; i--){ invpow2[i] = invpow2[i + 1] * 2; } } void solve(){ int n, k; cin >> n >> k; vector<int> a(n + 1); for(int i = 1; i <= n; i++){ cin >> a[i]; } sort(a.begin() + 1, a.end()); Trie trie(n + 1); mint res = n; for(int i = 1; i <= n; i++){ res += pow2[i - 1].val() * trie.query(a[i], k); trie.insert(a[i], invpow2[i].val()); } cout << res << '\n'; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); init(); int T = 1; cin >> T; while(T--) solve(); return 0; }
全部评论
(1) 回帖