2023.6.18 每日一题

原题链接

A: Codeforces Round 606 (Div. 1, based on Technocup 2020 Elimination Round 4) - C

B: Codeforces Round 631 (Div. 1) - Thanks, Denis aramis Shitov! - B

B. Dreamoon Likes Sequences - 1700

题目大意

给定两个整数 \(d\) 和 \(m\)，需要找到满足以下条件的数列 \(a\) 的个数。

• \(1\le a_i < a_{i + 1}\le d\)
• \(a\) 的异或前缀和数列 \(b\) 满足 \(b_i < b_{i + 1}\)

解题思路

异或前缀和要满足严格递增，那么数组元素的二进制位就需要递增。我们可以枚举每个二进制位数，看看它是否可以在我们的数列中，随后处理答案即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N = 5e5 + 10;
const int MOD = 998244353;

void solve() {
    LL d, m;
    LL res = 1;
    cin >> d >> m;
    for (LL i = 0; i <= 32; ++i) {
        if ((1ll << i) <= d) {
            res = res * (min((1ll << (i + 1)) - 1, d) - (1ll << i) + 2) % m;
        }
    }
    cout << (res - 1 < 0 ? m : res) - 1 << endl;
}

signed main() {
    ios;
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}