QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#528445 | #9225. Fibonacci Fusion | ucup-team987# | AC ✓ | 2574ms | 67700kb | C++17 | 74.0kb | 2024-08-23 14:15:47 | 2024-08-23 14:15:47 |
Judging History
answer
/**
* date : 2024-08-23 15:15:33
* author : Nyaan
*/
#define NDEBUG
using namespace std;
// intrinstic
#include <immintrin.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tr2/dynamic_bitset>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// utility
namespace Nyaan {
using ll = long long;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
using vi = vector<int>;
using vl = vector<long long>;
using vd = V<double>;
using vs = V<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
template <typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
template <typename T, typename U>
struct P : pair<T, U> {
template <typename... Args>
constexpr P(Args... args) : pair<T, U>(args...) {}
using pair<T, U>::first;
using pair<T, U>::second;
P &operator+=(const P &r) {
first += r.first;
second += r.second;
return *this;
}
P &operator-=(const P &r) {
first -= r.first;
second -= r.second;
return *this;
}
P &operator*=(const P &r) {
first *= r.first;
second *= r.second;
return *this;
}
template <typename S>
P &operator*=(const S &r) {
first *= r, second *= r;
return *this;
}
P operator+(const P &r) const { return P(*this) += r; }
P operator-(const P &r) const { return P(*this) -= r; }
P operator*(const P &r) const { return P(*this) *= r; }
template <typename S>
P operator*(const S &r) const {
return P(*this) *= r;
}
P operator-() const { return P{-first, -second}; }
};
using pl = P<ll, ll>;
using pi = P<int, int>;
using vp = V<pl>;
constexpr int inf = 1001001001;
constexpr long long infLL = 4004004004004004004LL;
template <typename T>
int sz(const T &t) {
return t.size();
}
template <typename T, typename U>
inline bool amin(T &x, U y) {
return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
return (x < y) ? (x = y, true) : false;
}
template <typename T>
inline T Max(const vector<T> &v) {
return *max_element(begin(v), end(v));
}
template <typename T>
inline T Min(const vector<T> &v) {
return *min_element(begin(v), end(v));
}
template <typename T>
inline long long Sum(const vector<T> &v) {
return accumulate(begin(v), end(v), 0LL);
}
template <typename T>
int lb(const vector<T> &v, const T &a) {
return lower_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, const T &a) {
return upper_bound(begin(v), end(v), a) - begin(v);
}
constexpr long long TEN(int n) {
long long ret = 1, x = 10;
for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1);
return ret;
}
template <typename T, typename U>
pair<T, U> mkp(const T &t, const U &u) {
return make_pair(t, u);
}
template <typename T>
vector<T> mkrui(const vector<T> &v, bool rev = false) {
vector<T> ret(v.size() + 1);
if (rev) {
for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1];
} else {
for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];
}
return ret;
};
template <typename T>
vector<T> mkuni(const vector<T> &v) {
vector<T> ret(v);
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
template <typename F>
vector<int> mkord(int N, F f) {
vector<int> ord(N);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), f);
return ord;
}
template <typename T>
vector<int> mkinv(vector<T> &v) {
int max_val = *max_element(begin(v), end(v));
vector<int> inv(max_val + 1, -1);
for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;
return inv;
}
vector<int> mkiota(int n) {
vector<int> ret(n);
iota(begin(ret), end(ret), 0);
return ret;
}
template <typename T>
T mkrev(const T &v) {
T w{v};
reverse(begin(w), end(w));
return w;
}
template <typename T>
bool nxp(T &v) {
return next_permutation(begin(v), end(v));
}
// 返り値の型は入力の T に依存
// i 要素目 : [0, a[i])
template <typename T>
vector<vector<T>> product(const vector<T> &a) {
vector<vector<T>> ret;
vector<T> v;
auto dfs = [&](auto rc, int i) -> void {
if (i == (int)a.size()) {
ret.push_back(v);
return;
}
for (int j = 0; j < a[i]; j++) v.push_back(j), rc(rc, i + 1), v.pop_back();
};
dfs(dfs, 0);
return ret;
}
// F : function(void(T&)), mod を取る操作
// T : 整数型のときはオーバーフローに注意する
template <typename T>
T Power(T a, long long n, const T &I, const function<void(T &)> &f) {
T res = I;
for (; n; f(a = a * a), n >>= 1) {
if (n & 1) f(res = res * a);
}
return res;
}
// T : 整数型のときはオーバーフローに注意する
template <typename T>
T Power(T a, long long n, const T &I = T{1}) {
return Power(a, n, I, function<void(T &)>{[](T &) -> void {}});
}
template <typename T>
T Rev(const T &v) {
T res = v;
reverse(begin(res), end(res));
return res;
}
template <typename T>
vector<T> Transpose(const vector<T> &v) {
using U = typename T::value_type;
if(v.empty()) return {};
int H = v.size(), W = v[0].size();
vector res(W, T(H, U{}));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
res[j][i] = v[i][j];
}
}
return res;
}
template <typename T>
vector<T> Rotate(const vector<T> &v, int clockwise = true) {
using U = typename T::value_type;
int H = v.size(), W = v[0].size();
vector res(W, T(H, U{}));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (clockwise) {
res[W - 1 - j][i] = v[i][j];
} else {
res[j][H - 1 - i] = v[i][j];
}
}
}
return res;
}
} // namespace Nyaan
// bit operation
namespace Nyaan {
__attribute__((target("popcnt"))) inline int popcnt(const u64 &a) {
return __builtin_popcountll(a);
}
inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; }
template <typename T>
inline int gbit(const T &a, int i) {
return (a >> i) & 1;
}
template <typename T>
inline void sbit(T &a, int i, bool b) {
if (gbit(a, i) != b) a ^= T(1) << i;
}
constexpr long long PW(int n) { return 1LL << n; }
constexpr long long MSK(int n) { return (1LL << n) - 1; }
} // namespace Nyaan
// inout
namespace Nyaan {
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
int s = (int)v.size();
for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (auto &x : v) is >> x;
return is;
}
istream &operator>>(istream &is, __int128_t &x) {
string S;
is >> S;
x = 0;
int flag = 0;
for (auto &c : S) {
if (c == '-') {
flag = true;
continue;
}
x *= 10;
x += c - '0';
}
if (flag) x = -x;
return is;
}
istream &operator>>(istream &is, __uint128_t &x) {
string S;
is >> S;
x = 0;
for (auto &c : S) {
x *= 10;
x += c - '0';
}
return is;
}
ostream &operator<<(ostream &os, __int128_t x) {
if (x == 0) return os << 0;
if (x < 0) os << '-', x = -x;
string S;
while (x) S.push_back('0' + x % 10), x /= 10;
reverse(begin(S), end(S));
return os << S;
}
ostream &operator<<(ostream &os, __uint128_t x) {
if (x == 0) return os << 0;
string S;
while (x) S.push_back('0' + x % 10), x /= 10;
reverse(begin(S), end(S));
return os << S;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &...u) {
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u) {
cout << t;
if (sizeof...(u)) cout << sep;
out(u...);
}
struct IoSetupNya {
IoSetupNya() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(7);
}
} iosetupnya;
} // namespace Nyaan
// debug
#ifdef NyaanDebug
#define trc(...) (void(0))
#else
#define trc(...) (void(0))
#endif
#ifdef NyaanLocal
#define trc2(...) (void(0))
#else
#define trc2(...) (void(0))
#endif
// macro
#define each(x, v) for (auto&& x : v)
#define each2(x, y, v) for (auto&& [x, y] : v)
#define all(v) (v).begin(), (v).end()
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define fi first
#define se second
#define ini(...) \
int __VA_ARGS__; \
in(__VA_ARGS__)
#define inl(...) \
long long __VA_ARGS__; \
in(__VA_ARGS__)
#define ins(...) \
string __VA_ARGS__; \
in(__VA_ARGS__)
#define in2(s, t) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i]); \
}
#define in3(s, t, u) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i]); \
}
#define in4(s, t, u, v) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i], v[i]); \
}
#define die(...) \
do { \
Nyaan::out(__VA_ARGS__); \
return; \
} while (0)
namespace Nyaan {
void solve();
}
int main() { Nyaan::solve(); }
//
using namespace std;
struct Timer {
chrono::high_resolution_clock::time_point st;
Timer() { reset(); }
void reset() { st = chrono::high_resolution_clock::now(); }
long long elapsed() {
auto ed = chrono::high_resolution_clock::now();
return chrono::duration_cast<chrono::milliseconds>(ed - st).count();
}
long long operator()() { return elapsed(); }
};
//
using namespace std;
using namespace std;
namespace internal {
template <typename T>
using is_broadly_integral =
typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> ||
is_same_v<T, __uint128_t>,
true_type, false_type>::type;
template <typename T>
using is_broadly_signed =
typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>,
true_type, false_type>::type;
template <typename T>
using is_broadly_unsigned =
typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>,
true_type, false_type>::type;
#define ENABLE_VALUE(x) \
template <typename T> \
constexpr bool x##_v = x<T>::value;
ENABLE_VALUE(is_broadly_integral);
ENABLE_VALUE(is_broadly_signed);
ENABLE_VALUE(is_broadly_unsigned);
#undef ENABLE_VALUE
#define ENABLE_HAS_TYPE(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<typename T::var>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
#define ENABLE_HAS_VAR(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
} // namespace internal
template <uint32_t mod>
struct LazyMontgomeryModInt {
using mint = LazyMontgomeryModInt;
using i32 = int32_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = mod;
for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(mod) % mod;
static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
static_assert(r * mod == 1, "this code has bugs.");
u32 a;
constexpr LazyMontgomeryModInt() : a(0) {}
constexpr LazyMontgomeryModInt(const int64_t &b)
: a(reduce(u64(b % mod + mod) * n2)){};
static constexpr u32 reduce(const u64 &b) {
return (b + u64(u32(b) * u32(-r)) * mod) >> 32;
}
constexpr mint &operator+=(const mint &b) {
if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;
return *this;
}
constexpr mint &operator-=(const mint &b) {
if (i32(a -= b.a) < 0) a += 2 * mod;
return *this;
}
constexpr mint &operator*=(const mint &b) {
a = reduce(u64(a) * b.a);
return *this;
}
constexpr mint &operator/=(const mint &b) {
*this *= b.inverse();
return *this;
}
constexpr mint operator+(const mint &b) const { return mint(*this) += b; }
constexpr mint operator-(const mint &b) const { return mint(*this) -= b; }
constexpr mint operator*(const mint &b) const { return mint(*this) *= b; }
constexpr mint operator/(const mint &b) const { return mint(*this) /= b; }
constexpr bool operator==(const mint &b) const {
return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
}
constexpr bool operator!=(const mint &b) const {
return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
}
constexpr mint operator-() const { return mint() - mint(*this); }
constexpr mint operator+() const { return mint(*this); }
constexpr mint pow(u64 n) const {
mint ret(1), mul(*this);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
constexpr mint inverse() const {
int x = get(), y = mod, u = 1, v = 0, t = 0, tmp = 0;
while (y > 0) {
t = x / y;
x -= t * y, u -= t * v;
tmp = x, x = y, y = tmp;
tmp = u, u = v, v = tmp;
}
return mint{u};
}
friend ostream &operator<<(ostream &os, const mint &b) {
return os << b.get();
}
friend istream &operator>>(istream &is, mint &b) {
int64_t t;
is >> t;
b = LazyMontgomeryModInt<mod>(t);
return (is);
}
constexpr u32 get() const {
u32 ret = reduce(a);
return ret >= mod ? ret - mod : ret;
}
static constexpr u32 get_mod() { return mod; }
};
__attribute__((target("sse4.2"))) inline __m128i my128_mullo_epu32(
const __m128i &a, const __m128i &b) {
return _mm_mullo_epi32(a, b);
}
__attribute__((target("sse4.2"))) inline __m128i my128_mulhi_epu32(
const __m128i &a, const __m128i &b) {
__m128i a13 = _mm_shuffle_epi32(a, 0xF5);
__m128i b13 = _mm_shuffle_epi32(b, 0xF5);
__m128i prod02 = _mm_mul_epu32(a, b);
__m128i prod13 = _mm_mul_epu32(a13, b13);
__m128i prod = _mm_unpackhi_epi64(_mm_unpacklo_epi32(prod02, prod13),
_mm_unpackhi_epi32(prod02, prod13));
return prod;
}
__attribute__((target("sse4.2"))) inline __m128i montgomery_mul_128(
const __m128i &a, const __m128i &b, const __m128i &r, const __m128i &m1) {
return _mm_sub_epi32(
_mm_add_epi32(my128_mulhi_epu32(a, b), m1),
my128_mulhi_epu32(my128_mullo_epu32(my128_mullo_epu32(a, b), r), m1));
}
__attribute__((target("sse4.2"))) inline __m128i montgomery_add_128(
const __m128i &a, const __m128i &b, const __m128i &m2, const __m128i &m0) {
__m128i ret = _mm_sub_epi32(_mm_add_epi32(a, b), m2);
return _mm_add_epi32(_mm_and_si128(_mm_cmpgt_epi32(m0, ret), m2), ret);
}
__attribute__((target("sse4.2"))) inline __m128i montgomery_sub_128(
const __m128i &a, const __m128i &b, const __m128i &m2, const __m128i &m0) {
__m128i ret = _mm_sub_epi32(a, b);
return _mm_add_epi32(_mm_and_si128(_mm_cmpgt_epi32(m0, ret), m2), ret);
}
__attribute__((target("avx2"))) inline __m256i my256_mullo_epu32(
const __m256i &a, const __m256i &b) {
return _mm256_mullo_epi32(a, b);
}
__attribute__((target("avx2"))) inline __m256i my256_mulhi_epu32(
const __m256i &a, const __m256i &b) {
__m256i a13 = _mm256_shuffle_epi32(a, 0xF5);
__m256i b13 = _mm256_shuffle_epi32(b, 0xF5);
__m256i prod02 = _mm256_mul_epu32(a, b);
__m256i prod13 = _mm256_mul_epu32(a13, b13);
__m256i prod = _mm256_unpackhi_epi64(_mm256_unpacklo_epi32(prod02, prod13),
_mm256_unpackhi_epi32(prod02, prod13));
return prod;
}
__attribute__((target("avx2"))) inline __m256i montgomery_mul_256(
const __m256i &a, const __m256i &b, const __m256i &r, const __m256i &m1) {
return _mm256_sub_epi32(
_mm256_add_epi32(my256_mulhi_epu32(a, b), m1),
my256_mulhi_epu32(my256_mullo_epu32(my256_mullo_epu32(a, b), r), m1));
}
__attribute__((target("avx2"))) inline __m256i montgomery_add_256(
const __m256i &a, const __m256i &b, const __m256i &m2, const __m256i &m0) {
__m256i ret = _mm256_sub_epi32(_mm256_add_epi32(a, b), m2);
return _mm256_add_epi32(_mm256_and_si256(_mm256_cmpgt_epi32(m0, ret), m2),
ret);
}
__attribute__((target("avx2"))) inline __m256i montgomery_sub_256(
const __m256i &a, const __m256i &b, const __m256i &m2, const __m256i &m0) {
__m256i ret = _mm256_sub_epi32(a, b);
return _mm256_add_epi32(_mm256_and_si256(_mm256_cmpgt_epi32(m0, ret), m2),
ret);
}
namespace ntt_inner {
using u64 = uint64_t;
constexpr uint32_t get_pr(uint32_t mod) {
if (mod == 2) return 1;
u64 ds[32] = {};
int idx = 0;
u64 m = mod - 1;
for (u64 i = 2; i * i <= m; ++i) {
if (m % i == 0) {
ds[idx++] = i;
while (m % i == 0) m /= i;
}
}
if (m != 1) ds[idx++] = m;
uint32_t pr = 2;
while (1) {
int flg = 1;
for (int i = 0; i < idx; ++i) {
u64 a = pr, b = (mod - 1) / ds[i], r = 1;
while (b) {
if (b & 1) r = r * a % mod;
a = a * a % mod;
b >>= 1;
}
if (r == 1) {
flg = 0;
break;
}
}
if (flg == 1) break;
++pr;
}
return pr;
}
constexpr int SZ_FFT_BUF = 1 << 23;
uint32_t _buf1[SZ_FFT_BUF] __attribute__((aligned(64)));
uint32_t _buf2[SZ_FFT_BUF] __attribute__((aligned(64)));
} // namespace ntt_inner
template <typename mint>
struct NTT {
static constexpr uint32_t mod = mint::get_mod();
static constexpr uint32_t pr = ntt_inner::get_pr(mint::get_mod());
static constexpr int level = __builtin_ctzll(mod - 1);
mint dw[level], dy[level];
mint *buf1, *buf2;
constexpr NTT() {
setwy(level);
union raw_cast {
mint dat;
uint32_t _;
};
buf1 = &(((raw_cast *)(ntt_inner::_buf1))->dat);
buf2 = &(((raw_cast *)(ntt_inner::_buf2))->dat);
}
constexpr void setwy(int k) {
mint w[level], y[level];
w[k - 1] = mint(pr).pow((mod - 1) / (1 << k));
y[k - 1] = w[k - 1].inverse();
for (int i = k - 2; i > 0; --i)
w[i] = w[i + 1] * w[i + 1], y[i] = y[i + 1] * y[i + 1];
dw[0] = dy[0] = w[1] * w[1];
dw[1] = w[1], dy[1] = y[1], dw[2] = w[2], dy[2] = y[2];
for (int i = 3; i < k; ++i) {
dw[i] = dw[i - 1] * y[i - 2] * w[i];
dy[i] = dy[i - 1] * w[i - 2] * y[i];
}
}
__attribute__((target("avx2"))) void ntt(mint *a, int n) {
int k = n ? __builtin_ctz(n) : 0;
if (k == 0) return;
if (k == 1) {
mint a1 = a[1];
a[1] = a[0] - a[1];
a[0] = a[0] + a1;
return;
}
if (k & 1) {
int v = 1 << (k - 1);
if (v < 8) {
for (int j = 0; j < v; ++j) {
mint ajv = a[j + v];
a[j + v] = a[j] - ajv;
a[j] += ajv;
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
int j0 = 0;
int j1 = v;
for (; j0 < v; j0 += 8, j1 += 8) {
__m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
__m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
__m256i naj = montgomery_add_256(T0, T1, m2, m0);
__m256i najv = montgomery_sub_256(T0, T1, m2, m0);
_mm256_storeu_si256((__m256i *)(a + j0), naj);
_mm256_storeu_si256((__m256i *)(a + j1), najv);
}
}
}
int u = 1 << (2 + (k & 1));
int v = 1 << (k - 2 - (k & 1));
mint one = mint(1);
mint imag = dw[1];
while (v) {
if (v == 1) {
mint ww = one, xx = one, wx = one;
for (int jh = 0; jh < u;) {
ww = xx * xx, wx = ww * xx;
mint t0 = a[jh + 0], t1 = a[jh + 1] * xx;
mint t2 = a[jh + 2] * ww, t3 = a[jh + 3] * wx;
mint t0p2 = t0 + t2, t1p3 = t1 + t3;
mint t0m2 = t0 - t2, t1m3 = (t1 - t3) * imag;
a[jh + 0] = t0p2 + t1p3, a[jh + 1] = t0p2 - t1p3;
a[jh + 2] = t0m2 + t1m3, a[jh + 3] = t0m2 - t1m3;
xx *= dw[__builtin_ctz((jh += 4))];
}
} else if (v == 4) {
const __m128i m0 = _mm_set1_epi32(0);
const __m128i m1 = _mm_set1_epi32(mod);
const __m128i m2 = _mm_set1_epi32(mod + mod);
const __m128i r = _mm_set1_epi32(mint::r);
const __m128i Imag = _mm_set1_epi32(imag.a);
mint ww = one, xx = one, wx = one;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = v;
for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i T0P2 = montgomery_add_128(T0, T2, m2, m0);
const __m128i T1P3 = montgomery_add_128(T1, T3, m2, m0);
const __m128i T0M2 = montgomery_sub_128(T0, T2, m2, m0);
const __m128i T1M3 = montgomery_mul_128(
montgomery_sub_128(T1, T3, m2, m0), Imag, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_sub_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j2),
montgomery_add_128(T0M2, T1M3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j3),
montgomery_sub_128(T0M2, T1M3, m2, m0));
}
} else {
ww = xx * xx, wx = ww * xx;
const __m128i WW = _mm_set1_epi32(ww.a);
const __m128i WX = _mm_set1_epi32(wx.a);
const __m128i XX = _mm_set1_epi32(xx.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i MT1 = montgomery_mul_128(T1, XX, r, m1);
const __m128i MT2 = montgomery_mul_128(T2, WW, r, m1);
const __m128i MT3 = montgomery_mul_128(T3, WX, r, m1);
const __m128i T0P2 = montgomery_add_128(T0, MT2, m2, m0);
const __m128i T1P3 = montgomery_add_128(MT1, MT3, m2, m0);
const __m128i T0M2 = montgomery_sub_128(T0, MT2, m2, m0);
const __m128i T1M3 = montgomery_mul_128(
montgomery_sub_128(MT1, MT3, m2, m0), Imag, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_sub_128(T0P2, T1P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j2),
montgomery_add_128(T0M2, T1M3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j3),
montgomery_sub_128(T0M2, T1M3, m2, m0));
}
}
xx *= dw[__builtin_ctz((jh += 4))];
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m1 = _mm256_set1_epi32(mod);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
const __m256i r = _mm256_set1_epi32(mint::r);
const __m256i Imag = _mm256_set1_epi32(imag.a);
mint ww = one, xx = one, wx = one;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = v;
for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i T0P2 = montgomery_add_256(T0, T2, m2, m0);
const __m256i T1P3 = montgomery_add_256(T1, T3, m2, m0);
const __m256i T0M2 = montgomery_sub_256(T0, T2, m2, m0);
const __m256i T1M3 = montgomery_mul_256(
montgomery_sub_256(T1, T3, m2, m0), Imag, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_sub_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j2),
montgomery_add_256(T0M2, T1M3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j3),
montgomery_sub_256(T0M2, T1M3, m2, m0));
}
} else {
ww = xx * xx, wx = ww * xx;
const __m256i WW = _mm256_set1_epi32(ww.a);
const __m256i WX = _mm256_set1_epi32(wx.a);
const __m256i XX = _mm256_set1_epi32(xx.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i MT1 = montgomery_mul_256(T1, XX, r, m1);
const __m256i MT2 = montgomery_mul_256(T2, WW, r, m1);
const __m256i MT3 = montgomery_mul_256(T3, WX, r, m1);
const __m256i T0P2 = montgomery_add_256(T0, MT2, m2, m0);
const __m256i T1P3 = montgomery_add_256(MT1, MT3, m2, m0);
const __m256i T0M2 = montgomery_sub_256(T0, MT2, m2, m0);
const __m256i T1M3 = montgomery_mul_256(
montgomery_sub_256(MT1, MT3, m2, m0), Imag, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_sub_256(T0P2, T1P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j2),
montgomery_add_256(T0M2, T1M3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j3),
montgomery_sub_256(T0M2, T1M3, m2, m0));
}
}
xx *= dw[__builtin_ctz((jh += 4))];
}
}
u <<= 2;
v >>= 2;
}
}
__attribute__((target("avx2"))) void intt(mint *a, int n,
int normalize = true) {
int k = n ? __builtin_ctz(n) : 0;
if (k == 0) return;
if (k == 1) {
mint a1 = a[1];
a[1] = a[0] - a[1];
a[0] = a[0] + a1;
if (normalize) {
a[0] *= mint(2).inverse();
a[1] *= mint(2).inverse();
}
return;
}
int u = 1 << (k - 2);
int v = 1;
mint one = mint(1);
mint imag = dy[1];
while (u) {
if (v == 1) {
mint ww = one, xx = one, yy = one;
u <<= 2;
for (int jh = 0; jh < u;) {
ww = xx * xx, yy = xx * imag;
mint t0 = a[jh + 0], t1 = a[jh + 1];
mint t2 = a[jh + 2], t3 = a[jh + 3];
mint t0p1 = t0 + t1, t2p3 = t2 + t3;
mint t0m1 = (t0 - t1) * xx, t2m3 = (t2 - t3) * yy;
a[jh + 0] = t0p1 + t2p3, a[jh + 2] = (t0p1 - t2p3) * ww;
a[jh + 1] = t0m1 + t2m3, a[jh + 3] = (t0m1 - t2m3) * ww;
xx *= dy[__builtin_ctz(jh += 4)];
}
} else if (v == 4) {
const __m128i m0 = _mm_set1_epi32(0);
const __m128i m1 = _mm_set1_epi32(mod);
const __m128i m2 = _mm_set1_epi32(mod + mod);
const __m128i r = _mm_set1_epi32(mint::r);
const __m128i Imag = _mm_set1_epi32(imag.a);
mint ww = one, xx = one, yy = one;
u <<= 2;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = v + v;
int j3 = j2 + v;
for (; j0 < v; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i T0P1 = montgomery_add_128(T0, T1, m2, m0);
const __m128i T2P3 = montgomery_add_128(T2, T3, m2, m0);
const __m128i T0M1 = montgomery_sub_128(T0, T1, m2, m0);
const __m128i T2M3 = montgomery_mul_128(
montgomery_sub_128(T2, T3, m2, m0), Imag, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P1, T2P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j2),
montgomery_sub_128(T0P1, T2P3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_add_128(T0M1, T2M3, m2, m0));
_mm_storeu_si128((__m128i *)(a + j3),
montgomery_sub_128(T0M1, T2M3, m2, m0));
}
} else {
ww = xx * xx, yy = xx * imag;
const __m128i WW = _mm_set1_epi32(ww.a);
const __m128i XX = _mm_set1_epi32(xx.a);
const __m128i YY = _mm_set1_epi32(yy.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 4, j1 += 4, j2 += 4, j3 += 4) {
const __m128i T0 = _mm_loadu_si128((__m128i *)(a + j0));
const __m128i T1 = _mm_loadu_si128((__m128i *)(a + j1));
const __m128i T2 = _mm_loadu_si128((__m128i *)(a + j2));
const __m128i T3 = _mm_loadu_si128((__m128i *)(a + j3));
const __m128i T0P1 = montgomery_add_128(T0, T1, m2, m0);
const __m128i T2P3 = montgomery_add_128(T2, T3, m2, m0);
const __m128i T0M1 = montgomery_mul_128(
montgomery_sub_128(T0, T1, m2, m0), XX, r, m1);
__m128i T2M3 = montgomery_mul_128(
montgomery_sub_128(T2, T3, m2, m0), YY, r, m1);
_mm_storeu_si128((__m128i *)(a + j0),
montgomery_add_128(T0P1, T2P3, m2, m0));
_mm_storeu_si128(
(__m128i *)(a + j2),
montgomery_mul_128(montgomery_sub_128(T0P1, T2P3, m2, m0), WW,
r, m1));
_mm_storeu_si128((__m128i *)(a + j1),
montgomery_add_128(T0M1, T2M3, m2, m0));
_mm_storeu_si128(
(__m128i *)(a + j3),
montgomery_mul_128(montgomery_sub_128(T0M1, T2M3, m2, m0), WW,
r, m1));
}
}
xx *= dy[__builtin_ctz(jh += 4)];
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m1 = _mm256_set1_epi32(mod);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
const __m256i r = _mm256_set1_epi32(mint::r);
const __m256i Imag = _mm256_set1_epi32(imag.a);
mint ww = one, xx = one, yy = one;
u <<= 2;
for (int jh = 0; jh < u;) {
if (jh == 0) {
int j0 = 0;
int j1 = v;
int j2 = v + v;
int j3 = j2 + v;
for (; j0 < v; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i T0P1 = montgomery_add_256(T0, T1, m2, m0);
const __m256i T2P3 = montgomery_add_256(T2, T3, m2, m0);
const __m256i T0M1 = montgomery_sub_256(T0, T1, m2, m0);
const __m256i T2M3 = montgomery_mul_256(
montgomery_sub_256(T2, T3, m2, m0), Imag, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P1, T2P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j2),
montgomery_sub_256(T0P1, T2P3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_add_256(T0M1, T2M3, m2, m0));
_mm256_storeu_si256((__m256i *)(a + j3),
montgomery_sub_256(T0M1, T2M3, m2, m0));
}
} else {
ww = xx * xx, yy = xx * imag;
const __m256i WW = _mm256_set1_epi32(ww.a);
const __m256i XX = _mm256_set1_epi32(xx.a);
const __m256i YY = _mm256_set1_epi32(yy.a);
int j0 = jh * v;
int j1 = j0 + v;
int j2 = j1 + v;
int j3 = j2 + v;
int je = j1;
for (; j0 < je; j0 += 8, j1 += 8, j2 += 8, j3 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
const __m256i T2 = _mm256_loadu_si256((__m256i *)(a + j2));
const __m256i T3 = _mm256_loadu_si256((__m256i *)(a + j3));
const __m256i T0P1 = montgomery_add_256(T0, T1, m2, m0);
const __m256i T2P3 = montgomery_add_256(T2, T3, m2, m0);
const __m256i T0M1 = montgomery_mul_256(
montgomery_sub_256(T0, T1, m2, m0), XX, r, m1);
const __m256i T2M3 = montgomery_mul_256(
montgomery_sub_256(T2, T3, m2, m0), YY, r, m1);
_mm256_storeu_si256((__m256i *)(a + j0),
montgomery_add_256(T0P1, T2P3, m2, m0));
_mm256_storeu_si256(
(__m256i *)(a + j2),
montgomery_mul_256(montgomery_sub_256(T0P1, T2P3, m2, m0), WW,
r, m1));
_mm256_storeu_si256((__m256i *)(a + j1),
montgomery_add_256(T0M1, T2M3, m2, m0));
_mm256_storeu_si256(
(__m256i *)(a + j3),
montgomery_mul_256(montgomery_sub_256(T0M1, T2M3, m2, m0), WW,
r, m1));
}
}
xx *= dy[__builtin_ctz(jh += 4)];
}
}
u >>= 4;
v <<= 2;
}
if (k & 1) {
v = 1 << (k - 1);
if (v < 8) {
for (int j = 0; j < v; ++j) {
mint ajv = a[j] - a[j + v];
a[j] += a[j + v];
a[j + v] = ajv;
}
} else {
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m2 = _mm256_set1_epi32(mod + mod);
int j0 = 0;
int j1 = v;
for (; j0 < v; j0 += 8, j1 += 8) {
const __m256i T0 = _mm256_loadu_si256((__m256i *)(a + j0));
const __m256i T1 = _mm256_loadu_si256((__m256i *)(a + j1));
__m256i naj = montgomery_add_256(T0, T1, m2, m0);
__m256i najv = montgomery_sub_256(T0, T1, m2, m0);
_mm256_storeu_si256((__m256i *)(a + j0), naj);
_mm256_storeu_si256((__m256i *)(a + j1), najv);
}
}
}
if (normalize) {
mint invn = mint(n).inverse();
for (int i = 0; i < n; i++) a[i] *= invn;
}
}
__attribute__((target("avx2"))) void inplace_multiply(
int l1, int l2, int zero_padding = true) {
int l = l1 + l2 - 1;
int M = 4;
while (M < l) M <<= 1;
if (zero_padding) {
for (int i = l1; i < M; i++) ntt_inner::_buf1[i] = 0;
for (int i = l2; i < M; i++) ntt_inner::_buf2[i] = 0;
}
const __m256i m0 = _mm256_set1_epi32(0);
const __m256i m1 = _mm256_set1_epi32(mod);
const __m256i r = _mm256_set1_epi32(mint::r);
const __m256i N2 = _mm256_set1_epi32(mint::n2);
for (int i = 0; i < l1; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
__m256i b = montgomery_mul_256(a, N2, r, m1);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), b);
}
for (int i = 0; i < l2; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf2 + i));
__m256i b = montgomery_mul_256(a, N2, r, m1);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf2 + i), b);
}
ntt(buf1, M);
ntt(buf2, M);
for (int i = 0; i < M; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
__m256i b = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf2 + i));
__m256i c = montgomery_mul_256(a, b, r, m1);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), c);
}
intt(buf1, M, false);
const __m256i INVM = _mm256_set1_epi32((mint(M).inverse()).a);
for (int i = 0; i < l; i += 8) {
__m256i a = _mm256_loadu_si256((__m256i *)(ntt_inner::_buf1 + i));
__m256i b = montgomery_mul_256(a, INVM, r, m1);
__m256i c = my256_mulhi_epu32(my256_mullo_epu32(b, r), m1);
__m256i d = _mm256_and_si256(_mm256_cmpgt_epi32(c, m0), m1);
__m256i e = _mm256_sub_epi32(d, c);
_mm256_storeu_si256((__m256i *)(ntt_inner::_buf1 + i), e);
}
}
void ntt(vector<mint> &a) {
int M = (int)a.size();
for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
ntt(buf1, M);
for (int i = 0; i < M; i++) a[i].a = buf1[i].a;
}
void intt(vector<mint> &a) {
int M = (int)a.size();
for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
intt(buf1, M, true);
for (int i = 0; i < M; i++) a[i].a = buf1[i].a;
}
vector<mint> multiply(const vector<mint> &a, const vector<mint> &b) {
if (a.size() == 0 && b.size() == 0) return vector<mint>{};
int l = a.size() + b.size() - 1;
if (min<int>(a.size(), b.size()) <= 40) {
vector<mint> s(l);
for (int i = 0; i < (int)a.size(); ++i)
for (int j = 0; j < (int)b.size(); ++j) s[i + j] += a[i] * b[j];
return s;
}
assert(l <= ntt_inner::SZ_FFT_BUF);
int M = 4;
while (M < l) M <<= 1;
for (int i = 0; i < (int)a.size(); ++i) buf1[i].a = a[i].a;
for (int i = (int)a.size(); i < M; ++i) buf1[i].a = 0;
for (int i = 0; i < (int)b.size(); ++i) buf2[i].a = b[i].a;
for (int i = (int)b.size(); i < M; ++i) buf2[i].a = 0;
ntt(buf1, M);
ntt(buf2, M);
for (int i = 0; i < M; ++i)
buf1[i].a = mint::reduce(uint64_t(buf1[i].a) * buf2[i].a);
intt(buf1, M, false);
vector<mint> s(l);
mint invm = mint(M).inverse();
for (int i = 0; i < l; ++i) s[i] = buf1[i] * invm;
return s;
}
void ntt_doubling(vector<mint> &a) {
int M = (int)a.size();
for (int i = 0; i < M; i++) buf1[i].a = a[i].a;
intt(buf1, M);
mint r = 1, zeta = mint(pr).pow((mint::get_mod() - 1) / (M << 1));
for (int i = 0; i < M; i++) buf1[i] *= r, r *= zeta;
ntt(buf1, M);
a.resize(2 * M);
for (int i = 0; i < M; i++) a[M + i].a = buf1[i].a;
}
};
namespace ArbitraryNTT {
using i64 = int64_t;
using u128 = __uint128_t;
constexpr int32_t m0 = 167772161;
constexpr int32_t m1 = 469762049;
constexpr int32_t m2 = 754974721;
using mint0 = LazyMontgomeryModInt<m0>;
using mint1 = LazyMontgomeryModInt<m1>;
using mint2 = LazyMontgomeryModInt<m2>;
constexpr int r01 = mint1(m0).inverse().get();
constexpr int r02 = mint2(m0).inverse().get();
constexpr int r12 = mint2(m1).inverse().get();
constexpr int r02r12 = i64(r02) * r12 % m2;
constexpr i64 w1 = m0;
constexpr i64 w2 = i64(m0) * m1;
template <typename T, typename submint>
vector<submint> mul(const vector<T> &a, const vector<T> &b) {
static NTT<submint> ntt;
vector<submint> s(a.size()), t(b.size());
for (int i = 0; i < (int)a.size(); ++i) s[i] = i64(a[i] % submint::get_mod());
for (int i = 0; i < (int)b.size(); ++i) t[i] = i64(b[i] % submint::get_mod());
return ntt.multiply(s, t);
}
template <typename T>
vector<int> multiply(const vector<T> &s, const vector<T> &t, int mod) {
auto d0 = mul<T, mint0>(s, t);
auto d1 = mul<T, mint1>(s, t);
auto d2 = mul<T, mint2>(s, t);
int n = d0.size();
vector<int> ret(n);
const int W1 = w1 % mod;
const int W2 = w2 % mod;
for (int i = 0; i < n; i++) {
int n1 = d1[i].get(), n2 = d2[i].get(), a = d0[i].get();
int b = i64(n1 + m1 - a) * r01 % m1;
int c = (i64(n2 + m2 - a) * r02r12 + i64(m2 - b) * r12) % m2;
ret[i] = (i64(a) + i64(b) * W1 + i64(c) * W2) % mod;
}
return ret;
}
template <typename mint>
vector<mint> multiply(const vector<mint> &a, const vector<mint> &b) {
if (a.size() == 0 && b.size() == 0) return {};
if (min<int>(a.size(), b.size()) < 128) {
vector<mint> ret(a.size() + b.size() - 1);
for (int i = 0; i < (int)a.size(); ++i)
for (int j = 0; j < (int)b.size(); ++j) ret[i + j] += a[i] * b[j];
return ret;
}
vector<int> s(a.size()), t(b.size());
for (int i = 0; i < (int)a.size(); ++i) s[i] = a[i].get();
for (int i = 0; i < (int)b.size(); ++i) t[i] = b[i].get();
vector<int> u = multiply<int>(s, t, mint::get_mod());
vector<mint> ret(u.size());
for (int i = 0; i < (int)u.size(); ++i) ret[i] = mint(u[i]);
return ret;
}
template <typename T>
vector<u128> multiply_u128(const vector<T> &s, const vector<T> &t) {
if (s.size() == 0 && t.size() == 0) return {};
if (min<int>(s.size(), t.size()) < 128) {
vector<u128> ret(s.size() + t.size() - 1);
for (int i = 0; i < (int)s.size(); ++i)
for (int j = 0; j < (int)t.size(); ++j) ret[i + j] += i64(s[i]) * t[j];
return ret;
}
auto d0 = mul<T, mint0>(s, t);
auto d1 = mul<T, mint1>(s, t);
auto d2 = mul<T, mint2>(s, t);
int n = d0.size();
vector<u128> ret(n);
for (int i = 0; i < n; i++) {
i64 n1 = d1[i].get(), n2 = d2[i].get();
i64 a = d0[i].get();
i64 b = (n1 + m1 - a) * r01 % m1;
i64 c = ((n2 + m2 - a) * r02r12 + (m2 - b) * r12) % m2;
ret[i] = a + b * w1 + u128(c) * w2;
}
return ret;
}
} // namespace ArbitraryNTT
namespace MultiPrecisionIntegerImpl {
struct TENS {
static constexpr int offset = 30;
constexpr TENS() : _tend() {
_tend[offset] = 1;
for (int i = 1; i <= offset; i++) {
_tend[offset + i] = _tend[offset + i - 1] * 10.0;
_tend[offset - i] = 1.0 / _tend[offset + i];
}
}
long double ten_ld(int n) const {
assert(-offset <= n and n <= offset);
return _tend[n + offset];
}
private:
long double _tend[offset * 2 + 1];
};
} // namespace MultiPrecisionIntegerImpl
// 0 は neg=false, dat={} として扱う
struct MultiPrecisionInteger {
using M = MultiPrecisionInteger;
inline constexpr static MultiPrecisionIntegerImpl::TENS tens = {};
static constexpr int D = 1000000000;
static constexpr int logD = 9;
bool neg;
vector<int> dat;
MultiPrecisionInteger() : neg(false), dat() {}
MultiPrecisionInteger(bool n, const vector<int>& d) : neg(n), dat(d) {}
template <typename I,
enable_if_t<internal::is_broadly_integral_v<I>>* = nullptr>
MultiPrecisionInteger(I x) : neg(false) {
if constexpr (internal::is_broadly_signed_v<I>) {
if (x < 0) neg = true, x = -x;
}
while (x) dat.push_back(x % D), x /= D;
}
MultiPrecisionInteger(const string& S) : neg(false) {
assert(!S.empty());
if (S.size() == 1u && S[0] == '0') return;
int l = 0;
if (S[0] == '-') ++l, neg = true;
for (int ie = S.size(); l < ie; ie -= logD) {
int is = max(l, ie - logD);
long long x = 0;
for (int i = is; i < ie; i++) x = x * 10 + S[i] - '0';
dat.push_back(x);
}
while(!dat.empty() and dat.back() == 0) dat.pop_back();
}
friend M operator+(const M& lhs, const M& rhs) {
if (lhs.neg == rhs.neg) return {lhs.neg, _add(lhs.dat, rhs.dat)};
if (_leq(lhs.dat, rhs.dat)) {
// |l| <= |r|
auto c = _sub(rhs.dat, lhs.dat);
bool n = _is_zero(c) ? false : rhs.neg;
return {n, c};
}
auto c = _sub(lhs.dat, rhs.dat);
bool n = _is_zero(c) ? false : lhs.neg;
return {n, c};
}
friend M operator-(const M& lhs, const M& rhs) { return lhs + (-rhs); }
friend M operator*(const M& lhs, const M& rhs) {
auto c = _mul(lhs.dat, rhs.dat);
bool n = _is_zero(c) ? false : (lhs.neg ^ rhs.neg);
return {n, c};
}
friend pair<M, M> divmod(const M& lhs, const M& rhs) {
auto dm = _divmod_newton(lhs.dat, rhs.dat);
bool dn = _is_zero(dm.first) ? false : lhs.neg != rhs.neg;
bool mn = _is_zero(dm.second) ? false : lhs.neg;
return {M{dn, dm.first}, M{mn, dm.second}};
}
friend M operator/(const M& lhs, const M& rhs) {
return divmod(lhs, rhs).first;
}
friend M operator%(const M& lhs, const M& rhs) {
return divmod(lhs, rhs).second;
}
M& operator+=(const M& rhs) { return (*this) = (*this) + rhs; }
M& operator-=(const M& rhs) { return (*this) = (*this) - rhs; }
M& operator*=(const M& rhs) { return (*this) = (*this) * rhs; }
M& operator/=(const M& rhs) { return (*this) = (*this) / rhs; }
M& operator%=(const M& rhs) { return (*this) = (*this) % rhs; }
M operator-() const {
if (is_zero()) return *this;
return {!neg, dat};
}
M operator+() const { return *this; }
friend M abs(const M& m) { return {false, m.dat}; }
bool is_zero() const { return _is_zero(dat); }
friend bool operator==(const M& lhs, const M& rhs) {
return lhs.neg == rhs.neg && lhs.dat == rhs.dat;
}
friend bool operator!=(const M& lhs, const M& rhs) {
return lhs.neg != rhs.neg || lhs.dat != rhs.dat;
}
friend bool operator<(const M& lhs, const M& rhs) {
if (lhs == rhs) return false;
return _neq_lt(lhs, rhs);
}
friend bool operator<=(const M& lhs, const M& rhs) {
if (lhs == rhs) return true;
return _neq_lt(lhs, rhs);
}
friend bool operator>(const M& lhs, const M& rhs) {
if (lhs == rhs) return false;
return _neq_lt(rhs, lhs);
}
friend bool operator>=(const M& lhs, const M& rhs) {
if (lhs == rhs) return true;
return _neq_lt(rhs, lhs);
}
// a * 10^b (1 <= |a| < 10) の形で渡す
// 相対誤差:10^{-16} ~ 10^{-19} 程度 (処理系依存)
pair<long double, int> dfp() const {
if (is_zero()) return {0, 0};
int l = max<int>(0, _size() - 3);
int b = logD * l;
string prefix{};
for (int i = _size() - 1; i >= l; i--) {
prefix += _itos(dat[i], i != _size() - 1);
}
b += prefix.size() - 1;
long double a = 0;
for (auto& c : prefix) a = a * 10.0 + (c - '0');
a *= tens.ten_ld(-((int)prefix.size()) + 1);
a = clamp<long double>(a, 1.0, nextafterl(10.0, 1.0));
if (neg) a = -a;
return {a, b};
}
string to_string() const {
if (is_zero()) return "0";
string res;
if (neg) res.push_back('-');
for (int i = _size() - 1; i >= 0; i--) {
res += _itos(dat[i], i != _size() - 1);
}
return res;
}
long double to_ld() const {
auto [a, b] = dfp();
if (-tens.offset <= b and b <= tens.offset) {
return a * tens.ten_ld(b);
}
return a * powl(10, b);
}
long long to_ll() const {
long long res = _to_ll(dat);
return neg ? -res : res;
}
__int128_t to_i128() const {
__int128_t res = _to_i128(dat);
return neg ? -res : res;
}
friend istream& operator>>(istream& is, M& m) {
string s;
is >> s;
m = M{s};
return is;
}
friend ostream& operator<<(ostream& os, const M& m) {
return os << m.to_string();
}
// 内部の関数をテスト
static void _test_private_function(const M&, const M&);
private:
// size
int _size() const { return dat.size(); }
// a == b
static bool _eq(const vector<int>& a, const vector<int>& b) { return a == b; }
// a < b
static bool _lt(const vector<int>& a, const vector<int>& b) {
if (a.size() != b.size()) return a.size() < b.size();
for (int i = a.size() - 1; i >= 0; i--) {
if (a[i] != b[i]) return a[i] < b[i];
}
return false;
}
// a <= b
static bool _leq(const vector<int>& a, const vector<int>& b) {
return _eq(a, b) || _lt(a, b);
}
// a < b (s.t. a != b)
static bool _neq_lt(const M& lhs, const M& rhs) {
assert(lhs != rhs);
if (lhs.neg != rhs.neg) return lhs.neg;
bool f = _lt(lhs.dat, rhs.dat);
if (f) return !lhs.neg;
return lhs.neg;
}
// a == 0
static bool _is_zero(const vector<int>& a) { return a.empty(); }
// a == 1
static bool _is_one(const vector<int>& a) {
return (int)a.size() == 1 && a[0] == 1;
}
// 末尾 0 を削除
static void _shrink(vector<int>& a) {
while (a.size() && a.back() == 0) a.pop_back();
}
// 末尾 0 を削除
void _shrink() {
while (_size() && dat.back() == 0) dat.pop_back();
}
// a + b
static vector<int> _add(const vector<int>& a, const vector<int>& b) {
vector<int> c(max(a.size(), b.size()) + 1);
for (int i = 0; i < (int)a.size(); i++) c[i] += a[i];
for (int i = 0; i < (int)b.size(); i++) c[i] += b[i];
for (int i = 0; i < (int)c.size() - 1; i++) {
if (c[i] >= D) c[i] -= D, c[i + 1]++;
}
_shrink(c);
return c;
}
// a - b
static vector<int> _sub(const vector<int>& a, const vector<int>& b) {
assert(_leq(b, a));
vector<int> c{a};
int borrow = 0;
for (int i = 0; i < (int)a.size(); i++) {
if (i < (int)b.size()) borrow += b[i];
c[i] -= borrow;
borrow = 0;
if (c[i] < 0) c[i] += D, borrow = 1;
}
assert(borrow == 0);
_shrink(c);
return c;
}
// a * b (fft)
static vector<int> _mul_fft(const vector<int>& a, const vector<int>& b) {
if (a.empty() || b.empty()) return {};
auto m = ArbitraryNTT::multiply_u128(a, b);
vector<int> c;
c.reserve(m.size() + 3);
__uint128_t x = 0;
for (int i = 0;; i++) {
if (i >= (int)m.size() && x == 0) break;
if (i < (int)m.size()) x += m[i];
c.push_back(x % D);
x /= D;
}
_shrink(c);
return c;
}
// a * b (naive)
static vector<int> _mul_naive(const vector<int>& a, const vector<int>& b) {
if (a.empty() || b.empty()) return {};
vector<long long> prod(a.size() + b.size() - 1 + 1);
for (int i = 0; i < (int)a.size(); i++) {
for (int j = 0; j < (int)b.size(); j++) {
long long p = 1LL * a[i] * b[j];
prod[i + j] += p;
if (prod[i + j] >= (4LL * D * D)) {
prod[i + j] -= 4LL * D * D;
prod[i + j + 1] += 4LL * D;
}
}
}
vector<int> c(prod.size() + 1);
long long x = 0;
int i = 0;
for (; i < (int)prod.size(); i++) x += prod[i], c[i] = x % D, x /= D;
while (x) c[i] = x % D, x /= D, i++;
_shrink(c);
return c;
}
// a * b
static vector<int> _mul(const vector<int>& a, const vector<int>& b) {
if (_is_zero(a) || _is_zero(b)) return {};
if (_is_one(a)) return b;
if (_is_one(b)) return a;
if (min<int>(a.size(), b.size()) <= 128) {
return a.size() < b.size() ? _mul_naive(b, a) : _mul_naive(a, b);
}
return _mul_fft(a, b);
}
// 0 <= A < 1e18, 1 <= B < 1e9
static pair<vector<int>, vector<int>> _divmod_li(const vector<int>& a,
const vector<int>& b) {
assert(0 <= (int)a.size() && (int)a.size() <= 2);
assert((int)b.size() == 1);
long long va = _to_ll(a);
int vb = b[0];
return {_integer_to_vec(va / vb), _integer_to_vec(va % vb)};
}
// 0 <= A < 1e18, 1 <= B < 1e18
static pair<vector<int>, vector<int>> _divmod_ll(const vector<int>& a,
const vector<int>& b) {
assert(0 <= (int)a.size() && (int)a.size() <= 2);
assert(1 <= (int)b.size() && (int)b.size() <= 2);
long long va = _to_ll(a), vb = _to_ll(b);
return {_integer_to_vec(va / vb), _integer_to_vec(va % vb)};
}
// 1 <= B < 1e9
static pair<vector<int>, vector<int>> _divmod_1e9(const vector<int>& a,
const vector<int>& b) {
assert((int)b.size() == 1);
if (b[0] == 1) return {a, {}};
if ((int)a.size() <= 2) return _divmod_li(a, b);
vector<int> quo(a.size());
long long d = 0;
int b0 = b[0];
for (int i = a.size() - 1; i >= 0; i--) {
d = d * D + a[i];
assert(d < 1LL * D * b0);
int q = d / b0, r = d % b0;
quo[i] = q, d = r;
}
_shrink(quo);
return {quo, d ? vector<int>{int(d)} : vector<int>{}};
}
// 0 <= A, 1 <= B
static pair<vector<int>, vector<int>> _divmod_naive(const vector<int>& a,
const vector<int>& b) {
if (_is_zero(b)) {
cerr << "Divide by Zero Exception" << endl;
exit(1);
}
assert(1 <= (int)b.size());
if ((int)b.size() == 1) return _divmod_1e9(a, b);
if (max<int>(a.size(), b.size()) <= 2) return _divmod_ll(a, b);
if (_lt(a, b)) return {{}, a};
// B >= 1e9, A >= B
int norm = D / (b.back() + 1);
vector<int> x = _mul(a, {norm});
vector<int> y = _mul(b, {norm});
int yb = y.back();
vector<int> quo(x.size() - y.size() + 1);
vector<int> rem(x.end() - y.size(), x.end());
for (int i = quo.size() - 1; i >= 0; i--) {
if (rem.size() < y.size()) {
// do nothing
} else if (rem.size() == y.size()) {
if (_leq(y, rem)) {
quo[i] = 1, rem = _sub(rem, y);
}
} else {
assert(y.size() + 1 == rem.size());
long long rb = 1LL * rem[rem.size() - 1] * D + rem[rem.size() - 2];
int q = rb / yb;
vector<int> yq = _mul(y, {q});
// 真の商は q-2 以上 q+1 以下だが自信が無いので念のため while を回す
while (_lt(rem, yq)) q--, yq = _sub(yq, y);
rem = _sub(rem, yq);
while (_leq(y, rem)) q++, rem = _sub(rem, y);
quo[i] = q;
}
if (i) rem.insert(begin(rem), x[i - 1]);
}
_shrink(quo), _shrink(rem);
auto [q2, r2] = _divmod_1e9(rem, {norm});
assert(_is_zero(r2));
return {quo, q2};
}
// 0 <= A, 1 <= B
static pair<vector<int>, vector<int>> _divmod_dc(const vector<int>& a,
const vector<int>& b);
// 1 / a を 絶対誤差 B^{-deg} で求める
static vector<int> _calc_inv(const vector<int>& a, int deg) {
assert(!a.empty() && D / 2 <= a.back() and a.back() < D);
int k = deg, c = a.size();
while (k > 64) k = (k + 1) / 2;
vector<int> z(c + k + 1);
z.back() = 1;
z = _divmod_naive(z, a).first;
while (k < deg) {
vector<int> s = _mul(z, z);
s.insert(begin(s), 0);
int d = min(c, 2 * k + 1);
vector<int> t{end(a) - d, end(a)}, u = _mul(s, t);
u.erase(begin(u), begin(u) + d);
vector<int> w(k + 1), w2 = _add(z, z);
copy(begin(w2), end(w2), back_inserter(w));
z = _sub(w, u);
z.erase(begin(z));
k *= 2;
}
z.erase(begin(z), begin(z) + k - deg);
return z;
}
static pair<vector<int>, vector<int>> _divmod_newton(const vector<int>& a,
const vector<int>& b) {
if (_is_zero(b)) {
cerr << "Divide by Zero Exception" << endl;
exit(1);
}
if ((int)b.size() <= 64) return _divmod_naive(a, b);
if ((int)a.size() - (int)b.size() <= 64) return _divmod_naive(a, b);
int norm = D / (b.back() + 1);
vector<int> x = _mul(a, {norm});
vector<int> y = _mul(b, {norm});
int s = x.size(), t = y.size();
int deg = s - t + 2;
vector<int> z = _calc_inv(y, deg);
vector<int> q = _mul(x, z);
q.erase(begin(q), begin(q) + t + deg);
vector<int> yq = _mul(y, {q});
while (_lt(x, yq)) q = _sub(q, {1}), yq = _sub(yq, y);
vector<int> r = _sub(x, yq);
while (_leq(y, r)) q = _add(q, {1}), r = _sub(r, y);
_shrink(q), _shrink(r);
auto [q2, r2] = _divmod_1e9(r, {norm});
assert(_is_zero(r2));
return {q, q2};
}
// int -> string
// 先頭かどうかに応じて zero padding するかを決める
static string _itos(int x, bool zero_padding) {
assert(0 <= x && x < D);
string res;
for (int i = 0; i < logD; i++) {
res.push_back('0' + x % 10), x /= 10;
}
if (!zero_padding) {
while (res.size() && res.back() == '0') res.pop_back();
assert(!res.empty());
}
reverse(begin(res), end(res));
return res;
}
// convert ll to vec
template <typename I,
enable_if_t<internal::is_broadly_integral_v<I>>* = nullptr>
static vector<int> _integer_to_vec(I x) {
if constexpr (internal::is_broadly_signed_v<I>) {
assert(x >= 0);
}
vector<int> res;
while (x) res.push_back(x % D), x /= D;
return res;
}
static long long _to_ll(const vector<int>& a) {
long long res = 0;
for (int i = (int)a.size() - 1; i >= 0; i--) res = res * D + a[i];
return res;
}
static __int128_t _to_i128(const vector<int>& a) {
__int128_t res = 0;
for (int i = (int)a.size() - 1; i >= 0; i--) res = res * D + a[i];
return res;
}
static void _dump(const vector<int>& a, string s = "") {
if (!s.empty()) cerr << s << " : ";
cerr << "{ ";
for (int i = 0; i < (int)a.size(); i++) cerr << a[i] << ", ";
cerr << "}" << endl;
}
};
using bigint = MultiPrecisionInteger;
/**
* @brief 多倍長整数
*/
using namespace std;
// {rank, det(非正方行列の場合は未定義)} を返す
// 型が double や Rational でも動くはず?(未検証)
//
// pivot 候補 : [0, pivot_end)
template <typename T>
std::pair<int, T> GaussElimination(vector<vector<T>> &a, int pivot_end = -1,
bool diagonalize = false) {
if (a.empty()) return {0, 1};
int H = a.size(), W = a[0].size(), rank = 0;
if (pivot_end == -1) pivot_end = W;
T det = 1;
for (int j = 0; j < pivot_end; j++) {
int idx = -1;
for (int i = rank; i < H; i++) {
if (a[i][j] != T(0)) {
idx = i;
break;
}
}
if (idx == -1) {
det = 0;
continue;
}
if (rank != idx) det = -det, swap(a[rank], a[idx]);
det *= a[rank][j];
if (diagonalize && a[rank][j] != T(1)) {
T coeff = T(1) / a[rank][j];
for (int k = j; k < W; k++) a[rank][k] *= coeff;
}
int is = diagonalize ? 0 : rank + 1;
for (int i = is; i < H; i++) {
if (i == rank) continue;
if (a[i][j] != T(0)) {
T coeff = a[i][j] / a[rank][j];
for (int k = j; k < W; k++) a[i][k] -= a[rank][k] * coeff;
}
}
rank++;
}
return make_pair(rank, det);
}
template <typename mint>
vector<vector<mint>> inverse_matrix(const vector<vector<mint>>& a) {
int N = a.size();
assert(N > 0);
assert(N == (int)a[0].size());
vector<vector<mint>> m(N, vector<mint>(2 * N));
for (int i = 0; i < N; i++) {
copy(begin(a[i]), end(a[i]), begin(m[i]));
m[i][N + i] = 1;
}
auto [rank, det] = GaussElimination(m, N, true);
if (rank != N) return {};
vector<vector<mint>> b(N);
for (int i = 0; i < N; i++) {
copy(begin(m[i]) + N, end(m[i]), back_inserter(b[i]));
}
return b;
}
template <class T>
struct Matrix {
vector<vector<T> > A;
Matrix() = default;
Matrix(int n, int m) : A(n, vector<T>(m, T())) {}
Matrix(int n) : A(n, vector<T>(n, T())){};
int H() const { return A.size(); }
int W() const { return A[0].size(); }
int size() const { return A.size(); }
inline const vector<T> &operator[](int k) const { return A[k]; }
inline vector<T> &operator[](int k) { return A[k]; }
static Matrix I(int n) {
Matrix mat(n);
for (int i = 0; i < n; i++) mat[i][i] = 1;
return (mat);
}
Matrix &operator+=(const Matrix &B) {
int n = H(), m = W();
assert(n == B.H() && m == B.W());
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j];
return (*this);
}
Matrix &operator-=(const Matrix &B) {
int n = H(), m = W();
assert(n == B.H() && m == B.W());
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j];
return (*this);
}
Matrix &operator*=(const Matrix &B) {
int n = H(), m = B.W(), p = W();
assert(p == B.H());
vector<vector<T> > C(n, vector<T>(m, T{}));
for (int i = 0; i < n; i++)
for (int k = 0; k < p; k++)
for (int j = 0; j < m; j++) C[i][j] += (*this)[i][k] * B[k][j];
A.swap(C);
return (*this);
}
Matrix &operator^=(long long k) {
Matrix B = Matrix::I(H());
while (k > 0) {
if (k & 1) B *= *this;
*this *= *this;
k >>= 1LL;
}
A.swap(B.A);
return (*this);
}
Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); }
Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); }
Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); }
Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); }
bool operator==(const Matrix &B) const {
assert(H() == B.H() && W() == B.W());
for (int i = 0; i < H(); i++)
for (int j = 0; j < W(); j++)
if (A[i][j] != B[i][j]) return false;
return true;
}
bool operator!=(const Matrix &B) const {
assert(H() == B.H() && W() == B.W());
for (int i = 0; i < H(); i++)
for (int j = 0; j < W(); j++)
if (A[i][j] != B[i][j]) return true;
return false;
}
Matrix inverse() const {
assert(H() == W());
Matrix B(H());
B.A = inverse_matrix(A);
return B;
}
friend ostream &operator<<(ostream &os, const Matrix &p) {
int n = p.H(), m = p.W();
for (int i = 0; i < n; i++) {
os << (i ? " " : "") << "[";
for (int j = 0; j < m; j++) {
os << p[i][j] << (j + 1 == m ? "]\n" : ",");
}
}
return (os);
}
T determinant() const {
Matrix B(*this);
assert(H() == W());
T ret = 1;
for (int i = 0; i < H(); i++) {
int idx = -1;
for (int j = i; j < W(); j++) {
if (B[j][i] != 0) {
idx = j;
break;
}
}
if (idx == -1) return 0;
if (i != idx) {
ret *= T(-1);
swap(B[i], B[idx]);
}
ret *= B[i][i];
T inv = T(1) / B[i][i];
for (int j = 0; j < W(); j++) {
B[i][j] *= inv;
}
for (int j = i + 1; j < H(); j++) {
T a = B[j][i];
if (a == 0) continue;
for (int k = i; k < W(); k++) {
B[j][k] -= B[i][k] * a;
}
}
}
return ret;
}
};
/**
* @brief 行列ライブラリ
*/
using namespace std;
namespace internal {
unsigned long long non_deterministic_seed() {
unsigned long long m =
chrono::duration_cast<chrono::nanoseconds>(
chrono::high_resolution_clock::now().time_since_epoch())
.count();
m ^= 9845834732710364265uLL;
m ^= m << 24, m ^= m >> 31, m ^= m << 35;
return m;
}
unsigned long long deterministic_seed() { return 88172645463325252UL; }
// 64 bit の seed 値を生成 (手元では seed 固定)
// 連続で呼び出すと同じ値が何度も返ってくるので注意
// #define RANDOMIZED_SEED するとシードがランダムになる
unsigned long long seed() {
#if defined(NyaanLocal) && !defined(RANDOMIZED_SEED)
return deterministic_seed();
#else
return non_deterministic_seed();
#endif
}
} // namespace internal
namespace my_rand {
using i64 = long long;
using u64 = unsigned long long;
// [0, 2^64 - 1)
u64 rng() {
static u64 _x = internal::seed();
return _x ^= _x << 7, _x ^= _x >> 9;
}
// [l, r]
i64 rng(i64 l, i64 r) {
assert(l <= r);
return l + rng() % u64(r - l + 1);
}
// [l, r)
i64 randint(i64 l, i64 r) {
assert(l < r);
return l + rng() % u64(r - l);
}
// choose n numbers from [l, r) without overlapping
vector<i64> randset(i64 l, i64 r, i64 n) {
assert(l <= r && n <= r - l);
unordered_set<i64> s;
for (i64 i = n; i; --i) {
i64 m = randint(l, r + 1 - i);
if (s.find(m) != s.end()) m = r - i;
s.insert(m);
}
vector<i64> ret;
for (auto& x : s) ret.push_back(x);
sort(begin(ret), end(ret));
return ret;
}
// [0.0, 1.0)
double rnd() { return rng() * 5.42101086242752217004e-20; }
// [l, r)
double rnd(double l, double r) {
assert(l < r);
return l + rnd() * (r - l);
}
template <typename T>
void randshf(vector<T>& v) {
int n = v.size();
for (int i = 1; i < n; i++) swap(v[i], v[randint(0, i + 1)]);
}
} // namespace my_rand
using my_rand::randint;
using my_rand::randset;
using my_rand::randshf;
using my_rand::rnd;
using my_rand::rng;
using namespace std;
namespace internal {
using namespace std;
// a mod p
template <typename T>
T safe_mod(T a, T p) {
a %= p;
if constexpr (is_broadly_signed_v<T>) {
if (a < 0) a += p;
}
return a;
}
// 返り値:pair(g, x)
// s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
template <typename T>
pair<T, T> inv_gcd(T a, T p) {
static_assert(is_broadly_signed_v<T>);
a = safe_mod(a, p);
if (a == 0) return {p, 0};
T b = p, x = 1, y = 0;
while (a != 0) {
T q = b / a;
swap(a, b %= a);
swap(x, y -= q * x);
}
if (y < 0) y += p / b;
return {b, y};
}
// 返り値 : a^{-1} mod p
// gcd(a, p) != 1 が必要
template <typename T>
T inv(T a, T p) {
static_assert(is_broadly_signed_v<T>);
a = safe_mod(a, p);
T b = p, x = 1, y = 0;
while (a != 0) {
T q = b / a;
swap(a, b %= a);
swap(x, y -= q * x);
}
assert(b == 1);
return y < 0 ? y + p : y;
}
// T : 底の型
// U : T*T がオーバーフローしない かつ 指数の型
template <typename T, typename U>
T modpow(T a, U n, T p) {
a = safe_mod(a, p);
T ret = 1 % p;
while (n != 0) {
if (n % 2 == 1) ret = U(ret) * a % p;
a = U(a) * a % p;
n /= 2;
}
return ret;
}
// 返り値 : pair(rem, mod)
// 解なしのときは {0, 0} を返す
template <typename T>
pair<T, T> crt(const vector<T>& r, const vector<T>& m) {
static_assert(is_broadly_signed_v<T>);
assert(r.size() == m.size());
int n = int(r.size());
T r0 = 0, m0 = 1;
for (int i = 0; i < n; i++) {
assert(1 <= m[i]);
T r1 = safe_mod(r[i], m[i]), m1 = m[i];
if (m0 < m1) swap(r0, r1), swap(m0, m1);
if (m0 % m1 == 0) {
if (r0 % m1 != r1) return {0, 0};
continue;
}
auto [g, im] = inv_gcd(m0, m1);
T u1 = m1 / g;
if ((r1 - r0) % g) return {0, 0};
T x = (r1 - r0) / g % u1 * im % u1;
r0 += x * m0;
m0 *= u1;
if (r0 < 0) r0 += m0;
}
return {r0, m0};
}
} // namespace internal
using namespace std;
template <typename Int, typename UInt, typename Long, typename ULong, int id>
struct ArbitraryLazyMontgomeryModIntBase {
using mint = ArbitraryLazyMontgomeryModIntBase;
inline static UInt mod;
inline static UInt r;
inline static UInt n2;
static constexpr int bit_length = sizeof(UInt) * 8;
static UInt get_r() {
UInt ret = mod;
while (mod * ret != 1) ret *= UInt(2) - mod * ret;
return ret;
}
static void set_mod(UInt m) {
assert(m < (UInt(1u) << (bit_length - 2)));
assert((m & 1) == 1);
mod = m, n2 = -ULong(m) % m, r = get_r();
}
UInt a;
ArbitraryLazyMontgomeryModIntBase() : a(0) {}
ArbitraryLazyMontgomeryModIntBase(const Long &b)
: a(reduce(ULong(b % mod + mod) * n2)){};
static UInt reduce(const ULong &b) {
return (b + ULong(UInt(b) * UInt(-r)) * mod) >> bit_length;
}
mint &operator+=(const mint &b) {
if (Int(a += b.a - 2 * mod) < 0) a += 2 * mod;
return *this;
}
mint &operator-=(const mint &b) {
if (Int(a -= b.a) < 0) a += 2 * mod;
return *this;
}
mint &operator*=(const mint &b) {
a = reduce(ULong(a) * b.a);
return *this;
}
mint &operator/=(const mint &b) {
*this *= b.inverse();
return *this;
}
mint operator+(const mint &b) const { return mint(*this) += b; }
mint operator-(const mint &b) const { return mint(*this) -= b; }
mint operator*(const mint &b) const { return mint(*this) *= b; }
mint operator/(const mint &b) const { return mint(*this) /= b; }
bool operator==(const mint &b) const {
return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
}
bool operator!=(const mint &b) const {
return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
}
mint operator-() const { return mint(0) - mint(*this); }
mint operator+() const { return mint(*this); }
mint pow(ULong n) const {
mint ret(1), mul(*this);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul, n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const mint &b) {
return os << b.get();
}
friend istream &operator>>(istream &is, mint &b) {
Long t;
is >> t;
b = ArbitraryLazyMontgomeryModIntBase(t);
return (is);
}
mint inverse() const {
Int x = get(), y = get_mod(), u = 1, v = 0;
while (y > 0) {
Int t = x / y;
swap(x -= t * y, y);
swap(u -= t * v, v);
}
return mint{u};
}
UInt get() const {
UInt ret = reduce(a);
return ret >= mod ? ret - mod : ret;
}
static UInt get_mod() { return mod; }
};
// id に適当な乱数を割り当てて使う
template <int id>
using ArbitraryLazyMontgomeryModInt =
ArbitraryLazyMontgomeryModIntBase<int, unsigned int, long long,
unsigned long long, id>;
template <int id>
using ArbitraryLazyMontgomeryModInt64bit =
ArbitraryLazyMontgomeryModIntBase<long long, unsigned long long, __int128_t,
__uint128_t, id>;
namespace fast_factorize {
template <typename T, typename U>
bool miller_rabin(const T& n, vector<T> ws) {
if (n <= 2) return n == 2;
if (n % 2 == 0) return false;
T d = n - 1;
while (d % 2 == 0) d /= 2;
U e = 1, rev = n - 1;
for (T w : ws) {
if (w % n == 0) continue;
T t = d;
U y = internal::modpow<T, U>(w, t, n);
while (t != n - 1 && y != e && y != rev) y = y * y % n, t *= 2;
if (y != rev && t % 2 == 0) return false;
}
return true;
}
bool miller_rabin_u64(unsigned long long n) {
return miller_rabin<unsigned long long, __uint128_t>(
n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}
template <typename mint>
bool miller_rabin(unsigned long long n, vector<unsigned long long> ws) {
if (n <= 2) return n == 2;
if (n % 2 == 0) return false;
if (mint::get_mod() != n) mint::set_mod(n);
unsigned long long d = n - 1;
while (~d & 1) d >>= 1;
mint e = 1, rev = n - 1;
for (unsigned long long w : ws) {
if (w % n == 0) continue;
unsigned long long t = d;
mint y = mint(w).pow(t);
while (t != n - 1 && y != e && y != rev) y *= y, t *= 2;
if (y != rev && t % 2 == 0) return false;
}
return true;
}
bool is_prime(unsigned long long n) {
using mint32 = ArbitraryLazyMontgomeryModInt<96229631>;
using mint64 = ArbitraryLazyMontgomeryModInt64bit<622196072>;
if (n <= 2) return n == 2;
if (n % 2 == 0) return false;
if (n < (1uLL << 30)) {
return miller_rabin<mint32>(n, {2, 7, 61});
} else if (n < (1uLL << 62)) {
return miller_rabin<mint64>(
n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
} else {
return miller_rabin_u64(n);
}
}
} // namespace fast_factorize
using fast_factorize::is_prime;
/**
* @brief Miller-Rabin primality test
*/
using namespace Nyaan;
void q() {
Timer timer;
ll p = 0;
do {
p = rng(9 * TEN(17), TEN(18));
} while (!is_prime(p));
auto modulo = [&](bigint x) -> ll { return (x % p).to_ll(); };
Matrix<bigint> m(2);
m[0][0] = m[0][1] = m[1][0] = 1;
m[1][1] = 0;
V<Matrix<bigint>> ms;
ms.push_back(m);
while (true) {
auto bc = ms.back();
bc *= bc;
if (bc[1][1].dfp().second > 2 * TEN(6) + 10) break;
ms.push_back(bc);
}
trc2(timer());
// (t 以下の fib のうち最大, 2 番目)
auto get = [&](bigint t) -> pair<bigint, bigint> {
int r = 0;
while (r < sz(ms) and ms[r][0][0] <= t) r++;
bigint x = 1, y = 0;
repr(i, r) {
bigint nx = ms[i][0][0] * x;
if (nx > t) continue;
nx += ms[i][0][1] * y;
if (nx > t) continue;
bigint ny = ms[i][1][0] * x + ms[i][1][1] * y;
x = nx, y = ny;
}
return {x, y};
};
#ifdef NyaanLocal
rep1(t, 1000) {
auto [x, y] = get(t);
assert(x <= t and x + y > t);
}
trc2("OK");
#endif
inl(N);
V<bigint> v(N);
in(v);
sort(all(v));
map<ll, int> mp;
ll ans = 0;
each(t, v) {
auto [x, y] = get(t);
trc(t, x, y);
rep(_, 2) {
bigint z = x + y;
ans += mp[modulo(z - t)];
y = x, x = z;
}
mp[modulo(t)]++;
}
out(ans);
trc2(timer());
}
void Nyaan::solve() {
int t = 1;
// in(t);
while (t--) q();
}
详细
Test #1:
score: 100
Accepted
time: 666ms
memory: 41712kb
input:
6 50 8 8 5 72 354224848179261915070
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2539ms
memory: 40260kb
input:
28 200878223506436882933619847964496455022155117513398820563747455993172799881403389571477889821109288771413214004090719097929400406252135763028179112130390003528046316900603668569910008417315162907579003880220844686222148696041857432602133894827753998572080650383305777912447151917272483538029469449...
output:
27
result:
ok 1 number(s): "27"
Test #3:
score: 0
Accepted
time: 993ms
memory: 39864kb
input:
5187 2640352926124261912741724778991366987330659389621881876017670644497364093930668042530271338851702874394631009332660937266680740235862107353443518003194307853104942996827176097428402408674756368623972812842571069642405111849826172879369776309763468485788964245903781380419155348915131587410703749...
output:
6073
result:
ok 1 number(s): "6073"
Test #4:
score: 0
Accepted
time: 858ms
memory: 41836kb
input:
200000 2 2 2 2 1 2 1 1 2 2 1 1 1 2 2 1 1 2 1 1 2 2 1 2 2 2 1 1 1 1 2 2 1 2 1 2 1 1 2 2 1 1 1 2 1 1 2 1 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 2 1 2 2 1 1 1 2 2 2 1 1 2 1 1 2 1 2 1 1 1 2 2 2 1 1 1 1 2 1 2 1 1 2 2 1 1 2 1 1 2 1 2 2 1 2 1 2 2 1 1 2 1 1 1 2 2 2 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 2 2 1 1 1 1 2 2 2 2...
output:
15003749259
result:
ok 1 number(s): "15003749259"
Test #5:
score: 0
Accepted
time: 1728ms
memory: 67700kb
input:
200000 944176313232170622314 2590599414036674999101 753315073608896000424 9299685298577430049245 9361800333778142620806 8988699166328904060999 9606920674025578304023 4203331868598952026136 5183047027116137697788 3968714342776915029801 8130984095583566992354 3206443643596048048798 6248561214283254355...
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 1174ms
memory: 40172kb
input:
200000 9 10 3 5 9 3 3 9 8 5 1 2 7 8 4 6 2 3 3 9 5 5 4 9 7 5 8 2 6 10 9 7 2 2 1 10 10 6 10 7 4 7 9 7 2 2 10 4 5 8 2 2 5 8 9 5 3 9 2 1 7 6 8 8 6 3 8 2 2 9 10 2 9 7 1 9 1 4 5 9 2 7 10 1 8 7 4 8 1 10 6 4 4 9 1 9 7 3 6 5 6 9 5 3 6 6 4 4 6 1 8 6 10 3 10 2 1 4 1 4 8 2 9 1 4 8 10 8 2 2 3 6 4 7 10 10 9 4 7 6...
output:
4388485679
result:
ok 1 number(s): "4388485679"
Test #7:
score: 0
Accepted
time: 1250ms
memory: 66336kb
input:
200000 6828421000391895 1989111434563275 5896525738540342 7580233289915833 7220157112714422 6690072177484914 6664449707566084 8245839001391019 3008772159581769 8148007474169818 9400853099859484 6346860654847919 7403109176990407 2581313740335401 1273038733901266 9824983373567665 7206452987542085 7181...
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1170ms
memory: 65708kb
input:
200000 163414517 35065810 104946881 686842158 509604537 114869915 194658958 55736013 211143419 526188788 18298540 311113507 727676120 517103071 25044427 38567543 386683792 246028194 750300322 4412101 865997254 674545866 775054146 977862574 699213474 347544102 740489922 632436817 297903184 435135324 ...
output:
59
result:
ok 1 number(s): "59"
Test #9:
score: 0
Accepted
time: 1751ms
memory: 41412kb
input:
2 2088564186870382794642016448725374479500907752342156600368614861600912666885211013490310624029649329209019866849808883315545780833167257516031795949145341911463438482795792374909577113387320732207052482556858037878075154734524317145645776084240387870219160545328462016106959746495953786767421892196...
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 1025ms
memory: 40032kb
input:
200000 6 1 3 9 1 8 9 9 2 6 8 6 2 3 9 2 2 7 4 7 8 8 4 8 2 7 8 9 2 9 2 4 4 1 10 6 2 10 2 6 8 3 10 3 6 10 10 10 2 4 6 4 7 8 1 2 1 1 4 10 5 5 4 10 3 8 5 6 1 7 8 1 2 6 3 8 9 9 5 1 9 5 6 10 9 4 1 7 8 3 10 4 3 2 7 7 9 4 5 6 6 7 8 10 6 6 3 6 8 1 7 4 2 6 10 8 4 2 7 4 2 5 4 9 10 5 2 3 2 4 8 7 9 7 7 8 2 5 7 2 ...
output:
4400854684
result:
ok 1 number(s): "4400854684"
Test #11:
score: 0
Accepted
time: 1224ms
memory: 66604kb
input:
200000 3118333850638 35270102833223 62994441325054 21050207685515 79452732606523 43405025574846 14676822470608 40589739145551 72610266245240 95906978427970 59399311725881 80286412880911 98171197939601 15555757959003 68766133429050 11529744877477 36884730947747 93994258932707 21245575958503 287958909...
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 1134ms
memory: 66260kb
input:
200000 1218982 621720 5848120 1753415 5889366 1747270 7735728 8089704 4279399 7927020 9269797 1332511 6334797 8964092 9525679 7325470 1527918 893049 8483303 1134021 8872739 532622 8977450 4503590 6512507 4903981 4892296 6522908 9237430 2297267 8063244 1546378 5054973 8702942 4392067 7868582 2029729 ...
output:
5695
result:
ok 1 number(s): "5695"
Test #13:
score: 0
Accepted
time: 1778ms
memory: 40572kb
input:
2 2088564186870382794642016448725374479500907752342156600368614861600912666885211013490310624029649329209019866849808883315545780833167257516031795949145341911463438482795792374909577113387320732207052482556858037878075154734524317145645776084240387870219160545328462016106959746495953786767421892196...
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 2574ms
memory: 40624kb
input:
7 1337338011484742791299410909385691591046809197321138600848517667449672944525104556519885455609314839827342014896149347803816156838828377155724440687227582622225528496005639283622580269360626125544811511998701746678193286138664078007880894120371020695543061391758951301196457121332483784041873539166...
output:
3
result:
ok 1 number(s): "3"
Test #15:
score: 0
Accepted
time: 1673ms
memory: 40852kb
input:
274 36199225654659696764078634911736913237817300779619275513532816361663892134832409526194170532894366762053993742963156407869241123825595148459428450874407641181641292360313933002704706339921470798414371554709977458935038423965022899542511184991008496997550268720067992926078576871685757638601127765...
output:
273
result:
ok 1 number(s): "273"
Test #16:
score: 0
Accepted
time: 1434ms
memory: 42672kb
input:
200000 4 3 8 5 8 9 4 10 1 3 7 1 3 10 1 10 10 7 8 2 8 9 6 6 1 2 2 6 6 7 10 7 1 3 6 2 8 4 3 3 8 9 4 3 9 6 4 1 6 3 3 5 4 2 3 9 3 3 6 7 6 1 5 5 2 10 2 1 5 9 6 7 3 2 9 1 3 8 8 3 10 7 5 5 6 9 10 8 1 5 6 2 1 8 5 4 1 7 9 9 2 8 9 8 5 7 4 9 3 3 4 7 9 1 8 1 5 9 8 8 7 10 1 4 2 3 7 8 6 1 10 10 8 9 4 10 4 5 5 6 9...
output:
4387062637
result:
ok 1 number(s): "4387062637"
Test #17:
score: 0
Accepted
time: 1853ms
memory: 65872kb
input:
200000 8244945625103564139 31587720380738895055 95764870267791202443 90342450187757930095 57990438361916446378 37041843791326956160 92044245094014254241 52147231507776742459 57440162490738372914 75951472709544205529 91095641579841704038 6354859395638708014 13171197741013485755 31875767906879519150 2...
output:
0
result:
ok 1 number(s): "0"
Test #18:
score: 0
Accepted
time: 672ms
memory: 39896kb
input:
10 6 8 6 6 7 6 3 3 2 6
output:
12
result:
ok 1 number(s): "12"
Test #19:
score: 0
Accepted
time: 1763ms
memory: 39980kb
input:
2 2088564186870382794642016448725374479500907752342156600368614861600912666885211013490310624029649329209019866849808883315545780833167257516031795949145341911463438482795792374909577113387320732207052482556858037878075154734524317145645776084240387870219160545328462016106959746495953786767421892196...
output:
0
result:
ok 1 number(s): "0"
Test #20:
score: 0
Accepted
time: 1249ms
memory: 66032kb
input:
200000 51732486464 15203118134 55665354475 37097810807 44823788729 92577384010 20189320156 62707564695 81665154265 89603063623 48003727587 14457078372 37230540002 65288477498 52282695470 76070393338 26054936545 14171092817 61770329497 85319218123 57730830347 20295186479 9036398880 63607160628 825711...
output:
1
result:
ok 1 number(s): "1"
Test #21:
score: 0
Accepted
time: 681ms
memory: 39996kb
input:
1000 7 2 6 10 8 6 1 4 5 4 8 6 9 4 1 5 1 5 2 10 6 8 10 10 1 3 4 2 10 1 9 2 7 6 7 9 10 6 9 8 3 2 10 7 6 5 4 3 1 10 5 3 5 1 8 6 5 10 5 7 10 4 9 1 10 9 4 8 8 7 8 5 9 1 5 6 2 10 1 10 9 10 10 10 1 5 3 10 10 3 3 9 10 3 9 1 5 7 6 5 2 9 7 9 10 4 9 1 7 7 5 8 10 8 8 5 5 6 1 5 5 6 10 2 1 1 2 5 9 5 3 5 6 8 5 3 8...
output:
108128
result:
ok 1 number(s): "108128"
Test #22:
score: 0
Accepted
time: 1495ms
memory: 40688kb
input:
170297 36618903089511909212027904 295898671290484359833820549055 855922209609024693421257591054 104046893712788281969810034913 294974348216094859258128389147 898675289823399842963411259541 849917444544425201790051381287 554091687601993279655091754543 100543835187751461953816001432 324625661878684349...
output:
669637
result:
ok 1 number(s): "669637"
Test #23:
score: 0
Accepted
time: 2248ms
memory: 41256kb
input:
9 1554055664340235444670436446744662342403532554270354440324316254234564540613440405260344004460144314614345467104554712624142524427154124266304046362254623626323466324132625200314136012323044624260020307414632254233433163613166424734133322715601644464634614352434441422431546266431240655123113002704...
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 658ms
memory: 41008kb
input:
30 173224810532175 17167616931584 361 605 17167680176960 956658780060 4052737359577 497497353099204 1548072001901 190392490708530 789347852872433 5 804010804445736 139520616464 43988911432793 4052739537276 514224 2178304 25273161431631 53314112869 17114366064696 20097096794 26821231255228 4944012745...
output:
29
result:
ok 1 number(s): "29"
Test #25:
score: 0
Accepted
time: 1814ms
memory: 41008kb
input:
100 11549310117176145486225764017375125851223984720694884717797775426631366931455266419214045399503089615971818090352858567015012529938870819767662704737995190471260542479965705803468920094883954929878415301662741322840828368641397254767329039284292920968364857914289821588505056486091849012400101879...
output:
36
result:
ok 1 number(s): "36"
Test #26:
score: 0
Accepted
time: 1379ms
memory: 44052kb
input:
100223 94009034043768394308211497706411911232935573312371 90700235808140495519523074128684120917303691406421 72874906060637684247409916135076680433361225881761 80161826274205256086415063126094978143520789283159 98145703778166390989463238108464755254200147417281 70995217131009339533392756476859088949...
output:
0
result:
ok 1 number(s): "0"
Test #27:
score: 0
Accepted
time: 663ms
memory: 40364kb
input:
6 50 8 8 5 72 354224848179261915070
output:
4
result:
ok 1 number(s): "4"
Test #28:
score: 0
Accepted
time: 1115ms
memory: 40584kb
input:
3161 7 14 130 1467 16244 105149 1241120 13689232 151890909 1684420994 10901848031 128682014414 1419326741506 15748353436059 101920677024935 1203048867903722 13269285156772499 147231358659594589 1632748057345119600 10567412357776757138 124734439986929988911 1375786096219966094366 15265241654400597567...
output:
3160
result:
ok 1 number(s): "3160"
Test #29:
score: 0
Accepted
time: 1267ms
memory: 66892kb
input:
200000 7930099016 7136448262 4599143849 4725192685 4685680672 739140078 7214691825 5031750793 4820916507 6017675339 485443032 2327198454 8808146518 7746012012 713572475 4706110510 3560774990 7482541413 8975601524 3896030632 3018545943 7048325939 2370597692 7867568189 6902951191 333917381 112842576 9...
output:
7
result:
ok 1 number(s): "7"
Test #30:
score: 0
Accepted
time: 731ms
memory: 40380kb
input:
60123 4 3 4 7 5 7 5 1 2 6 9 10 7 4 2 1 8 6 4 6 4 2 8 6 2 8 5 4 5 7 1 10 7 5 1 9 7 4 8 8 8 5 2 6 8 4 6 4 9 7 3 9 5 6 2 8 10 2 10 2 1 4 9 5 10 9 7 2 1 9 3 9 10 1 8 7 6 5 7 1 4 10 5 9 8 10 4 10 4 9 3 7 4 4 10 4 1 7 4 10 4 9 10 2 2 8 3 7 1 1 6 4 10 9 9 4 8 3 4 7 5 7 6 10 10 2 8 1 8 10 6 9 4 7 3 8 2 5 6 ...
output:
399686351
result:
ok 1 number(s): "399686351"
Test #31:
score: 0
Accepted
time: 662ms
memory: 41660kb
input:
20 11142320330634256153203413422244004724022423010341634226101444226235404243251 1510233372263004374041444256322353356243032432623343544033530634305504714430614564334410564323262245 3315442551434205740422347432544540327016564444656542244600440525402604662333366 53153452623340724302644316423336472713...
output:
0
result:
ok 1 number(s): "0"
Test #32:
score: 0
Accepted
time: 661ms
memory: 40480kb
input:
15 9227465 832040 701408733 2178309 267914296 433494437 165580141 1346269 5702887 3524578 102334155 24157817 14930352 63245986 39088169
output:
14
result:
ok 1 number(s): "14"
Test #33:
score: 0
Accepted
time: 762ms
memory: 41252kb
input:
10011 5327909559109070794570420158512927656597532686406620479564191583982981578330651724849734045529811497 9659152635523321620063357842120653540264735554377366787893904211734024058449827205523008852363337860 74727969709789190305111991663528709940303307406256850364862896747520682645094217166643105732...
output:
0
result:
ok 1 number(s): "0"
Test #34:
score: 0
Accepted
time: 1000ms
memory: 40880kb
input:
10051 63063334260332707210045601560460743222655443603043556526226343270234640534370464564114515210165526527443654044521634373434642424304154632545440427364312534131536671541443033313334224226302334143144172200431314323334240461563243422303322351122343066463334623434 625665325411647124616714317265541...
output:
14
result:
ok 1 number(s): "14"
Test #35:
score: 0
Accepted
time: 1345ms
memory: 67168kb
input:
200000 3231427058997 5671035772108 505876205893 9869979702346 336233080766 4805367039084 270125613380 929924360332 6390838551951 1896341268898 3923051450784 397979630166 6527843499305 1937207519921 9355189911971 953387547771 5307619807657 6689006266290 517624961010 1532034993156 1921439567851 331239...
output:
0
result:
ok 1 number(s): "0"
Test #36:
score: 0
Accepted
time: 2060ms
memory: 40732kb
input:
30 167491015938836604073444715975948275020752570351918554475806772549228015468626967999929915531115950274814727218152384400389926950026165552262394643249255747252904223055992443689134599380405599101636105379410012227917206510976118633243994494607279010051579617303878166798657109212106136099974387457...
output:
29
result:
ok 1 number(s): "29"
Test #37:
score: 0
Accepted
time: 1082ms
memory: 40564kb
input:
200000 31520 9835 67679 91981 37157 27950 36846 70635 13880 18818 52443 46788 38014 56271 48270 28452 36146 82523 60850 55346 16869 95814 89245 98640 40746 68625 53391 63023 4402 36521 95532 52344 24072 70060 11619 12227 98964 78211 95010 83216 22122 46697 31271 85556 57237 82689 92115 88247 9186 85...
output:
555586
result:
ok 1 number(s): "555586"
Test #38:
score: 0
Accepted
time: 1751ms
memory: 40948kb
input:
2 7471143542670631923583760838674866685142093708045228091216520373087113961892117195149240140968159205634006625906479367372855893882103887377565868731323681755476477285090435798416695243644387513257156317699123267511524797133211810893688279220755514610253525742595752854587254548452737426517576583616...
output:
1
result:
ok 1 number(s): "1"
Test #39:
score: 0
Accepted
time: 747ms
memory: 40088kb
input:
80000 6 4 5 5 4 5 9 8 5 6 2 2 1 10 6 9 4 10 6 5 3 4 3 3 4 5 10 2 6 4 6 2 6 2 4 7 9 6 6 8 1 1 7 10 10 2 7 2 2 9 8 5 4 9 1 5 7 4 7 7 6 7 7 9 8 9 9 4 10 7 2 9 9 9 4 2 8 4 9 1 3 9 1 4 2 1 2 4 3 2 1 10 5 7 10 5 9 3 6 3 4 4 1 8 1 8 10 8 6 6 2 5 1 3 6 8 2 2 10 6 6 3 2 6 3 8 4 10 8 10 3 9 9 2 8 8 10 4 5 5 7...
output:
706251650
result:
ok 1 number(s): "706251650"
Test #40:
score: 0
Accepted
time: 1447ms
memory: 42732kb
input:
200000 9 1 4 4 5 2 4 9 7 5 3 6 6 8 4 7 2 1 9 10 8 2 1 4 9 3 10 8 1 5 5 8 2 9 3 1 9 3 9 4 9 10 4 5 4 4 2 1 1 7 5 7 7 3 6 8 10 6 4 1 5 2 5 5 9 4 10 2 10 7 9 5 2 7 4 9 7 5 2 1 4 7 6 7 10 9 10 2 10 4 9 1 7 5 7 3 1 4 5 2 6 6 2 4 8 8 7 9 10 4 10 2 1 10 10 5 10 1 1 6 7 8 8 7 5 8 3 8 1 1 10 8 9 10 7 3 8 6 4...
output:
4417250451
result:
ok 1 number(s): "4417250451"
Test #41:
score: 0
Accepted
time: 1195ms
memory: 40956kb
input:
84752 86009844223237105273313186367406421847273312848013100091343 340516459610995530579473198046278412250343444815876655725270 62236463822700922600990709332929319814536375509143833251557 5611500219672931601067284378715174151735452175901717138530 64201778346042476353565735947990316834224189505881 609...
output:
420579
result:
ok 1 number(s): "420579"
Test #42:
score: 0
Accepted
time: 1602ms
memory: 67296kb
input:
200000 7127173784651987052 4249291679502906721 9703708230592019478 4404701921242244700 2344941043578422215 3091914365064271594 9867051863259427168 9880844309023770200 7211977710785226267 1694381065563438860 201683809955321192 4085536489000602058 7553409623903962290 4033981640350364868 54455660173955...
output:
0
result:
ok 1 number(s): "0"
Test #43:
score: 0
Accepted
time: 1540ms
memory: 44316kb
input:
200000 9 9 2 10 3 4 3 9 7 7 8 5 9 9 7 5 8 5 7 1 5 6 3 2 7 5 7 7 2 9 8 6 2 1 8 1 3 4 10 2 3 4 4 7 4 10 8 6 1 5 3 3 3 5 5 8 6 9 3 6 5 4 2 8 10 9 1 5 1 4 8 9 4 3 4 9 10 3 6 2 10 3 3 6 6 7 4 9 5 2 1 8 8 7 308061521170126 7 4 6 1 9 3 9 9 3 1 10 8 7 2 9 10 6 2 6 10 8 5 1 5 1 7 9 5 3 6 1 4 2 6 2 8 5 3 1 6 ...
output:
4397248166
result:
ok 1 number(s): "4397248166"
Test #44:
score: 0
Accepted
time: 921ms
memory: 41328kb
input:
156 18459619692692557705784877669569448552986613407875981372394172107449477143544507182981317111359110933094916231296859516709399078435198069511763391151449973008095601542066128297192521457018669738382503324519683244087838172215626103362576668917140635977557324975206273718561053735845026938082217687...
output:
155
result:
ok 1 number(s): "155"
Test #45:
score: 0
Accepted
time: 1422ms
memory: 41564kb
input:
200000 1 10 4 3 10 1 9 5 9 4 9 1 6 6 1 7 2 1 10 3 2 3 4 7 7 3 9 9 10 3 4 10 10 7 7 2 5 10 9 6 8 1 4 4 5 8 8 6 5 10 10 9 10 9 5 1 7 6 5 10 2 4 1 7 10 6 7 8 2 3 3 10 1 7 6 10 2 7 1 9 6 10 8 4 7 3 9 1 6 9 2 3 4 8 7 8 3 6 4 10 2 2 1 9 7 2 2 8 2 1 2 10 5 4 10 9 9 7 9 4 3 10 9 1 2 9 9 2 7 1 6 7 10 6 5 9 6...
output:
4407433502
result:
ok 1 number(s): "4407433502"
Test #46:
score: 0
Accepted
time: 1108ms
memory: 41212kb
input:
51002 376123568879569384290612536925367837315702704676220875375604948366932308891841579226324979782110 28623980260058260408921525210046136035459718869538444006842678034295486291710095655185249062457587 21690449377523978494384257361181223226054780834691728496618681724478608654823982012150023238151530...
output:
81486
result:
ok 1 number(s): "81486"
Test #47:
score: 0
Accepted
time: 1304ms
memory: 67180kb
input:
200000 478606336755874083 603529542039676573 240066379679942455 20635508638460497 945472883349378253 395868479387568634 865948317871000880 136079313625171264 764680881358360622 195117422398549932 143437863196805305 907507515211279442 723479709912499971 671617918537158715 439287855279754360 202716825...
output:
0
result:
ok 1 number(s): "0"
Test #48:
score: 0
Accepted
time: 2283ms
memory: 39808kb
input:
19 114661534643152246311744033174352334643324503262044605562234546544736534426056314403004340112331342520053464440541422433562206354434233744572233143044234304056542423441346156352252422334142225474302135741207345424432300443162054415443457163346015613444533444074633135446264371437171714063445404655...
output:
0
result:
ok 1 number(s): "0"
Test #49:
score: 0
Accepted
time: 1273ms
memory: 66560kb
input:
200000 497856383454 506720870857 899176487457 12145678485 541966940864 272264831455 178825186059 7038707436 481602633783 181735126537 559631305498 335603421321 761406732158 369431205173 615437274239 923671138603 543441698085 733638673698 858564208935 726626729204 880133143653 415511404815 9211110013...
output:
1
result:
ok 1 number(s): "1"
Test #50:
score: 0
Accepted
time: 2480ms
memory: 40068kb
input:
5 2011068126132617886949194530211424837999019187297342375967282498616949073685995418305378991927261698758022155241855161670361072821581948280878066032787805987660111096801265330758292151243775781982581126595354464038574958455139626266660161003165949122588221798586300395825356961553839057885407409810...
output:
4
result:
ok 1 number(s): "4"
Test #51:
score: 0
Accepted
time: 948ms
memory: 41216kb
input:
200000 91 67 28 7 87 97 87 80 71 5 67 1 98 85 60 62 99 46 9 81 10 7 15 91 74 69 11 34 85 47 56 48 29 16 25 5 46 9 73 24 84 10 97 22 78 18 29 70 92 98 61 43 54 66 55 15 77 20 25 16 84 11 93 65 61 91 18 59 31 93 53 33 34 59 90 41 21 27 82 49 33 64 96 18 46 71 94 95 30 62 47 9 62 79 29 28 65 67 32 48 9...
output:
591328867
result:
ok 1 number(s): "591328867"
Extra Test:
score: 0
Extra Test Passed