QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #483103 | #9120. Huge Segment Tree | ucup-team1134 | AC ✓ | 536ms | 64512kb | C++23 | 29.6kb | 2024-07-18 11:08:42 | 2024-07-18 11:08:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=2000005,INF=1<<30;
// sparse FPS 全部載せ
// from: https://gist.github.com/yosupo06/ddd51afb727600fd95d9d8ad6c3c80c9
// (based on AtCoder STL)
#include <algorithm>
#include <array>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
#include <utility>
namespace atcoder {
namespace internal {
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
struct barrett {
unsigned int _m;
unsigned long long im;
barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
unsigned int umod() const { return _m; }
unsigned int mul(unsigned int a, unsigned int b) const {
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned int v = (unsigned int)(z - x * _m);
if (_m <= v) v += _m;
return v;
}
};
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
for (long long a : {2, 7, 61}) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
static_modint(bool v) { _v = ((unsigned int)(v) % umod()); }
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); }
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt = 998244353;
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <type_traits>
#include <vector>
namespace atcoder {
namespace internal {
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a) {
static constexpr int g = internal::primitive_root<mint::mod()>;
int n = int(a.size());
int h = internal::ceil_pow2(n);
static bool first = true;
static mint sum_e[30]; // sum_e[i] = ies[0] * ... * ies[i - 1] * es[i]
if (first) {
first = false;
mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1
int cnt2 = bsf(mint::mod() - 1);
mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_e[i] = es[i] * now;
now *= ies[i];
}
}
for (int ph = 1; ph <= h; ph++) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint now = 1;
for (int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * now;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
now *= sum_e[bsf(~(unsigned int)(s))];
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a) {
static constexpr int g = internal::primitive_root<mint::mod()>;
int n = int(a.size());
int h = internal::ceil_pow2(n);
static bool first = true;
static mint sum_ie[30]; // sum_ie[i] = es[0] * ... * es[i - 1] * ies[i]
if (first) {
first = false;
mint es[30], ies[30]; // es[i]^(2^(2+i)) == 1
int cnt2 = bsf(mint::mod() - 1);
mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_ie[i] = ies[i] * now;
now *= es[i];
}
}
for (int ph = h; ph >= 1; ph--) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint inow = 1;
for (int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)(mint::mod() + l.val() - r.val()) *
inow.val();
}
inow *= sum_ie[bsf(~(unsigned int)(s))];
}
}
}
} // namespace internal
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (std::min(n, m) <= 60) {
if (n < m) {
std::swap(n, m);
std::swap(a, b);
}
std::vector<mint> ans(n + m - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i + j] += a[i] * b[j];
}
}
return ans;
}
int z = 1 << internal::ceil_pow2(n + m - 1);
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for (int i = 0; i < z; i++) {
a[i] *= b[i];
}
internal::butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
template <unsigned int mod = 998244353,
class T,
std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
using mint = static_modint<mod>;
std::vector<mint> a2(n), b2(m);
for (int i = 0; i < n; i++) {
a2[i] = mint(a[i]);
}
for (int i = 0; i < m; i++) {
b2[i] = mint(b[i]);
}
auto c2 = convolution(move(a2), move(b2));
std::vector<T> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c[i] = c2[i].val();
}
return c;
}
std::vector<long long> convolution_ll(const std::vector<long long>& a,
const std::vector<long long>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
static constexpr unsigned long long MOD1 = 754974721; // 2^24
static constexpr unsigned long long MOD2 = 167772161; // 2^25
static constexpr unsigned long long MOD3 = 469762049; // 2^26
static constexpr unsigned long long M2M3 = MOD2 * MOD3;
static constexpr unsigned long long M1M3 = MOD1 * MOD3;
static constexpr unsigned long long M1M2 = MOD1 * MOD2;
static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
static constexpr unsigned long long i1 =
internal::inv_gcd(MOD2 * MOD3, MOD1).second;
static constexpr unsigned long long i2 =
internal::inv_gcd(MOD1 * MOD3, MOD2).second;
static constexpr unsigned long long i3 =
internal::inv_gcd(MOD1 * MOD2, MOD3).second;
auto c1 = convolution<MOD1>(a, b);
auto c2 = convolution<MOD2>(a, b);
auto c3 = convolution<MOD3>(a, b);
std::vector<long long> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
unsigned long long x = 0;
x += (c1[i] * i1) % MOD1 * M2M3;
x += (c2[i] * i2) % MOD2 * M1M3;
x += (c3[i] * i3) % MOD3 * M1M2;
long long diff =
c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
if (diff < 0) diff += MOD1;
static constexpr unsigned long long offset[5] = {
0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
x -= offset[diff % 5];
c[i] = x;
}
return c;
}
} // namespace atcoder
using mint=atcoder::modint998244353;
// sparse fps
// F first increasing
// F second not-zero
// を仮定
mint inv[MAX],fac[MAX],finv[MAX];
void make(){
fac[0]=fac[1]=1;
finv[0]=finv[1]=1;
inv[1]=1;
for(int i=2;i<MAX;i++){
inv[i]=-inv[mod%i]*(mod/i);
fac[i]=fac[i-1]*i;
finv[i]=finv[i-1]*inv[i];
}
}
mint comb(ll a,ll b){
if(a<b) return 0;
return fac[a]*finv[b]*finv[a-b];
}
mint perm(ll a,ll b){
if(a<b) return 0;
return fac[a]*finv[a-b];
}
vector<mint> bibun(vector<mint> F,int deg){
vector<mint> res(deg+1);
for(int i=1;i<si(F)&&i-1<=deg;i++){
res[i-1]=F[i]*i;
}
return res;
}
vector<mint> sekibun(vector<mint> F,int deg){
vector<mint> res(deg+1);
for(int i=0;i<min(si(F),deg);i++){
res[i+1]=F[i]*inv[i+1];
}
return res;
}
vector<pair<ll,mint>> bibun_sparse(vector<pair<ll,mint>> F){
vector<pair<ll,mint>> FF;
for(int i=0;i<si(F);i++){
if(F[i].fi>0){
FF.push_back(mp(F[i].fi-1,F[i].se*F[i].fi));
}
}
return FF;
}
vector<pair<ll,mint>> sekibun_sparse(vector<pair<ll,mint>> F){
vector<pair<ll,mint>> FF;
for(int i=0;i<si(F);i++){
FF.push_back(mp(F[i].fi+1,F[i].se/(F[i].fi+1)));
}
return FF;
}
vector<mint> inv_sparse(vector<pair<ll,mint>> F,int deg){
assert(si(F)>=1);
assert(F[0].fi==0);
assert(F[0].se!=0);
mint f0inv=F[0].se.inv();
vector<mint> G(deg+1);
G[0]=f0inv;
for(int k=1;k<=deg;k++){
for(auto [i,pa]:F){
if(1<=i&&i<=k) G[k]-=pa*G[k-i];
}
G[k]*=f0inv;
}
return G;
}
vector<mint> log_sparse(vector<pair<ll,mint>> F,int deg){
assert(si(F)>=1);
assert(F[0].fi==0);
assert(F[0].se==1);
mint f0inv=F[0].se.inv();
vector<pair<ll,mint>> FF=bibun_sparse(F);
vector<mint> waru=inv_sparse(F,deg);
vector<mint> G(deg+1);
for(auto [i,pa]:FF){
for(int j=0;j<=deg;j++){
if(i+j<=deg) G[i+j]+=pa*waru[j];
}
}
G=sekibun(G,deg);
return G;
}
// F0. fi = 0, F0. se = 1
vector<mint> exp_sparse(vector<pair<ll,mint>> F,int deg){
if(si(F)){
assert(F[0].fi>0);
}
vector<pair<ll,mint>> FF=bibun_sparse(F);
vector<mint> G(deg+1);
G[0]=1;
for(int k=1;k<=deg;k++){
for(auto [i,pa]:FF){
if(i<=k-1) G[k]+=pa*G[k-1-i];
}
G[k]*=inv[k];
}
return G;
}
// F0. fi > 0
vector<mint> pow_sparse(vector<pair<ll,mint>> F,int deg,ll K){
if(K==0){
vector<mint> res(deg+1);
res[0]=1;
return res;
}
if(si(F)==0){
vector<mint> res(deg+1);
return res;
}
if(F[0].fi>1000000000LL/K){
vector<mint> res(deg+1);
return res;
}
if(F[0].fi*K>deg){
vector<mint> res(deg+1);
return res;
}
ll geta=F[0].fi;
for(int i=0;i<si(F);i++){
F[i].fi-=geta;
}
vector<pair<ll,mint>> FF;
for(int i=0;i<si(F);i++){
if(F[i].fi>0){
FF.push_back(mp(F[i].fi-1,F[i].se*F[i].fi));
}
}
vector<mint> G(deg+1);
G[geta*K]=F[0].se.pow(K);
mint f0inv=F[0].se.inv();
for(int k=1;k<=deg-geta*K;k++){
for(auto [i,pa]:FF){
if(i<k) G[k+geta*K]+=pa*G[k+geta*K-1-i]*K;
}
for(auto [i,pa]:F){
if(1<=i&&i<=k) G[k+geta*K]-=pa*(k-i)*G[k+geta*K-i];
}
G[k+geta*K]*=f0inv;
G[k+geta*K]*=inv[k];
}
return G;
}
// make() 呼ばないと sekibun,exp,pow でバグる
// MAX=2*deg ぐらい必要な気がする
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
make();
mint r2=mint(2).inv();
ll K;cin>>K;
vector<mint> res(3*K);
{
vector<pair<ll,mint>> S,T;
T.push_back(mp(0,r2));
T.push_back(mp(1,-1));
T.push_back(mp(2,-r2));
auto TT=inv_sparse(T,2*K);
S.push_back(mp(0,r2));
S.push_back(mp(1,1));
S.push_back(mp(2,r2));
auto SS=pow_sparse(S,2*K,K);
//vector<mint> S=poww({mint(2).inv(),1,mint(2).inv()},2*K,K);
for(int i=0;i<si(SS);i++) SS[i]*=-1;
SS[0]++;
auto U=atcoder::convolution(SS,TT);
for(int i=0;i<=2*K;i++){
res[i]+=mint(2).pow(K-1)*U[i];
}
}
{
/*
vector<mint> T={mint(2).inv(),-(mint(2).inv())};
T=invv(T,2*K);
vector<mint> S=poww({mint(2).inv(),mint(2).inv()},2*K,K);
for(int i=0;i<si(S);i++) S[i]*=-1;
S[0]++;
*/
vector<pair<ll,mint>> S,T;
T.push_back(mp(0,r2));
T.push_back(mp(1,-r2));
auto TT=inv_sparse(T,2*K);
S.push_back(mp(0,r2));
S.push_back(mp(1,r2));
auto SS=pow_sparse(S,2*K,K);
for(int i=0;i<si(SS);i++) SS[i]*=-1;
SS[0]++;
auto U=atcoder::convolution(SS,TT);
U=atcoder::convolution(U,{-1,1});
for(int i=0;i<=2*K;i++){
res[i]+=mint(2).pow(K)*U[i];
}
}
for(int k=0;k<K;k++){
res[1]-=mint(2).pow(K-k-1);
}
res[1]=mint(2).pow(K+1)-1;
for(int i=1;i<=2*K-2;i++) cout<<res[i].val()<<" ";
cout<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 14ms
memory: 27056kb
input:
2
output:
7 3
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 13ms
memory: 27028kb
input:
3
output:
15 14 6 1
result:
ok 4 tokens
Test #3:
score: 0
Accepted
time: 12ms
memory: 27092kb
input:
4
output:
31 43 36 19 6 1
result:
ok 6 tokens
Test #4:
score: 0
Accepted
time: 10ms
memory: 27064kb
input:
5
output:
63 110 132 114 70 30 8 1
result:
ok 8 tokens
Test #5:
score: 0
Accepted
time: 13ms
memory: 27024kb
input:
6
output:
127 255 384 448 400 272 136 47 10 1
result:
ok 10 tokens
Test #6:
score: 0
Accepted
time: 13ms
memory: 27332kb
input:
7
output:
255 558 978 1401 1610 1478 1066 589 240 68 12 1
result:
ok 12 tokens
Test #7:
score: 0
Accepted
time: 13ms
memory: 27320kb
input:
8
output:
511 1179 2292 3803 5250 5987 5576 4183 2482 1137 388 93 14 1
result:
ok 14 tokens
Test #8:
score: 0
Accepted
time: 14ms
memory: 27092kb
input:
9
output:
1023 2438 5088 9398 14896 20038 22632 21250 16406 10282 5144 2006 588 122 16 1
result:
ok 16 tokens
Test #9:
score: 0
Accepted
time: 17ms
memory: 27036kb
input:
10
output:
2047 4975 10896 21772 38360 58724 77184 86312 81448 64324 42112 22576 9744 3304 848 155 18 1
result:
ok 18 tokens
Test #10:
score: 0
Accepted
time: 14ms
memory: 27088kb
input:
11
output:
4095 10070 22782 48209 92140 156292 232068 298744 330926 313422 252186 171122 97008 45368 17200 5155 1176 192 20 1
result:
ok 20 tokens
Test #11:
score: 0
Accepted
time: 536ms
memory: 64332kb
input:
500000
output:
390220183 534638705 182393715 303662724 176884209 76063846 314206329 970463075 138271132 869076105 902568877 121426660 599330372 720576343 535733058 609095360 499854676 427738345 789967637 850801793 767689169 103101879 573005863 597231280 725469375 299015007 178535851 966708332 305629 940093777 7830...
result:
ok 999998 tokens
Test #12:
score: 0
Accepted
time: 115ms
memory: 34068kb
input:
72787
output:
863191949 852718765 363831665 964981186 487891193 263854743 37522806 18985671 265243835 698211861 413341848 452649596 684165069 41891590 781946347 633808644 213891845 90859042 654886506 681500079 853399752 536402628 160278411 189221861 144879826 449123001 395247186 477700669 245829076 740028721 3991...
result:
ok 145572 tokens
Test #13:
score: 0
Accepted
time: 47ms
memory: 28916kb
input:
29621
output:
625188972 186328126 837166229 677006047 662339899 556164288 627678499 464879587 574719635 860749906 37224574 952205162 612486418 67731480 127518779 222659320 311864904 739493528 441208728 656349279 675863661 193365665 871786422 429030382 542544944 65332274 279132780 886986640 23673291 260179258 1458...
result:
ok 59240 tokens
Test #14:
score: 0
Accepted
time: 423ms
memory: 55568kb
input:
287834
output:
839249597 106353691 541743754 176289649 331709790 90695814 581166563 660013633 12148749 777570497 239549256 50822832 928845641 783688014 527134794 967565837 8829067 728890387 532021836 723133136 271356603 442733913 109610442 872231778 997519892 627636901 942495046 612005045 480787271 380535891 31598...
result:
ok 575666 tokens
Test #15:
score: 0
Accepted
time: 480ms
memory: 58924kb
input:
372458
output:
238073678 125575487 257781224 432208434 926232022 985032784 972531646 156874450 242230869 958239072 623209641 963804956 760997596 492384034 248852029 480721426 727545366 871518883 526580215 340703419 119254798 894452847 503218079 466661994 21196998 64609258 607451189 866020376 472431142 833623174 95...
result:
ok 744914 tokens
Test #16:
score: 0
Accepted
time: 458ms
memory: 57024kb
input:
326174
output:
182767154 379158505 976650370 950752234 730142912 199366602 217176449 58415818 942059311 29041812 600728528 238722381 35842882 619426938 166582941 887411034 365366704 226747213 653768421 675658473 198607105 971515601 49241364 300610682 741576498 580333820 788122734 812899883 506754294 906735361 8477...
result:
ok 652346 tokens
Test #17:
score: 0
Accepted
time: 466ms
memory: 60836kb
input:
414785
output:
119371452 447324155 812098442 674259707 906095700 995739643 507821850 144836991 944844465 417859866 526136325 446179637 841143258 71594396 600687837 115917880 869472132 733304409 785178785 942797825 461532099 569481220 498200557 562246854 231360418 806781417 603555993 817444062 8765767 415391941 188...
result:
ok 829568 tokens
Test #18:
score: 0
Accepted
time: 68ms
memory: 30728kb
input:
52410
output:
109025791 520279794 997868526 544815757 1210333 262602454 444694081 215482612 359518123 630972106 469202475 93255040 356550496 552798085 978002390 758808807 872405738 26538225 591804454 180245449 487598812 486435998 100463040 636978431 131160375 54547501 21577758 600993423 54379208 278755072 3851668...
result:
ok 104818 tokens
Test #19:
score: 0
Accepted
time: 414ms
memory: 54660kb
input:
266488
output:
670591955 536664499 834582667 435202901 981715449 216606476 24885754 288060317 473842053 728197980 859018006 359189535 188879878 589394421 415307716 612098332 697672094 255330112 873094951 829240529 612715926 251238400 811393752 657428602 471660768 508314629 890321558 248471292 52873644 528909339 36...
result:
ok 532974 tokens
Test #20:
score: 0
Accepted
time: 264ms
memory: 44976kb
input:
235412
output:
838376130 82261816 749813798 853852768 548463514 590159263 767906723 873538508 681808483 793716931 81414518 387819437 489838184 649414809 971267048 518919507 299233671 402683441 670109161 673246099 315748962 982292160 524024775 990312514 930875705 394644470 79309906 651862394 296416662 949936814 511...
result:
ok 470822 tokens
Test #21:
score: 0
Accepted
time: 447ms
memory: 57252kb
input:
335028
output:
412572542 90575816 592590793 134956941 681546461 84123901 23797401 287575357 580630562 822219941 496015371 798714568 996561274 228437956 38964111 210338108 447304705 455001788 541599590 15999929 531678296 86106708 417035208 77019361 258493500 3295255 609295926 388289340 12082287 479955282 13536114 5...
result:
ok 670054 tokens
Test #22:
score: 0
Accepted
time: 533ms
memory: 63968kb
input:
490193
output:
89108812 9400903 759083927 482137918 881472778 819325246 469847190 224397125 941016878 318853318 823063910 192963094 253539854 195834928 305679610 177655853 744021959 486473727 952943524 80929181 726898580 419500987 86904978 500273473 864375683 752394278 447105311 649043680 568500692 716331790 79426...
result:
ok 980384 tokens
Test #23:
score: 0
Accepted
time: 531ms
memory: 64168kb
input:
494427
output:
224396630 171699844 874970651 366738496 188097388 20105024 923005591 475213547 862579354 219327984 402729610 343802472 824016768 274735056 606982614 720737421 379273500 527635893 326566225 588809571 892479263 956818966 119334763 921549067 728518606 341094293 734579914 96978341 54880988 441706555 375...
result:
ok 988852 tokens
Test #24:
score: 0
Accepted
time: 525ms
memory: 64352kb
input:
495456
output:
176309560 31132799 871206936 191727597 372664218 912078745 128667682 749015357 783582110 969205654 792240671 185634038 963924594 739384852 286035580 546230295 777033259 473035706 331715612 919733935 140740960 188303720 108317267 957369642 570466063 215525809 161735173 289750332 41787886 592639789 24...
result:
ok 990910 tokens
Test #25:
score: 0
Accepted
time: 532ms
memory: 64512kb
input:
499498
output:
10762491 87744479 29345176 330762125 67139471 859322674 517319159 444257903 287766504 323230886 614147692 179153449 789116746 632670050 42290946 845385229 648164696 260416611 791349068 162962424 446055973 201137312 796950696 787484329 797523547 634752612 675290933 712512594 448869911 573190874 93885...
result:
ok 998994 tokens
Test #26:
score: 0
Accepted
time: 529ms
memory: 64352kb
input:
493812
output:
613558532 754129691 624537960 491192546 52587972 335888580 918154485 412643191 632432095 756789608 652622556 498719566 684849283 923391920 735537543 543746954 46908287 213544787 692082087 977892286 329586609 673904401 701415241 768595797 918191698 628376968 628786912 839407278 263562545 942236399 70...
result:
ok 987622 tokens
Extra Test:
score: 0
Extra Test Passed