题目描述

Abathur采集了一系列Primal Zerg 的基因样本，这些基因构成了一个完整的进化链。为了方便，我们用A0,A1…An-1 这n 个正整数描述它们。 一个基因Ax 可以进化为序列中在它之后的基因Ay。这个进化的复杂度，等于Ax | Ax+1…| Ay的值，其中| 是二进制或运算。 Abathur 认为复杂度小于M 的进化的被认为是温和的。它希望计算出温和的进化的对数。

---

思路

将全部数转化为二进制数进行操作，详见代码

---

#include 
#include 
#include 
using namespace std;
#define maxn 200001
#define maxm 41
#define fill(x, y) memset(x, y, sizeof(x))
int a[maxn][maxm];
int f[maxm];
bool check()
{
    for (int k = maxm - 1; k >= 1; k--)
    {
        if (a[0][k] == 1 && f[k] == 0) return 1;
        if (a[0][k] == 0 && f[k] > 0) return 0;
    }
}
int main()
{
    freopen("evolve.in", "r", stdin);
    freopen("evolve.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    int l = 0;
    while (m > 0)
    {
        int x = m % 2;
        a[0][++l] = x;
        m /= 2;
    }
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        int l = 0;
        while (x > 0)
        {
            int y = x % 2;
            a[i][++l] = y;
            x /= 2;
        }
    }
    long long ans = 0;
    for (int i = 1; i <= maxm; i++)
        f[i] = a[1][i];
    int i = 1, j = 1;
    do
    {
        while (check())
        {
            j++;
            for (int k = 1; k < maxm; k++) f[k] += a[j][k];
            if (j > n) break;
        }
        if (j <= n) for (int k = 1; k < maxm; k++) f[k] -= a[j][k];
        j--;
        ans += j - i;
        for (int k = 1; k < maxm; k++) f[k] -= a[i][k];
        i++;
    }
    while (i != n);
    printf("%lld\n", ans);
}