Code shoe set - mt3149 · and - the data is not very strong. Violent pruning can deceive AC

---

AND

• AND.

The time limit ：1 second
Space restriction ：64M

---

Title Description

Give a long n Sequence of numbers a, set up $p_{i,j}=a_i$ and $a_{i+1}$ and ……and $a_j$,
seek ${\sum }_{i=1}^n{\sum }_{j=i}^n{p}_{i,j}$
​

---

Input description

The first line is an integer n, Represents the length of a sequence .

The second line n An integer represents a sequence of numbers a.

Data range

Data range

$1\le n\le 100000,0\le a_i\le 10^9$

---

Output description

An integer represents the answer .

---

Example 1

Input

5
5 8 4 5 6

Output

40

Preface

The data of this question is weak , I was thinking of violence first to see how many groups I could pass , The result is pure violence $7$ Group .

Then I want to see how much I can get with pruning , The result is AC 了 .

Then I didn't think about any more methods with lower complexity .

The complexity of the method used in this blog is $O(n^2)$, By the end of 2022 year 6 month 30 Japan 18:38 You can pass this question .

I wonder if there will be new test data in the future .

Topic analysis

First, let's think about how violence . The initial violence complexity is $O(n^3)$：

 from 1 To n enumeration i
     from i To n enumeration j
         from i AND  To j

But it's easy to think of , stay $j$ from $i$ Enumerate to $n$ When , The new result can be used on the basis of the old one $O(1)$ The time complexity of .

Speak in a professional language , Namely ：

In known $p_{i,j}$ Under the premise of , It can be used $O(1)$ The time complexity of $p_{i,j+1}$

The formula is ： $p_{i,j+1}=p_{i,j}\&a[j+1]$

such , The time complexity will be for $O(n^2)$

int a[100010];

int main() {
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    ll ans = 0;
    for (int i = 0; i < n; i++) {
    
        ll k = a[i];
        for (int j = i; j < n; j++) {
    
            k &= a[j];  // p{i,j+1}=p{i,j} & a[j+1]
            ans += k;
        }
    }
    cout << ans << endl;
    return 0;
}

In this way, you can pass $3$ Group data .

prune

It's not hard to find out , If $p_{i,j}=0$, that $p_{i,j+1}$、$p_{i,j+2}$、$\cdots$、$p_{i,n}$ All for $0$

because $0ANDrenWhatCountallby0$ .

Therefore, the above code is in $k=0$ When , We directly $break$ that will do .

I'll just try , Just AC 了 .

But watch out , Whenever there is a group that is all $1$ Of $1e5$ The data of , The above method will not pass

AC Code

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int a[100010];

int main() {
    
    int n;
    cin >> n;
    fi (i, 0, n)  // for (int i = 0; i < n; i++)
        cd(a[i]);  // scanf a[i]
    ll ans = 0;
    for (int i = 0; i < n; i++) {
    
        ll k = a[i];
        for (int j = i; j < n; j++) {
    
            k &= a[j];
            if (!k)
                break;  //  prune 
            ans += k;
        }
    }
    cout << ans << endl;
    return 0;
}

Update the weekly competition solution of elite class in advance every week , Focus , Neverlost

Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125546150