ARC141B

FiraCode · 2023-12-01 20:55:27 · 题解

思路：

首先看到序列长度是 2^{60} 一眼不太可做的样子。

实际上我们仔细分析一下，假如前 i 个数的异或和的最高位为 k。

那么因为要求 a 递增，又因为是异或，所以之前的数中二进制的第 k 位为最高位的至少有一个，所以当前若最高位是 k，那么也应该是 1，但这样一异或就抵消的第 k 为的 1，不满足异或和严格单调递增，所以最高位只要要比之前的 +1，所以方案数不为 0 的 n 也就是 \log m 级别的。

那么就可以考虑 DP，设 dp_i 表示序列长为 i 的方案数。

那么枚举 2^i < m 的 i，对于 j < i，都可以加上这一位（因为若长度为 i 那么最大的数的二进制至少要 i 位）的贡献（就是取第 i 位，那么异或和无论如何都比以前大，所以剩下的位乱取即可，别忘了最多取到 m 的限制就行）。

Code：

#include<bits/stdc++.h>

using namespace std;

const int mod = 998244353;
typedef long long ll;

ll n, m;
ll dp[100] = {0, 1};

int main() {
    scanf("%lld%lld", &n, &m);

    int Log2 = 1;
    for (ll x = 1; x <= m; ++Log2, x *= 2) {
        ll t = (min(m, x * 2 - 1ll) - x + 1) % mod;
        for (int j = Log2; j; --j) dp[j] = (dp[j] + dp[j - 1] * t % mod) % mod;
    }

    if (n > Log2) puts("0");
    else printf("%lld\n", dp[n]); 

    return 0;
}