题目#

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！！！

代码#

1
#include<bits/stdc++.h>
2
#define int long long
3
using namespace std;
4
int T, n;
5
const int N = 1e5 + 10;
6
int a[N];
7

8
unordered_map<int, int> suf, pre;
9
int len[N], L, P, bit[62];
10

11
inline int getlen(int u)
12
{
13
  int ans = 0;
14
  while(u)
15
  {
16
    ans ++;
17
    u >>= 1;
18
  }
19
  return ans;
20
}
21

22
signed main()
23
{
24
  bit[0] = 1;
25
  for(int i = 1;i <= 60;i++)
26
    bit[i] = bit[i - 1] * 2;
27
  ios::sync_with_stdio(0), cin.tie(0);
28
  cin >> T;
29
  while(T --)
30
  {
31
    pre.clear(), suf.clear();
32
    int ans = 0;
33
    cin >> n, cin >> P, L = getlen(P);
34
//    cout << "P LEN" << L << endl;
35
    for(int i = 1;i <= n;i++)
36
      cin >> a[i], len[i] = getlen(a[i]);
37

38
    for(int i = 2;i <= n;i++)
39
      suf[a[i]]++;
40
    for(int j = 2;j < n;j++)
41
    {
42
      int i = j;
43
      pre[a[j - 1]] ++;
44
      suf[a[j]] --;
45
      for(int start = 2; start + len[i] - 1 < L;start++)
46
      {
47
        int t = (L - start - len[i] + 1);
48
        if(((P >> t) & ((1 << len[i]) - 1)) != a[i] || !((P >> (t - 1)) & 1)) continue;
49
        int before = (P >> (L - start + 1)), after = (P & ((1ll << t) - 1));
50
//        if(j == 3)
51
//          cout << before <<" " << after<< endl;
52
        ans += pre[before] * suf[after];
53
      }
54
//      cout << ans << endl;
55
    }
56
    cout << ans << endl;
57
  }
58
}
59

60
/*
61
input:
62
1
63
5 7
64
8 8 1 1 1
65

66
std: 1
67
output: 0
68

69
*/

奇怪的等式

https://blog.histcat.top/posts/strange-equations/

作者

Histcat

发布于

2023-10-03

许可协议

CC BY-NC-SA 4.0

染色

小葱买糖