#1141855 (C++23) No.186 中華風 (Easy)

提出ソース
結果

問題	No.186 中華風 (Easy)
コンテスト
ユーザー	zoidzium (zz)
提出日時	2025-12-26 00:08:14
言語	C++23 (gcc 13.3.0 + boost 1.89.0)
結果	WA
実行時間	-
コード長	11,559 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	3,403 ms
コンパイル使用メモリ	288,836 KB
実行使用メモリ	7,848 KB
最終ジャッジ日時	2025-12-26 00:08:19
合計ジャッジ時間	4,467 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 21 WA * 2
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>

#include <cassert>
using namespace std;

using ull = unsigned long long;
using ll = long long;
using xy = pair<ll, ll>;
using coord = pair<double, double>;
using bs8 = bitset<8>;
using bs16 = bitset<16>;
using bs32 = bitset<32>;
using bs64 = bitset<64>;

using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;
using vcoord = vector<coord>;
using vvcoord = vector<vcoord>;

#define rep(var, n) for (ll var = 0; var < (ll)(n); var++)
#define cnt(var, n, m) for (ll var = (n); var <= (ll)(m); var++)
#define rcnt(var, n, m) for (ll var = (n); var >= (ll)(m); var--)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define ZINIT 1

#if __has_include("zout.h")
#include "zout.h"
#else
namespace zz_print {
class dbg {
 public:
  static bool unprint;
  static string margin;
  static string separated;
  static string indentS;
  static int hierarchical;
  static int topHier;
  static int precision;
  static bool exponential;

  static void setFloat(const int& prec, const bool& expo) {
    precision = prec;
    exponential = expo;
  };

  template <int hier = 0, int sep = 2, int mgn = 1, typename... Args>
  static void zout(Args&&... args) {};
};
bool dbg::unprint = false;
string dbg::margin = "";
string dbg::separated = "";
string dbg::indentS = "";
int dbg::hierarchical = 0;
int dbg::topHier = 0;
int dbg::precision = 6;
bool dbg::exponential = false;
};  // namespace zz_print
using namespace zz_print;
#endif

xy gcdex(const ll a, const ll b) {
  xy ans;

  if (abs(a) < abs(b)) {
    ans = gcdex(b, a);
    swap(ans.first, ans.second);
    return ans;
  } else if (b == 0) {
    return xy{1, 0};
  }

  //  a > b
  //  da x + db y = d
  //   a x +  b y = 1
  //   (b(a/b) + a%b) x + b y = 1
  //   b ((a/b)x + y) + a%b x = 1
  //   b x' + a%b y' = 1
  //
  //   |x|   | 0   1  | |x'|
  //   | | = |        |*|  |
  //   |y|   | 1 -a/b | |y'|
  //
  ans = gcdex(b, a % b);
  return xy{ans.second, ans.first - (a / b) * ans.second};
};
xy gcdex(const xy ab) { return gcdex(ab.first, ab.second); }
ll gcd(const ll a, const ll b) {
  xy ans = gcdex(a, b);
  return abs(a * ans.first + b * ans.second);
}
ll gcd(const xy ab) { return gcd(ab.first, ab.second); }
ll gcd(const vl& vec) {
  ll n = vec.size();
  if (n == 0) return 1;
  if (n == 1) return vec[0];
  vl subvec;
  rep(i, n / 2) subvec.push_back(gcd(vec[2 * i], vec[2 * i + 1]));
  if (n % 2) subvec.push_back(vec[n - 1]);
  return gcd(subvec);
}
ll lcm(const ll a, const ll b) { return (a * (b / gcd(a, b))); }
ll lcm(const xy ab) { return lcm(ab.first, ab.second); }
ll lcm(const vl& vec) {
  ll n = vec.size();
  if (n == 0) return 1;
  if (n == 1) return vec[0];
  vl subvec;
  rep(i, n / 2) subvec.push_back(lcm(vec[2 * i], vec[2 * i + 1]));
  if (n % 2) subvec.push_back(vec[n - 1]);
  return lcm(subvec);
}

