問題#
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$ の 3 つの数を 2 進数で結合して $P$ を構成していることがわかります。したがって、$j$ を列挙し、$P$ のどの位置に $a_j$ があるかを列挙します。列挙の過程で、$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
*/