結果
| 問題 |
No.8120 Aoki's Present for Takahashi
|
| コンテスト | |
| ユーザー |
 Tamiji153
|
| 提出日時 | 2025-11-05 13:17:19 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 443 ms / 2,000 ms |
| コード長 | 10,567 bytes |
| コンパイル時間 | 2,908 ms |
| コンパイル使用メモリ | 291,028 KB |
| 実行使用メモリ | 14,332 KB |
| 最終ジャッジ日時 | 2025-11-05 13:17:31 |
| 合計ジャッジ時間 | 12,037 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge7 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 20 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:387:32: warning: narrowing conversion of ‘a’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
387 | vector<int> c={a,b-a};
| ^
main.cpp:387:32: warning: narrowing conversion of ‘a’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
main.cpp:387:35: warning: narrowing conversion of ‘(b - a)’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
387 | vector<int> c={a,b-a};
| ~^~
main.cpp:387:35: warning: narrowing conversion of ‘(b - a)’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
ソースコード
//一部 copy from https://atcoder.jp/contests/abc425/submissions/69691103
#include<bits/stdc++.h>
using namespace std;
#ifndef ATCODER_MATH_HPP
#define ATCODER_MATH_HPP 1
#include <algorithm>
#include <cassert>
#include <tuple>
#include <vector>
#ifndef ATCODER_INTERNAL_MATH_HPP
#define ATCODER_INTERNAL_MATH_HPP 1
#include <utility>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned long long y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
// @param n `n < 2^32`
// @param m `1 <= m < 2^32`
// @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
// y_max < m * (n + 1)
// floor(y_max / m) <= n
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_MATH_HPP
namespace atcoder {
long long pow_mod(long long x, long long n, int m) {
assert(0 <= n && 1 <= m);
if (m == 1) return 0;
internal::barrett bt((unsigned int)(m));
unsigned int r = 1, y = (unsigned int)(internal::safe_mod(x, m));
while (n) {
if (n & 1) r = bt.mul(r, y);
y = bt.mul(y, y);
n >>= 1;
}
return r;
}
long long inv_mod(long long x, long long m) {
assert(1 <= m);
auto z = internal::inv_gcd(x, m);
assert(z.first == 1);
return z.second;
}
// (rem, mod)
std::pair<long long, long long> crt(const std::vector<long long>& r,
const std::vector<long long>& m) {
assert(r.size() == m.size());
int n = int(r.size());
// Contracts: 0 <= r0 < m0
long long r0 = 0, m0 = 1;
for (int i = 0; i < n; i++) {
assert(1 <= m[i]);
long long r1 = internal::safe_mod(r[i], m[i]), m1 = m[i];
if (m0 < m1) {
std::swap(r0, r1);
std::swap(m0, m1);
}
if (m0 % m1 == 0) {
if (r0 % m1 != r1) return {0, 0};
continue;
}
// assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)
// (r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));
// r2 % m0 = r0
// r2 % m1 = r1
// -> (r0 + x*m0) % m1 = r1
// -> x*u0*g = r1-r0 (mod u1*g) (u0*g = m0, u1*g = m1)
// -> x = (r1 - r0) / g * inv(u0) (mod u1)
// im = inv(u0) (mod u1) (0 <= im < u1)
long long g, im;
std::tie(g, im) = internal::inv_gcd(m0, m1);
long long u1 = (m1 / g);
// |r1 - r0| < (m0 + m1) <= lcm(m0, m1)
if ((r1 - r0) % g) return {0, 0};
// u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)
long long x = (r1 - r0) / g % u1 * im % u1;
// |r0| + |m0 * x|
// < m0 + m0 * (u1 - 1)
// = m0 + m0 * m1 / g - m0
// = lcm(m0, m1)
r0 += x * m0;
m0 *= u1; // -> lcm(m0, m1)
if (r0 < 0) r0 += m0;
}
return {r0, m0};
}
long long floor_sum(long long n, long long m, long long a, long long b) {
assert(0 <= n && n < (1LL << 32));
assert(1 <= m && m < (1LL << 32));
unsigned long long ans = 0;
if (a < 0) {
unsigned long long a2 = internal::safe_mod(a, m);
ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m);
a = a2;
}
if (b < 0) {
unsigned long long b2 = internal::safe_mod(b, m);
ans -= 1ULL * n * ((b2 - b) / m);
b = b2;
}
return ans + internal::floor_sum_unsigned(n, m, a, b);
}
} // namespace atcoder
#endif // ATCODER_MATH_HPP
typedef long long ll;
// 素因数分解
vector<pair<ll,int>> pfact(ll m) {
vector<pair<ll,int>> ret;
for (ll i=2; i*i<=m; i++) {
if (m % i == 0) {
int cnt = 0;
while (m % i == 0) {
m /= i;
cnt++;
}
ret.emplace_back(i, cnt);
}
}
if (m > 1) ret.emplace_back(m, 1);
return ret;
}
int main() {
ll m=998243353;
vector<pair<ll,int>> pf = pfact(m);
const int mx = 200003;
int k = (int)pf.size();
// 各 M_i = p_i ^ a_i の値を計算する
vector<ll> mods(k);
for (int i=0; i<k; i++) {
mods[i] = 1;
for (int j=0; j<pf[i].second; j++) {
mods[i] *= pf[i].first;
}
}
// k! = p_i^r_i(k) * f_i(k) (mod M_i)
vector<vector<ll>> r(k, vector<ll>(mx + 1));
vector<vector<ll>> f(k, vector<ll>(mx + 1));
vector<vector<ll>> finv(k, vector<ll>(mx + 1));
for (int i=0; i<k; i++) {
f[i][0] = 1;
ll p = pf[i].first;
for (int j=1; j<=mx; j++) {
r[i][j] = r[i][j-1];
ll x = j;
while (x % p == 0) {
x /= p;
r[i][j]++;
}
f[i][j] = f[i][j-1] * x % mods[i];
}
finv[i][mx] = atcoder::inv_mod(f[i][mx], mods[i]);
for (int j=mx-1; j>=0; j--) {
ll x = j+1;
while (x % p == 0) {
x /= p;
}
finv[i][j] = finv[i][j+1] * x % mods[i];
}
}
ll t,t2;
cin>>t>>t2;
for(ll i=1;i<=t2;++i){
ll a,b;
cin>>a>>b;
if(i==t){cout<<"-1\n";continue;}
int n=2;
vector<int> c={a,b-a};
int sums = 0;
for (int i=0; i<n; i++) {
sums += c[i];
}
// ans[i] : M_i での答え
vector<ll> ans(k);
for (int i=0; i<k; i++) {
ans[i] = f[i][sums];
ll rt = r[i][sums]; // p_i^rt
for (int j=0; j<n; j++) {
ans[i] *= finv[i][c[j]];
ans[i] %= mods[i];
rt -= r[i][c[j]];
}
// p_i^a_i を超えている場合 0
if (rt >= pf[i].second) ans[i] = 0;
else {
// そうでないとき愚直に掛ける
for (int j=0; j<rt; j++) {
ans[i] *= pf[i].first;
ans[i] %= mods[i];
}
}
}
// CRT で復元
ll ret = atcoder::crt(ans, mods).first;
cout << ret << '\n';
}
}