xy ganner(const vxy& vec) {
  ll n = vec.size();
  if (n == 0) return xy{-1, 0};
  if (n == 1) return vec[0];

  vxy subvec;
  rep(i, n / 2) {
    ll r1 = vec[2 * i].first, r2 = vec[2 * i + 1].first;
    ll p1 = vec[2 * i].second, p2 = vec[2 * i + 1].second;

    // p1 * x + p2 * y = d  [%lcm(p1,p2)]
    // d*p1' * x + d*p2' * y = d [%(p1*p2/d)]
    // (d*p1' * x + d*p2' * y) * ((r2 - r1)/d) = d * ((r2 - r1)/d) [%(p1*p2/d)]
    // s * p1 * x + s * p2 * y = r2 - r1 [%(p1*p2/d)]
    // r1 + (s * x) * p1  = r2 - (s * p2) * y [%(p1*p2/d)]
    //
    // d*s = r2 - r1 [%p2]
    // s = (r2 - r1)/d [%(p2/d)]
    // x = d * 1 / p1 [%p2]
    // x = 1 / p1' [%p2]
    // x = inv(p1') [%p2]
    // x = inv(p1) [%(p2/d)]
    xy ans = gcdex(p1, p2);
    ll d = abs(p1 * ans.first + p2 * ans.second);
    ll mod = (p1 / d) * p2;
    if (((r2 - r1) % d) != 0) return xy{-1, 0};
    ll s = (r2 - r1) / d;
    ll k = (s * ans.first) % (p2 / d);
    if (k < 0) k += p2 / d;

    xy pm = xy{k * p1 + r1, mod};
    pm.first %= mod;
    if (pm.first < 0) pm.first += mod;
    subvec.push_back(pm);
  }

  if (n % 2) subvec.push_back(vec[n - 1]);
  return ganner(subvec);
};

namespace zz_mod {
template <ll mod = 998244353>
class pp {
 public:
  ll val;
  void flush() {
    val %= mod;
    if (val < 0) val += mod;
  };
  void weak_flush() {
    if (val < 0) {
      val += mod;
    } else if (val >= mod) {
      val -= mod;
    }
  };
  pp(ll x = 0) {
    val = x % mod;
    weak_flush();
  };
  friend std::ostream& operator<<(std::ostream& os, const pp<mod>& x) {
    return os << '{' << x.val << '|' << mod << '}';
  };

  pp<mod>& operator+=(const pp<mod>& p) {
    val += p.val;
    weak_flush();
    return *this;
  };
  pp<mod>& operator+=(ll x) {
    val += x % mod;
    weak_flush();
    return *this;
  };
  friend pp<mod> operator+(pp<mod> a, const pp<mod>& b) { return a += b; };
  friend pp<mod> operator+(pp<mod> a, ll x) { return a += x; };
  friend pp<mod> operator+(ll x, pp<mod> a) { return a += x; };

  pp<mod>& operator-=(const pp<mod>& p) {
    val -= p.val;
    weak_flush();
    return *this;
  };
  pp<mod>& operator-=(ll x) {
    val -= x % mod;
    weak_flush();
    return *this;
  };
  friend pp<mod> operator-(pp<mod> a, const pp<mod>& b) { return a -= b; };
  friend pp<mod> operator-(pp<mod> a, ll x) { return a -= x; };
  friend pp<mod> operator-(ll x, const pp<mod>& a) { return pp<mod>(x) -= a; };

  pp<mod>& operator*=(const pp<mod>& p) {
    val = (__int128)val * p.val;
    flush();
    return *this;
  };
  pp<mod>& operator*=(ll x) {
    val = (__int128)val * x;
    flush();
    return *this;
  };
  friend pp<mod> operator*(pp<mod> a, const pp<mod>& b) { return a *= b; };
  friend pp<mod> operator*(pp<mod> a, ll x) { return a *= x; };
  friend pp<mod> operator*(ll x, const pp<mod>& a) { return pp<mod>(x) *= a; };

