結果

問題 No.2188 整数列コイントスゲーム
ユーザー US_cubeUS_cube
提出日時 2023-01-13 22:44:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,224 bytes
コンパイル時間 1,318 ms
コンパイル使用メモリ 110,572 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-06 23:37:33
合計ジャッジ時間 6,965 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 RE -
testcase_06 WA -
testcase_07 RE -
testcase_08 WA -
testcase_09 AC 2 ms
5,376 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 2 ms
5,376 KB
testcase_19 WA -
testcase_20 RE -
testcase_21 AC 2 ms
5,376 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 RE -
testcase_27 AC 2 ms
5,376 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 2 ms
5,376 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <climits>
#include <functional>
#include <cassert>
#include <numeric>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define per(i, n) for(int i = (n) - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
constexpr int mod = 1000000007;
using namespace std;
template<class T, class U>
bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; }
template<class T, class U>
bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; }
struct bint {
  private:
  static constexpr int BASE = 100000000;
  static constexpr int LEN = 8; //log10(BASE)
  bool negative;
  vector<int> a;
  int n = 0;
  bint &normalize(){
    int i = n - 1;
    while(i >= 0 && a[i] == 0) i--;
    a.resize(i + 1);
    n = i + 1;
    if(n == 0) negative = false;
    return *this;
  }
  public:
  bint(int x = 0) : negative(x < 0){
    if(negative) x = -x;
    for(; x > 0; x /= BASE){
      a.push_back(x % BASE);
      n++;
    }
  }
  bint(const string &s) : negative(false){
    int p = 0;
    if(s[p] == '-'){
      p++;
      negative = true;
    }
    else if(s[p] == '+') p++;
    for(int i = s.size() - 1, v = BASE; i >= p; i--, v *= 10){
      int x = s[i] - '0';
      if(x < 0 || 9 < x){
        cerr << "error: parse error:" << s << "\n";
        exit(1);
      } 
      if(v == BASE){
        v = 1;
        a.push_back(x);
        n++;
      }else a.back() += x * v;
    }
    normalize();
  }
  bint &operator=(const bint& x){
    negative = x.negative;
    a = x.a; n = x.n;
    return *this;
  }
  bint &operator=(int x){ return *this = bint(x); }
  bint &operator=(const std::string &s){ return *this = bint(s); }
  const bool operator<(const bint &x) const{
    if(negative != x.negative) return negative < x.negative;
    if(n != x.n) return (n < x.n) ^ negative;
    for(int i = n - 1; i >= 0; i--)
      if(a[i] != x.a[i]) return (a[i] < x.a[i]) ^ negative;
    return false;
  }
  const bool operator>(const bint& x) const{ return x < (*this); }
  const bool operator<=(const bint& x) const{ return !(x < (*this)); }
  const bool operator>=(const bint& x) const{ return !((*this) < x); }
  const bool operator!=(const bint& x) const{ return (*this) < x || x < (*this); }
  const bool operator==(const bint& x) const{ return !((*this) < x || x < (*this)); }
  bint operator-() const{
    bint ret(*this);
    if(n) ret.negative = !ret.negative;
    return ret;
  }
  bint &operator+=(const bint& x){
    if(negative != x.negative) return *this -= -x;
    if(n < x.n){
      a.resize(x.n);
      n = x.n;
    }
    int tmp = 0;
    for(int i = 0; i < n; i++){
      a[i] += (i < x.n ? x.a[i] : 0) + tmp;
      tmp = a[i] / BASE;
      a[i] %= BASE;
    }
    if(tmp){
      a.push_back(1);
      n++;
    }
    return *this;
  }
  bint &operator-=(const bint &x){
    if(negative != x.negative) return *this += -x;
    vector<int> b(x.a);
    int bn = b.size();
    if((*this < x) ^ negative){
      a.swap(b);
      swap(n, bn);
      negative = !negative;
    }
    for(int i = 0, tmp = 0; i < n; i++){
      a[i] += BASE - (i < bn ? b[i] : 0) + tmp;
      tmp = a[i] / BASE - 1;
      a[i] %= BASE;
    }
    return this->normalize();
  }
  bint &operator*=(const bint &x){
    negative ^= x.negative;
    vector<int> c(n * x.n + 1);
    for(int i = 0; i < n; i++){
      ll tmp = 0;
      for(int j = 0; j < x.n; j++){
        ll v = (ll)a[i] * x.a[j] + c[i+j] + tmp;
        tmp = v / BASE;
        c[i+j] = (int)(v % BASE);
      }
      if(tmp) c[i + x.n] += (int)tmp;
    }
    a.swap(c);
    n = a.size();
    return this->normalize();
  }
  bint &operator/=(const bint &x){
    return *this = divmod(*this, x).first;
  }
  bint &operator%=(const bint &x){
    return *this = divmod(*this, x).second;
  }
  const bint operator+(const bint &x) const{
    bint res(*this); return res += x;
  }
  const bint operator-(const bint &x) const{
    bint res(*this); return res -= x;
  }
  const bint operator*(const bint &x) const{
    bint res(*this); return res *= x;
  }
  const bint operator/(const bint &x) const{
    bint res(*this); return res /= x;
  }
  const bint operator%(const bint &x) const{
    bint res(*this); return res %= x;
  }
  pair<bint,bint> divmod(const bint &lhs, const bint &rhs){
    if(!rhs.n){
      cerr << "error: division by zero\n";
      exit(1);
    }
    bint x(abs(rhs)), q, r;
    for(int i = lhs.n - 1; i >= 0; i--){
      r = r * BASE + lhs.a[i];
      int left = 0, right = BASE;
      if(r >= x){
        while(left + 1 < right){
          int mid = (left + right) / 2;
          if(x * bint(mid) > r) right = mid;
          else left = mid;
        }
        r -= x * left;
      }
      q.a.push_back(left);
      q.n++;
    }
    reverse(q.a.begin(), q.a.end());
    bool neg = lhs.negative ^ lhs.negative;
    q.negative = neg; r.negative = neg;
    return { q.normalize(), r.normalize() };
  }
  string to_string() const{
    string s;
    if(negative) s += '-';
    if(!n) s += '0';
    else s += std::to_string(a.back());
    for(int i = n - 2; i >= 0; i--){
      const string t = std::to_string(a[i]);
      s += string(LEN - t.size(), '0');
      s += t;
    }
    return s;
  }
  friend istream &operator>>(istream &is, bint &x){
    string tmp; is >> tmp;
    x = bint(tmp);
    return is;
  }
  friend ostream &operator<<(ostream &os, const bint &x){
    if(x.negative) os << '-';
    if(!x.n) os << 0;
    else os << x.a.back();
    for(int i = x.n - 2; i >= 0; i--){
      os.width(LEN);
      os.fill('0');
      os << x.a[i];
    }
    return os;
  }
  const bint abs(bint x){
    x.negative = false;
    return x;
  }
};
int main(){
  int n,m;
  cin >> n >> m;
  bint ans = 1;
  rep(i, n) ans *= m;
  cout << ans % (m * 2) << "\n";
}
0