結果

問題 No.1952 xooooooooooor
コンテスト
ユーザー nawawan
提出日時 2022-05-21 00:23:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 4,040 bytes
コンパイル時間 723 ms
コンパイル使用メモリ 87,372 KB
最終ジャッジ日時 2025-01-29 12:19:37
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <queue>
using namespace std;
template <const int MOD>
struct modint
{
    long long val;
    modint() : val(0) {}
    modint(long long x)
    {
        if (x < 0)
            val = x % MOD + MOD;
        else
            val = x % MOD;
    }
    modint(const modint &t)
    {
        val = t.val;
    }
    modint &operator=(const modint m)
    {
        val = m.val;
        return *this;
    }
    modint operator-()
    {
        return modint(-val);
    }
    modint &operator-=(const modint &m)
    {
        val -= m.val;
        if (val < 0)
            val += MOD;
        return *this;
    }
    modint &operator+=(const modint &m)
    {
        val += m.val;
        if (val >= MOD)
            val -= MOD;
        return *this;
    }
    modint &operator*=(const modint &m)
    {
        val *= m.val;
        val %= MOD;
        return *this;
    }
    modint &operator/=(modint m)
    {
        *this *= m.inv();
        return *this;
    }
    modint inv()
    {
        long long x = 1, y = 0;
        long long a = val, b = MOD;
        while (b != 0)
        {
            long long t = a / b;
            a -= t * b;
            x -= t * y;
            swap(a, b);
            swap(x, y);
        }
        x %= MOD;
        if (x < 0)
            x += MOD;
        return modint(x);
    }
    modint pow(long long k)
    {
        long long res = 1;
        long long v = val;
        if (v == 0)
            return modint(0);
        while (k > 0)
        {
            if (k & 1)
                res = res * v % MOD;
            v = v * v % MOD;
            k >>= 1;
        }
        return modint(res);
    }
    bool operator==(const modint &m)
    {
        return val == m.val;
    }
    modint operator+(const modint &m)
    {
        return modint(*this) += m;
    }
    modint operator-(const modint &m)
    {
        return modint(*this) -= m;
    }
    modint operator*(const modint &m)
    {
        return modint(*this) *= m;
    }
    modint operator/(const modint &m)
    {
        return modint(*this) /= m;
    }
    bool operator!=(const modint &m)
    {
        return modint(*this).val != m.val;
    }
    bool operator!=(const int &m)
    {
        return modint(*this).val != m;
    }
};
const int MOD = 998244353;
using mint = modint<MOD>;
const int MAX = 410000;
mint fac[MAX], finv[MAX], inv[MAX];
// MAX < MOD
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        fac[i] = fac[i - 1] * i;
        inv[i] = mint(MOD) - inv[MOD % i] * (MOD / i);
        finv[i] = finv[i - 1] * inv[i];
    }
}
mint COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * finv[k] * finv[n - k];
}
mint repow(long long x, long long y)
{
    if (y == 0)
        return 1;
    mint res = 1;
    mint x2 = x;
    while (y > 0)
    {
        if (y & 1)
            res = res * x2;
        x2 = x2 * x2;
        y >>= 1;
    }
    return res;
}
int main()
{
    int N, M;
    cin >> N >> M;
    int cnt = 0;
    mint ans = 0;
    if (M < 40)
    {
        long long temp = 0;
        for (int i = 0; i < M; i++)
        {
            temp ^= (1LL << i) * N;
        }
        cout << temp % MOD << endl;
        return 0;
    }
    for (int i = 0; i < 40; i++)
    {
        if ((N >> i) & 1)
            cnt++;
        if (N < (1LL << i))
        {
            if (cnt % 2 == 1)
            {
                ans += (repow(2, M) - repow(2, i));
            }
            cnt = 0;
            for (int j = i - 1; j >= 1; j--)
            {
                if ((N >> j) & 1)
                    cnt++;
                if (cnt % 2 == 1)
                    ans += repow(2, M - 1 + j);
            }
            break;
        }
        else
        {
            if (cnt % 2 == 1)
                ans += mint(1LL << i);
        }
    }
    cout << ans.val << endl;
}
0