題目#
KK 有一個正整數序列 $a_1,a_2,\ldots,a_n$，以及一個正整數 $P$。KK 認為一個整數三元組 $(i,j,k)$ 是好的，當且僅當同時滿足以下條件：
- $1 \le i < j < k \le n$；
- $P=a_i\times 2^{\lfloor\log_2 a_j\rfloor+\lfloor\log_2 a_k\rfloor+2}+a_j\times 2^{\lfloor\log_2 a_k\rfloor+1}+a_k$。
請你幫 KK 求出好的三元組數量。
對於 $100%$ 的數據，$1\le T\le 10^3,1\le n\le 10^5,\sum n\le 10^6,1\le a_i <2^{20},1\le P < 2^{60}$。
題解#
首先考慮暴力求，$O (n^3)$，肯定不行，考慮優化
可以預處理出每個數的 log 下取整的 2 次幂，然後式子可以拆分成有 $k$ 的因式和沒有 $k$ 的因式
，枚舉 $k$ 並順便算出另一個因式的個數。可以用 map 存，時間複雜度 $O (n^2)$，還是行不通
觀察式子，可以發現這個式子其實是把 $a_i$，$a_j$，$a_k$ 三個數在二進制下拼起來，組成 $P$，所以我們枚舉 $j$，並枚舉 $a_j$ 在 $P$ 的哪個位置。枚舉過程中順便維護序列中 $j$ 前後的數字個數，用來統計答案
問題#
1.$a_k$ 不能有前導 0！！！
2. 當1 << t會爆long long的時候，要改成1ll << t！！！
代碼#
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T, n;
const int N = 1e5 + 10;
int a[N];
unordered_map<int, int> suf, pre;
int len[N], L, P, bit[62];
inline int getlen(int u)
{
int ans = 0;
while(u)
{
ans ++;
u >>= 1;
}
return ans;
}
signed main()
{
bit[0] = 1;
for(int i = 1;i <= 60;i++)
bit[i] = bit[i - 1] * 2;
ios::sync_with_stdio(0), cin.tie(0);
cin >> T;
while(T --)
{
pre.clear(), suf.clear();
int ans = 0;
cin >> n, cin >> P, L = getlen(P);
// cout << "P LEN" << L << endl;
for(int i = 1;i <= n;i++)
cin >> a[i], len[i] = getlen(a[i]);
for(int i = 2;i <= n;i++)
suf[a[i]]++;
for(int j = 2;j < n;j++)
{
int i = j;
pre[a[j - 1]] ++;
suf[a[j]] --;
for(int start = 2; start + len[i] - 1 < L;start++)
{
int t = (L - start - len[i] + 1);
if(((P >> t) & ((1 << len[i]) - 1)) != a[i] || !((P >> (t - 1)) & 1)) continue;
int before = (P >> (L - start + 1)), after = (P & ((1ll << t) - 1));
// if(j == 3)
// cout << before <<" " << after<< endl;
ans += pre[before] * suf[after];
}
// cout << ans << endl;
}
cout << ans << endl;
}
}
/*
input:
1
5 7
8 8 1 1 1
std: 1
output: 0
*/