結果
問題 | No.1800 Random XOR |
ユーザー | 🍮かんプリン |
提出日時 | 2022-01-07 21:52:02 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,069 bytes |
コンパイル時間 | 1,442 ms |
コンパイル使用メモリ | 167,616 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-14 08:41:16 |
合計ジャッジ時間 | 2,037 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 1 ms
6,820 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 1 ms
6,820 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,820 KB |
testcase_08 | AC | 1 ms
6,820 KB |
testcase_09 | AC | 2 ms
6,820 KB |
testcase_10 | AC | 2 ms
6,816 KB |
testcase_11 | AC | 1 ms
6,820 KB |
testcase_12 | AC | 2 ms
6,816 KB |
testcase_13 | AC | 2 ms
6,816 KB |
testcase_14 | AC | 2 ms
6,816 KB |
testcase_15 | AC | 2 ms
6,816 KB |
ソースコード
/** * @FileName a.cpp * @Author kanpurin * @Created 2022.01.07 21:51:58 **/ #include "bits/stdc++.h" using namespace std; typedef long long ll; template< int MOD > struct mint { public: unsigned int x; mint() : x(0) {} mint(long long v) { long long w = (long long)(v % (long long)(MOD)); if (w < 0) w += MOD; x = (unsigned int)(w); } mint(std::string &s) { unsigned int z = 0; for (int i = 0; i < s.size(); i++) { z *= 10; z += s[i] - '0'; z %= MOD; } x = z; } mint operator+() const { return *this; } mint operator-() const { return mint() - *this; } mint& operator+=(const mint &a) { if ((x += a.x) >= MOD) x -= MOD; return *this; } mint& operator-=(const mint &a) { if ((x -= a.x) >= MOD) x += MOD; return *this; } mint& operator*=(const mint &a) { unsigned long long z = x; z *= a.x; x = (unsigned int)(z % MOD); return *this; } mint& operator/=(const mint &a) {return *this = *this * a.inv(); } friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; } friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; } friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; } friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; } friend bool operator==(const mint& lhs, const mint& rhs) { return lhs.x == rhs.x; } friend bool operator!=(const mint& lhs, const mint& rhs) { return lhs.x != rhs.x; } friend std::ostream& operator<<(std::ostream &os, const mint &n) { return os << n.x; } friend std::istream &operator>>(std::istream &is, mint &n) { unsigned int x; is >> x; n = mint(x); return is; } mint inv() const { assert(x); return pow(MOD-2); } mint pow(long long n) const { assert(0 <= n); mint p = *this, r = 1; while (n) { if (n & 1) r *= p; p *= p; n >>= 1; } return r; } mint sqrt() const { if (this->x < 2) return *this; if (this->pow((MOD-1)>>1).x != 1) return mint(0); mint b = 1, one = 1; while (b.pow((MOD-1) >> 1) == 1) b += one; long long m = MOD-1, e = 0; while (m % 2 == 0) m >>= 1, e += 1; mint x = this->pow((m - 1) >> 1); mint y = (*this) * x * x; x *= (*this); mint z = b.pow(m); while (y.x != 1) { int j = 0; mint t = y; while (t != one) j += 1, t *= t; z = z.pow(1LL << (e-j-1)); x *= z; z *= z; y *= z; e = j; } return x; } }; constexpr int MOD = 1e9 + 7; int main() { ll n,m;cin >> n >> m; cout << (mint<MOD>(2).pow(m)-1)/2 << endl; return 0; }