  pp<mod> inv() {
    xy ans = gcdex(mod, val);
    assert((mod * ans.first + val * ans.second) == 1);
    pp<mod> p(ans.second);
    return p;
  };
  pp<mod>& operator/=(const pp<mod>& p) { return *this *= p.inv(); }
  pp<mod>& operator/=(ll x) { return *this *= gcdex(mod, x).second; }

  friend pp<mod> operator/(pp<mod> a, const pp<mod>& b) { return a /= b; };
  friend pp<mod> operator/(pp<mod> a, ll x) { return a /= x; };
  friend pp<mod> operator/(ll x, const pp<mod>& a) {
    a = a.inv();
    return a /= x;
  };

  pp<mod> exp(ll n) {
    if (n < 0) return inv().exp(-n);
    pp<mod> p = *this, ans(1);
    while (n > 1) {
      if (n & 1) ans *= p;
      p *= p;
      n >>= 1;
    }
    if (n > 0) ans *= p;
    return ans;
  };
};

}  // namespace zz_mod
using namespace zz_mod;

/////////////////////////////////////////////////
namespace zz_poly {
ll resize_2exp(vl& a) {
  ll nb = 0;
  while ((1 << nb) < a.size()) nb++;
  a.resize(1 << nb, 0);
  return nb;
}

template <ll mod>
ll getFFTroot(ll len, bool rvs = false) {
  pp<mod> w;
  switch (mod) {
    case 880803841:
      // w = pp<mod>(26).exp(105).val;
      w = pp<mod>(26);
      break;
    case 897581057:
      // w = pp<mod>(3).exp(107).val;
      w = pp<mod>(3);
      break;
    case 998244353:
      // w = pp<mod>(3).exp(119).val;
      w = pp<mod>(3);
      break;
    default:
      assert("convolution nomatch mod" == "");
  }
  if (rvs) return w.inv().exp((mod - 1) / len).val;
  return w.exp((mod - 1) / len).val;
}

template <ll mod>
vl tran(const vl& vec, ll zeta) {
  ll n = vec.size();
  if (n == 1) return vec;
  vl subvec1, subvec2;
  rep(i, n / 2) {
    subvec1.push_back(vec[2 * i]);
    subvec2.push_back(vec[2 * i + 1]);
  }
  vl SUBVEC1 = tran<mod>(subvec1, (zeta * zeta) % mod);
  vl SUBVEC2 = tran<mod>(subvec2, (zeta * zeta) % mod);
  ll w = 1;
  vl ans(n);
  rep(i, n) {
    ans[i] = (SUBVEC1[i % (n / 2)] + SUBVEC2[i % (n / 2)] * w) % mod;
    w = (w * zeta) % mod;
  }
  return ans;
}

template <ll mod>
vl fft(vl& a) {
  resize_2exp(a);
  ll w = getFFTroot<mod>(a.size(), false);
  return tran<mod>(a, w);
}

template <ll mod>
vl fft_reverse(vl& A) {
  resize_2exp(A);
  ll n = A.size();
  ll w = getFFTroot<mod>(n, true);
  vl a = tran<mod>(A, w);
  rep(i, n) a[i] = (pp<mod>(a[i]) / n).val;
  return a;
}

template <ll mod>
vl convolution(vl& a, vl& b) {
  ll n = a.size() + b.size() - 1;
  a.resize(n);
  b.resize(n);
  resize_2exp(a);
  resize_2exp(b);
  n = a.size();
  //  dbg::zout(getFFTroot<mod>(a.size(), false), pp<mod>(getFFTroot<mod>(a.size(), false)).exp(a.size()),
  //          pp<mod>(getFFTroot<mod>(a.size(), false)).exp(a.size() / 2));
  // dbg::zout(getFFTroot<mod>(a.size(), true), pp<mod>(getFFTroot<mod>(a.size(), true)).exp(a.size()),
  //        pp<mod>(getFFTroot<mod>(a.size(), true)).exp(a.size() / 2));
  dbg::zout("convolution a =", a);
  dbg::zout("convolution b =", b);
  vl A = fft<mod>(a);
  vl B = fft<mod>(b);
  dbg::zout("convolution  A=", A);
  dbg::zout("convolution  B=", B);
  vl C(n);
  rep(i, n) C[i] = pp<mod>(A[i] * B[i]).val;
  dbg::zout("convolution  C=", C);
  vl c = fft_reverse<mod>(C);
  dbg::zout("convolution c =", c);
  return c;
}
};  // namespace zz_poly
using namespace zz_poly;
/////////////////////////////////////////////////

