Codeforces Round #757 (Div. 2) C

• C
• • Description
  • Input
  • Output
  • Solution
  • • 1.按位考虑
  • Code

once Divan analyzed a sequence a 1 , a 2 , … , a n a_1,a_2,…,a_n a1​,a2​,…,an​ consisting of n n n non-negative integers as follows. He considered each non-empty subsequence of the sequence a a a, computed the bitwise XOR of its elements and added up all the XORs, obtaining the coziness of the sequence a a a.

A sequence c c c is a subsequence of a sequence d d d if c c c can be obtained from d d d by deletion of several (possibly, zero or all) elements. For example, [1,2,3,4], [2,4], and [2] are subsequences of [1,2,3,4], but [4,3] and [0] are not.

Divan was very proud of his analysis, but now he lost the sequence a a a, and also the coziness value! However, Divan remembers the value of bitwise OR on 푚m contiguous subsegments of the sequence a a a. It turns out that each element of the original sequence is contained in at least one of these m m m segments.

Divan asks you to help find the coziness of the sequence a a a using the information he remembers. If several coziness values are possible, print any.

As the result can be very large, print the value modulo 1 0 9 + 7 10^9+7 109+7.

The first line contains one integer number t ( 1 ≤ t ≤ 1 0 3 ) t (1≤t≤10^3) t(1≤t≤103) — the number of test cases.

The first line of each test case contains two integer numbers n n n and m m m ( 1 ≤ n , m ≤ 2 ⋅ 1 0 5 1≤n,m≤2⋅10^5 1≤n,m≤2⋅105) — the length of the sequence and the number of contiguous segments whose bitwise OR values Divan remembers, respectively.

The following m m m lines describe the segments, one per line.

Each segment is described with three integers l l l, r r r, and x x x ( 1 ≤ l ≤ r ≤ n , 0 ≤ x ≤ 2 30 − 1 1≤l≤r≤n, 0≤x≤2^{30}−1 1≤l≤r≤n,0≤x≤230−1) — the first and last elements of the segment and the bitwise OR of a l , a l + 1 , … , a r a_l,a_{l+1},…,a_r al​,al+1​,…,ar​, respectively.

It is guaranteed that each element of the sequence is contained in at least one of the segments. It is guaranteed that there exists a sequence that satisfies all constraints.

It is guaranteed that the sum of 푛n and the sum of 푚m over all test cases do not exceed 2 ⋅ 1 0 5 2⋅10^5 2⋅105.

For each test case print the coziness any suitable sequence a a a modulo 1 0 9 + 7 10^9+7 109+7.

如果集合 { a 1 , a 2 , . . , a n } {a_1, a_2, ..,a_n} {a1​,a2​,..,an​}的某一位元素 a x a_x ax​的二进制上的某一位为1，则一定是恰好有一半的自己满足异或和为1.

因为一个不包含 a x a_x ax​的子集 S ′ S' S′和 S = S ′ ⋃ { a x } S=S'bigcup {a_x} S=S′⋃{ax​}中，恰好有一个的异或和为1.

而找到所有含有1的位，只需要求出 a 1   o r   a 2   . . .   o r   a n a_1 or a_2 ... or a_n a1​ or a2​ ... or an​的值即可。

然后将这个值乘以集合个数的一半 （ 2 n − 1 2^{n-1} 2n−1），就是答案。

由于给定的信息是 [ l , r ] [l, r] [l,r] 的 o r or or值，所以直接乘即可。（该位为1证明该位有1，为0则没有）

#include 

using namespace std;

typedef long long ll;

#define itn int
#define memmax 0x7fffffff
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair
#define pll pair

const ll MOD = 1000000007;
const int intmax = 2147483647;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 1e5 + 10;

inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

inline void write(ll x)
{ //快写
    char F[200];
    ll tmp = x > 0 ? x : -x;
    if (x < 0)
        putchar('-');
    ll cnt = 0;
    while (tmp > 0)
    {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0)
        putchar(F[--cnt]);
}

ll quickPow(ll n, ll p, ll k = MOD)
{
    ll ans = 1;
    ll base = n;

    while (p)
    {
        //最后一位为1
        if (p & 1)
        {
            ans *= base;
            ans %= k;
        }
        //去掉一位数
        base *= base;
        base %= k;
        p >>= 1;
    }

    return ans;
}

ll t;
ll n, m;
ll x;

void solve()
{
    ll res = 0;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> x >> x;

        res |= x;
    }

    cout << (res * quickPow(2, n - 1)) % MOD << 'n';

    // cout << "ans = ";

}

void run_code_with_time()
{
    clock_t start, finish;
    double totaltime;
    start = clock();

    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        solve();
    }

    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("此程序的运行时间为%.36lf秒！n", totaltime);
}

void run_code()
{
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        solve();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //run_code_with_time();

    run_code();

    return 0;
}