結果
| 問題 | No.3533 Difficult Counting Problem? |
| コンテスト | |
| ユーザー |
 7deQSJCy8c4Hg7I
|
| 提出日時 | 2026-05-08 21:29:39 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 25,364 bytes |
| 記録 | |
| コンパイル時間 | 8,171 ms |
| コンパイル使用メモリ | 421,492 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-05-08 21:29:55 |
| 合計ジャッジ時間 | 9,038 ms |
|
ジャッジサーバーID （参考情報） |
judge2_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 17 |
ソースコード
#if __INCLUDE_LEVEL__ == 0
#include __BASE_FILE__
void solve() {
ll t;
ll N, M, K;
ll a = 0, b = 0, c = 0;
string S, T;
cin >>N;
cout << (N<=1) <<'\n';
}
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << std::fixed << std::setprecision(20);
int t = 1;
cin >> t;
rep(_, t) solve();
}
#elif __INCLUDE_LEVEL__ == 2
#elif __INCLUDE_LEVEL__ == 1
#pragma once
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int> >;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vb = vector<bool>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vvvvvll = vector<vvvvll>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vld = vector<long double>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) n.begin(), n.end()
#define rALL(n) n.rbegin(), n.rend()
#define fore(i, a) for (auto& i : a)
#define IN(a, x, b) (a <= x && x < b)
#define IN(a, x, b) (a <= x && x < b)
#define INIT \
std::ios::sync_with_stdio(false); \
std::cin.tie(0);
#pragma once
template <typename T>
// [0,M)についての階上を求める
vector<T> KAI(int M) {
vector<T> kai(M, 1);
rep(i, M - 1) { kai[i + 1] = kai[i] * (i + 1); }
return kai;
}
template <typename T>
vector<T> DIV(int M) {
vector<T> kai = KAI<T>(M), div(M, 1);
div.back() /= kai.back();
for (int i = M - 2; i >= 0; --i) {
div[i] = div[i + 1] * (i + 1);
}
return div;
}
long long Power(long long a, long long b, long long m) {
long long p = a, Answer = 1;
p %= m;
for (int i = 0; i < 62; i++) {
ll wari = (1LL << i);
if ((b / wari) % 2 == 1) {
Answer %= m;
Answer = (Answer * p) % m;
// 「a の 2^i 乗」が掛けられるとき
}
ll t = p % m;
p = (t * t) % m;
// cout << p << endl;
}
return Answer;
}
// a ÷ b を m で割った余りを返す関数え
long long Division(long long a, long long b, long long m) {
return (a * Power(b, m - 2, m)) % m;
}
template <class T>
void output(T& W, bool x) {
cout << W;
if (!x)
cout << ' ';
else
cout << endl;
return;
}
// sは改行するか否かを表す
template <class T>
void output(vector<T>& W, bool s) {
rep(i, W.size()) { output(W[i], ((i == W.size() - 1) || s)); }
return;
}
// sは改行するか否かを表す
template <class T>
void output(vector<vector<T> >& W, bool s) {
rep(i, W.size()) { output(W[i], s); }
return;
}
template <class T>
T vectorsum(vector<T>& W, int a, int b) {
return accumulate(W.begin() + a, W.end() + b, (T)0);
}
template <class T>
T vectorsum(vector<T>& W) {
int b = W.size();
return accumulate(ALL(W), (T)0);
}
template <class T>
inline T CHMAX(T& a, const T b) {
return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
return a = (a > b) ? b : a;
}
template <class T>
void input(T& W) {
cin >> W;
return;
}
template <class T>
void input(vector<T>& W) {
for (auto& u : W) input(u);
return;
}
template <class T, class TT>
void add(T& W, TT& a) {
W += a;
return;
}
template <class T>
void add(vector<T>& W, vector<T>& a) {
rep(i, W.size()) add(W[i], a[i]);
}
template <class T>
void add(T& W, T& a) {
W += a;
}
template <class T, class TT>
void add(vector<T>& W, TT a) {
for (auto& u : W) add(u, a);
return;
}
vll dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
void Yes(bool b) {
if (b)
cout << "Yes" << '\n';
else
cout << "No" << '\n';
}
struct TRI {
ll a;
ll b;
ll c;
ll d;
};
bool operator>(const TRI& r, const TRI& l) {
return (r.a > l.a | (r.a == l.a & r.b > l.b) |
(r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TRI& r, const TRI& l) {
return (r.a < l.a | (r.a == l.a & r.b < l.b) |
(r.a == l.a & r.b == l.b & r.c < l.c));
}
struct TRK {
ll a;
ll b;
ll c;
};
bool operator>(const TRK& r, const TRK& l) {
return (r.a > l.a | (r.a == l.a & r.b > l.b) |
(r.a == l.a & r.b == l.b & r.c > l.c));
}
bool operator<(const TRK& r, const TRK& l) {
return (r.a < l.a | (r.a == l.a & r.b < l.b) |
(r.a == l.a & r.b == l.b & r.c < l.c));
}
struct Mo {
int n;
vector<pair<int, int> > lr;
explicit Mo(int n) : n(n) {}
void add(int l, int r) { /* [l, r) */ lr.emplace_back(l, r); }
template <typename AL, typename AR, typename EL, typename ER, typename O>
void build(const AL& add_left, const AR& add_right, const EL& erase_left,
const ER& erase_right, const O& out) {
int q = (int)lr.size();
int bs = n / min<int>(n, sqrt(q));
vector<int> ord(q);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), [&](int a, int b) {
int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
if (ablock != bblock) return ablock < bblock;
return (ablock & 1) ? lr[a].second > lr[b].second
: lr[a].second < lr[b].second;
});
int l = 0, r = 0;
for (auto idx : ord) {
while (l > lr[idx].first) add_left(--l, r);
while (r < lr[idx].second) add_right(l, r++);
while (l < lr[idx].first) erase_left(l++, r);
while (r > lr[idx].second) erase_right(l, --r);
out(idx);
}
}
template <typename A, typename E, typename O>
void build(const A& add, const E& erase, const O& out) {
build(add, add, erase, erase, out);
}
};
namespace RangeChMinMaxAddSum {
template <typename Num>
inline Num second_lowest(Num a, Num a2, Num c, Num c2) noexcept {
// a < a2, c < c2 のとき全引数を昇順ソートして二番目の値
return a == c ? std::min(a2, c2)
: a2 <= c ? a2
: c2 <= a ? c2
: std::max(a, c);
}
template <typename Num>
inline Num second_highest(Num a, Num a2, Num b, Num b2) noexcept {
// a > a2, b > b2 のとき全引数を降順ソートして二番目の値
return a == b ? std::max(a2, b2)
: a2 >= b ? a2
: b2 >= a ? b2
: std::min(a, b);
}
using BNum = long long;
constexpr BNum BINF = 1LL << 61;
struct S {
BNum lo, hi, lo2, hi2,
sum; // 区間最小・最大値，区間最小・最大から二番目の値，区間総和
unsigned sz, nlo, nhi; // 区間要素数，区間最小・最大値をとる要素の個数
bool fail;
S()
: lo(BINF),
hi(-BINF),
lo2(BINF),
hi2(-BINF),
sum(0),
sz(0),
nlo(0),
nhi(0),
fail(0) {}
S(BNum x, unsigned sz_ = 1)
: lo(x),
hi(x),
lo2(BINF),
hi2(-BINF),
sum(x * sz_),
sz(sz_),
nlo(sz_),
nhi(sz_),
fail(0) {}
};
S e() { return S(); }
S op(S l, S r) {
S ret;
ret.lo = std::min(l.lo, r.lo), ret.hi = std::max(l.hi, r.hi);
ret.lo2 = second_lowest(l.lo, l.lo2, r.lo, r.lo2);
ret.hi2 = second_highest(l.hi, l.hi2, r.hi, r.hi2);
ret.sum = l.sum + r.sum, ret.sz = l.sz + r.sz;
ret.nlo = l.nlo * (l.lo <= r.lo) + r.nlo * (r.lo <= l.lo);
ret.nhi = l.nhi * (l.hi >= r.hi) + r.nhi * (r.hi >= l.hi);
return ret;
}
struct F {
BNum lb, ub, bias;
F(BNum chmax_ = -BINF, BNum chmin_ = BINF, BNum add = 0)
: lb(chmax_), ub(chmin_), bias(add) {}
static F chmin(BNum x) noexcept { return F(-BINF, x, BNum(0)); }
static F chmax(BNum x) noexcept { return F(x, BINF, BNum(0)); }
static F add(BNum x) noexcept { return F(-BINF, BINF, x); };
};
F composition(F fnew, F fold) {
F ret;
ret.lb =
std::max(std::min(fold.lb + fold.bias, fnew.ub), fnew.lb) - fold.bias;
ret.ub =
std::min(std::max(fold.ub + fold.bias, fnew.lb), fnew.ub) - fold.bias;
ret.bias = fold.bias + fnew.bias;
return ret;
}
F id() { return F(); }
S mapping(F f, S x) {
if (x.sz == 0)
return e();
else if (x.lo == x.hi or f.lb == f.ub or f.lb >= x.hi or f.ub <= x.lo) {
return S(std::min(std::max(x.lo, f.lb), f.ub) + f.bias, x.sz);
} else if (x.lo2 == x.hi) {
x.lo = x.hi2 = std::max(x.lo, f.lb) + f.bias;
x.hi = x.lo2 = std::min(x.hi, f.ub) + f.bias;
x.sum = x.lo * x.nlo + x.hi * x.nhi;
return x;
} else if (f.lb < x.lo2 and f.ub > x.hi2) {
BNum nxt_lo = std::max(x.lo, f.lb), nxt_hi = std::min(x.hi, f.ub);
x.sum +=
(nxt_lo - x.lo) * x.nlo - (x.hi - nxt_hi) * x.nhi + f.bias * x.sz;
x.lo = nxt_lo + f.bias, x.hi = nxt_hi + f.bias, x.lo2 += f.bias,
x.hi2 += f.bias;
return x;
}
x.fail = 1;
return x;
}
using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
} // namespace RangeChMinMaxAddSum
std::random_device rnd;
std::mt19937 mt(rnd());
default_random_engine engineX(rnd());
// 平均0.0、標準偏差1.0で分布させる
std::normal_distribution<> seikidist(0.0, 1.0);
template <class T>
// 0以上K未満の整数を等確率で発生させる
long long randomX(T K) {
uniform_int_distribution<ll> select(0, K - 1);
return select(mt);
}
template <typename T>
vector<T> dycstra(vector<vector<pair<ll, T> > > G, ll N, ll K) {
vb kaku(N, false);
vector<T> cur(N, 1e18);
cur[K] = 0;
priority_queue<pair<T, ll>, vector<pair<T, ll> >, greater<pair<T, ll> > > Q;
Q.push(make_pair(cur[K], K));
while (!Q.empty()) {
ll pos = Q.top().second;
Q.pop();
if (kaku[pos]) continue;
kaku[pos] = true;
for (ll i = 0; i < G[pos].size(); i++) {
ll nex = G[pos][i].first;
T cost = G[pos][i].second;
if (cur[nex] > cur[pos] + cost) {
cur[nex] = cur[pos] + cost;
Q.push(make_pair(cur[nex], nex));
}
}
}
return cur;
}
// 意図的な衝突を防ぐためのカスタムハッシャー
struct SafeHasher {
static uint64_t splitmix64(uint64_t x) {
// 固定値ではなく、ビットを十分に拡散させるためのミキシング関数
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
// static修飾子により、プログラム実行中に一度だけ初期化される
static const uint64_t FIXED_RANDOM = []() {
std::random_device rd;
// 64ビットの高品質な乱数生成器
std::mt19937_64 gen(rd());
std::uniform_int_distribution<uint64_t> dis;
return dis(gen);
}();
return splitmix64(x + FIXED_RANDOM);
}
};
namespace rolling_hash_on_segtree_INVAl {
struct Sx {
ll value; // 値
ll x; // 乱択で選ばれた数をHASHとすると右側にいくつHASYがあるか(説明が難しい)
ll mod; // modはmod
// 値更新型の遅延セグ木を作りたければ長さを追加する必要もある
};
Sx op(Sx a, Sx b) {
return {((a.value * b.x) % a.mod + b.value) % a.mod, (a.x * b.x) % a.mod,
a.mod};
}
// １つ目のmodに対応した単位元
Sx e() { return {0, 1, 998244353}; }
// 2つ目のmodに対応した単位元
Sx e2() { return {0, 1, 1000000007}; }
// 念のため２つ用意してある(1つで十分だと思う...)
vector<ll> MOD = {998244353, 1000000007};
segtree<Sx, op, e> segS, segT;
segtree<Sx, op, e2> segS1, segT1;
ll a = randomX(998244351) + 2;
ll b = randomX(1000000005) + 2;
vector<ll> HASH = {a, b};
// 参考(https://nyaannyaan.github.io/library/string/rolling-hash-on-segment-tree.hpp.html)
struct rolling_hash_on_segtree {
private:
int n{};
vector<ll> A, B;
public:
rolling_hash_on_segtree() = default;
explicit rolling_hash_on_segtree(int n, vector<ll> A, vector<ll> B)
: n(n), A(A), B(B) {
build(n, A, B);
};
explicit rolling_hash_on_segtree(vector<ll> A, vector<ll> B)
: rolling_hash_on_segtree(A.size(), A, B) {};
void build(int n, vector<ll>& A, vector<ll>& B) {
segtree<Sx, op, e> r(n);
segS = r;
segT = r;
rep(i, A.size()) segS.set(i, {A[i], a, MOD[0]});
rep(i, B.size()) segT.set(i, {B[i], a, MOD[0]});
segtree<Sx, op, e2> r2(n);
segS1 = r2;
segT1 = r2;
rep(i, A.size()) segS1.set(i, {A[i], b, MOD[1]});
rep(i, B.size()) segT1.set(i, {B[i], b, MOD[1]});
return;
}
// １番目のk番目の要素をkに変更する
void setS(int k, ll x) {
segS.set(k, {x, HASH[0], MOD[0]}), segS1.set(k, {x, HASH[1], MOD[1]});
}
// 2番目のk番目の要素をkに変更する
void setT(int k, ll x) {
segT.set(k, {x, HASH[0], MOD[0]}), segT1.set(k, {x, HASH[1], MOD[1]});
}
// i∈[l,r)を満たす１番目の文字列のハッシュ値
vector<ll> prodS(int l, int r) {
return {segS.prod(l, r).value, segS1.prod(l, r).value};
}
// i∈[l,r)を満たす2番目の文字列のハッシュ値
vector<ll> prodT(int l, int r) {
return {segT.prod(l, r).value, segT1.prod(l, r).value};
}
// i∈[0,n)を満たす１番目の文字列のハッシュ値
vector<ll> all_prodS() {
return {segS.all_prod().value, segS1.all_prod().value};
}
// i∈[0,n)を満たす2番目の文字列のハッシュ値
vector<ll> all_prodT() {
return {segT.all_prod().value, segT1.all_prod().value};
}
// 1番目の文字列[l,r)と2番目の文字列[l1,r1)の文字列の一致判定
bool same(int l, int r, int l1, int r1) {
if (r - l != r1 - l1) return false;
if (r < l || r1 < l1) return false;
return prodS(l, r) == prodT(l1, r1);
}
// 1番目のハッシュ値を返す
ll HASH_S() { return a; }
// 2番目のハッシュ値を返す
ll HASH_T() { return b; }
// 全てのハッシュの変換
vector<ll> ALL_HASH() { return HASH; }
};
} // namespace rolling_hash_on_segtree_INVAl
// namespace rolling_hash_on_segtree_INVAl
using rolling_hash_on_segtree_INVAl::rolling_hash_on_segtree;
template <typename mint>
struct FormalPowerSeries : vector<mint> {
using vector<mint>::vector;
using FPS = FormalPowerSeries;
FPS& operator+=(const FPS& r) {
if (r.size() > this->size()) this->resize(r.size());
for (int i = 0; i < (int)r.size(); i++) (*this)[i] += r[i];
return *this;
}
FPS& operator+=(const mint& r) {
if (this->empty()) this->resize(1);
(*this)[0] += r;
return *this;
}
FPS& operator-=(const FPS& r) {
if (r.size() > this->size()) this->resize(r.size());
for (int i = 0; i < (int)r.size(); i++) (*this)[i] -= r[i];
return *this;
}
FPS& operator-=(const mint& r) {
if (this->empty()) this->resize(1);
(*this)[0] -= r;
return *this;
}
FPS& operator*=(const mint& v) {
for (int k = 0; k < (int)this->size(); k++) (*this)[k] *= v;
return *this;
}
FPS& operator/=(const FPS& r) {
if (this->size() < r.size()) {
this->clear();
return *this;
}
int n = this->size() - r.size() + 1;
if ((int)r.size() <= 64) {
FPS f(*this), g(r);
g.shrink();
mint coeff = g.back().inverse();
for (auto& x : g) x *= coeff;
int deg = (int)f.size() - (int)g.size() + 1;
int gs = g.size();
FPS quo(deg);
for (int i = deg - 1; i >= 0; i--) {
quo[i] = f[i + gs - 1];
for (int j = 0; j < gs; j++) f[i + j] -= quo[i] * g[j];
}
*this = quo * coeff;
this->resize(n, mint(0));
return *this;
}
return *this = ((*this).rev().pre(n) * r.rev().inv(n)).pre(n).rev();
}
FPS& operator%=(const FPS& r) {
*this -= *this / r * r;
shrink();
return *this;
}
FPS operator+(const FPS& r) const { return FPS(*this) += r; }
FPS operator+(const mint& v) const { return FPS(*this) += v; }
FPS operator-(const FPS& r) const { return FPS(*this) -= r; }
FPS operator-(const mint& v) const { return FPS(*this) -= v; }
FPS operator*(const FPS& r) const { return FPS(*this) *= r; }
FPS operator*(const mint& v) const { return FPS(*this) *= v; }
FPS operator/(const FPS& r) const { return FPS(*this) /= r; }
FPS operator%(const FPS& r) const { return FPS(*this) %= r; }
FPS operator-() const {
FPS ret(this->size());
for (int i = 0; i < (int)this->size(); i++) ret[i] = -(*this)[i];
return ret;
}
void shrink() {
while (this->size() && this->back() == mint(0)) this->pop_back();
}
FPS rev() const {
FPS ret(*this);
reverse(begin(ret), end(ret));
return ret;
}
FPS dot(FPS r) const {
FPS ret(min(this->size(), r.size()));
for (int i = 0; i < (int)ret.size(); i++) ret[i] = (*this)[i] * r[i];
return ret;
}
// 前 sz 項を取ってくる。sz に足りない項は 0 埋めする
FPS pre(int sz) const {
FPS ret(begin(*this), begin(*this) + min((int)this->size(), sz));
if ((int)ret.size() < sz) ret.resize(sz);
return ret;
}
FPS operator>>(int sz) const {
if ((int)this->size() <= sz) return {};
FPS ret(*this);
ret.erase(ret.begin(), ret.begin() + sz);
return ret;
}
FPS operator<<(int sz) const {
FPS ret(*this);
ret.insert(ret.begin(), sz, mint(0));
return ret;
}
FPS diff() const {
const int n = (int)this->size();
FPS ret(max(0, n - 1));
mint one(1), coeff(1);
for (int i = 1; i < n; i++) {
ret[i - 1] = (*this)[i] * coeff;
coeff += one;
}
return ret;
}
FPS integral() const {
const int n = (int)this->size();
FPS ret(n + 1);
ret[0] = mint(0);
if (n > 0) ret[1] = mint(1);
auto mod = mint::get_mod();
for (int i = 2; i <= n; i++) ret[i] = (-ret[mod % i]) * (mod / i);
for (int i = 0; i < n; i++) ret[i + 1] *= (*this)[i];
return ret;
}
mint eval(mint x) const {
mint r = 0, w = 1;
for (auto& v : *this) r += w * v, w *= x;
return r;
}
FPS log(int deg = -1) const {
assert(!(*this).empty() && (*this)[0] == mint(1));
if (deg == -1) deg = (int)this->size();
return (this->diff() * this->inv(deg)).pre(deg - 1).integral();
}
FPS pow(int64_t k, int deg = -1) const {
const int n = (int)this->size();
if (deg == -1) deg = n;
if (k == 0) {
FPS ret(deg);
if (deg) ret[0] = 1;
return ret;
}
for (int i = 0; i < n; i++) {
if ((*this)[i] != mint(0)) {
mint rev = mint(1) / (*this)[i];
FPS ret = (((*this * rev) >> i).log(deg) * k).exp(deg);
ret *= (*this)[i].pow(k);
ret = (ret << (i * k)).pre(deg);
if ((int)ret.size() < deg) ret.resize(deg, mint(0));
return ret;
}
if (__int128_t(i + 1) * k >= deg) return FPS(deg, mint(0));
}
return FPS(deg, mint(0));
}
static void* ntt_ptr;
static void set_fft();
FPS& operator*=(const FPS& r);
void ntt();
void intt();
void ntt_doubling();
static int ntt_pr();
FPS inv(int deg = -1) const;
FPS exp(int deg = -1) const;
};
template <typename mint>
void* FormalPowerSeries<mint>::ntt_ptr = nullptr;
/**
* @brief 多項式/形式的冪級数ライブラリ
* @docs docs/fps/formal-power-series.md
*/
template <typename mint>
mint LinearRecurrence(long long k, FormalPowerSeries<mint> Q,
FormalPowerSeries<mint> P) {
Q.shrink();
mint ret = 0;
if (P.size() >= Q.size()) {
auto R = P / Q;
P -= R * Q;
P.shrink();
if (k < (int)R.size()) ret += R[k];
}
if ((int)P.size() == 0) return ret;
FormalPowerSeries<mint>::set_fft();
if (FormalPowerSeries<mint>::ntt_ptr == nullptr) {
P.resize((int)Q.size() - 1);
while (k) {
auto Q2 = Q;
for (int i = 1; i < (int)Q2.size(); i += 2) Q2[i] = -Q2[i];
auto S = P * Q2;
auto T = Q * Q2;
if (k & 1) {
for (int i = 1; i < (int)S.size(); i += 2) P[i >> 1] = S[i];
for (int i = 0; i < (int)T.size(); i += 2) Q[i >> 1] = T[i];
} else {
for (int i = 0; i < (int)S.size(); i += 2) P[i >> 1] = S[i];
for (int i = 0; i < (int)T.size(); i += 2) Q[i >> 1] = T[i];
}
k >>= 1;
}
return ret + P[0];
} else {
int N = 1;
while (N < (int)Q.size()) N <<= 1;
P.resize(2 * N);
Q.resize(2 * N);
P.ntt();
Q.ntt();
vector<mint> S(2 * N), T(2 * N);
vector<int> btr(N);
for (int i = 0, logn = __builtin_ctz(N); i < (1 << logn); i++) {
btr[i] = (btr[i >> 1] >> 1) + ((i & 1) << (logn - 1));
}
mint dw = mint(FormalPowerSeries<mint>::ntt_pr())
.inverse()
.pow((mint::get_mod() - 1) / (2 * N));
while (k) {
mint inv2 = mint(2).inverse();
// even degree of Q(x)Q(-x)
T.resize(N);
for (int i = 0; i < N; i++)
T[i] = Q[(i << 1) | 0] * Q[(i << 1) | 1];
S.resize(N);
if (k & 1) {
// odd degree of P(x)Q(-x)
for (auto& i : btr) {
S[i] = (P[(i << 1) | 0] * Q[(i << 1) | 1] -
P[(i << 1) | 1] * Q[(i << 1) | 0]) *
inv2;
inv2 *= dw;
}
} else {
// even degree of P(x)Q(-x)
for (int i = 0; i < N; i++) {
S[i] = (P[(i << 1) | 0] * Q[(i << 1) | 1] +
P[(i << 1) | 1] * Q[(i << 1) | 0]) *
inv2;
}
}
swap(P, S);
swap(Q, T);
k >>= 1;
if (k < N) break;
P.ntt_doubling();
Q.ntt_doubling();
}
P.intt();
Q.intt();
return ret + (P * (Q.inv()))[k];
}
}
template <typename mint>
mint kitamasa(long long N, FormalPowerSeries<mint> Q,
FormalPowerSeries<mint> a) {
assert(!Q.empty() && Q[0] != 0);
if (N < (int)a.size()) return a[N];
assert((int)a.size() >= int(Q.size()) - 1);
auto P = a.pre((int)Q.size() - 1) * Q;
P.resize(Q.size() - 1);
return LinearRecurrence<mint>(N, Q, P);
}
/**
* @brief 線形漸化式の高速計算
* @docs docs/fps/kitamasa.md
*/
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
__int128_t Power(__int128_t a, __int128_t b, __int128_t m) {
__int128_t p = a, Answer = 1;
for (int i = 0; i < 63; i++) {
__int128_t wari = (1LL << i);
if ((b / wari) % 2 == 1) {
Answer %= m;
Answer = (Answer * p) % m; // 「a の 2^i 乗」が掛けられるとき
}
p %= m;
p = (p * p) % m;
}
return Answer;
}
// ミラーラビン素数判定法(10**18以下の素数までなら判定可能)
bool is_prime(long long N) {
if (N <= 1) return false;
if (N == 2 || N == 3) return true;
if (N % 2 == 0) return false;
vector<long long> A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
long long s = 0, d = N - 1;
while (d % 2 == 0) {
++s;
d >>= 1;
}
for (auto a : A) {
if (a % N == 0) return true;
long long t, x = Power(a, d, N);
if (x != 1) {
for (t = 0; t < s; ++t) {
if (x == N - 1) break;
x = __int128_t(x) * x % N;
}
if (t == s) return false;
}
}
return true;
}
#endif