xy Gn(const vxy& vec, ll mod = -1) {
  ll n = vec.size();
  if (n == 0) return xy{-1, mod};
  if (mod == -1) {
    mod = lcm([&vec]() {
      vl v;
      each(ite, vec) v.push_back(ite->second);
      return v;
    }());
  }

  //
  // x * p1 + y * p2 = d
  // (x*p1/d) = 1 [%(p2/d)]
  // (y*p2/d) = 1 [%(p1/d)]
  // r3 = r1 * (y*p2/d) + r2 * (x*p1/d)
  // p3 = lcm(p1,p2)
  dbg::zout("Gn: mod=", mod, " vec=", vec);
  ll r1 = 0, p1 = 1;
  rep(i, n) {
    xy prevrp = xy{r1, p1};
    ll r2 = vec[i].first, p2 = vec[i].second;
    dbg::zout("Gn: rp1=", xy{r1, p1}, " rp2=", xy{r2, p2});
    xy ans = gcdex(p1, p2);
    ll d = (ans.first * p1 + ans.second * p2);
    dbg::zout("Gn: ans=", ans, " d=", d);
    if (abs(r1 - r2) % d != 0) return xy{-1, mod};

    ll a = ans.second * (p2 / d), b = ans.first * (p1 / d);
    dbg::zout("Gn: a=", a, " b=", b);
    p1 = p1 * (p2 / d);
    //    a %= p1;
    //    if (a < 0) a += p1;
    //    b %= p1;
    //    if (b < 0) b += p1;

    dbg::zout("Gn: a=", a, " b=", b);
    dbg::zout("Gn: r1*a=", (__int128)r1 * a, " r2*b=", (__int128)r2 * b);
    __int128 r3 = (__int128)r1 * a + (__int128)r2 * b;
    r3 %= p1;
    if (r3 < 0) r3 += p1;
    r1 = r3;
    //    ll r3 = r1 * a;
    //    r3 %= p1;
    //    if (r3 < 0) r3 += p1;
    //    r1 = (r2 * b);
    //    r1 %= p1;
    //    if (r1 < 0) r1 += p1;
    //    r1 += r3;
    //    if (r1 >= p1) r1 -= p1;
    dbg::zout("Gn: rp=", xy{r1, p1});
    dbg::zout("Gm :[*]=", xy{r1 % prevrp.second, prevrp.first});
    rcnt(j, i, 0) dbg::zout("Gm :[", j, "]=", xy{r1 % vec[j].second, vec[j].first});
  }
  return xy{r1, p1};
}

int main() {
  // dbg::unprint = true;

  vl x(3), y(3);
  rep(i, 3) cin >> x[i] >> y[i];

  cout << Gn(vxy{xy{x[0], y[0]}, xy{x[1], y[1]}, xy{x[2], y[2]}}).first << endl;
  //  ll N, M;
  //  cin >> N >> M;
  //  vl a(N), b(M);
  //  rep(i, N) cin >> a[i];
  //  rep(i, M) cin >> b[i];
  //  vl a1 = a, b1 = b;
  //  vl a2 = a, b2 = b;
  //  vl a3 = a, b3 = b;
  //
  //  vl c = convolution<998244353>(a1, b1);
  //  vl c2 = convolution<880803841>(a2, b2);
  //  vl c3 = convolution<897581057>(a3, b3);

  //  rep(i, N + M - 1) { cout << ganner(vxy{xy{c2[i], 880803841}, xy{c3[i], 897581057}}).first % 1000000007 << " "; }
  //  cout << endl;
  return 0;
}
yukicoder

結果

ソースコード
