#define SKIP_RUNTIME_CHECKS // Verify: https://yukicoder.me/problems/no/2 // Library: Math/Zeta_Mebius.cpp // SPDX-License-Identifier: CC0-1.0 // 参考: https://nyaannyaan.github.io/library/set-function/zeta-mobius-transform.hpp.html // 参考: https://nyaannyaan.github.io/library/multiplicative-function/divisor-multiple-transform.hpp.html // Original Source: https://nyaannyaan.github.io/library/set-function/and-convolution.hpp.html // Original Source: https://nyaannyaan.github.io/library/set-function/or-convolution.hpp.html // ドキュメント: https://github.com/reinsirk/sirkit-cpp-library/blob/main/Document/zeta_mobius.md // // API一覧 // [集合のゼータ/メビウス変換] // 集合4変換: 空配列または長さn=2^kを直接更新、O(1+n log(n+1))時間・O(1)追加領域。 // superset_zeta_transform(f): f[S]を上位集合の総和へ更新、Tの+=が必要。 // superset_mobius_transform(f): 上位集合ゼータ変換の逆、Tの-=が必要。 // subset_zeta_transform(f): f[S]を部分集合の総和へ更新、Tの+=が必要。 // subset_mobius_transform(f): 部分集合ゼータ変換の逆、Tの-=が必要。 // Tはbool以外の加法型。符号付き整数の全途中結果は型の範囲内、符号なしは型の幅の剰余。値演算送出時は部分更新。 // // [AND/OR畳み込み] // bitwise_and_convolution(f,g): h[k]=sum_{i&j=k}f[i]g[j]を返す。同長の空配列または長さn=2^k。 // bitwise_or_convolution(f,g): h[k]=sum_{i|j=k}f[i]g[j]を返す。同長の空配列または長さn=2^k。 // bitwise_and_square(f)/bitwise_or_square(f): 同じ式のg=fを返す。入力1本、変換2回(通常の畳み込みは3回)。 // 各APIはO(1+n log(n+1))時間・O(n+1)領域。値渡しのためlvalue入力は保持、rvalueは領域を移譲できる。 // Tはbool以外の環型で+=/-=/*=が必要。符号付き整数の全途中結果は型の範囲内、符号なしは型の幅の剰余。 // // [IntegerSieve] // IntegerSieve(maxn): maxn>=0の最小素因数表・昇順素数列をO(maxn)時間・領域で作る。0,1の最小素因数は0。 // least_prime_factor[x]は最小素因数、prime_listは昇順素数列。表は書き換えず利用する。 // コピーは独立、コピー代入は強保証。ムーブ元は空となりmax_value()=-1。 // swap(other): 表と素数列をO(1)で交換する。 // max_value(): 表の上限を返す。is_prime(x): 0<=x<=max_value()の素数判定をO(1)で返す。 // prime_factorization(x): 1<=x<=max_value()^2の素因数と指数のmapを返す。x=1は空の表でも許す。 // enumerate_divisors(x), sorted_divisors(x): prime_factorizationと同じ前提で全約数を返す。後者だけ昇順。 // divisor_totients(x): prime_factorizationと同じ前提で各約数dからphi(d)へのmapを返す。 // mobius_table(): O(maxn)でmu表を返す。mu[0]=0,mu[1]=1。 // totient_table(): O(maxn)でphi表を返す。phi[0]=0,phi[1]=1。 // power_table(k,nmax): 0<=nmax<=max_value(),k>=0でn^kの表。0^0=1。 // べき乗表はO(nmax+pi(nmax)log(k+1))時間・O(nmax)領域。公開配列を変更せず使う。 // // [約数/倍数のゼータ/メビウス変換] // 正の添字の4変換。f[0]は不変、空配列も可。時間O(n log log n)。 // multiple_zeta_transform(f): f[d]=sum_{d|k} f[k]へ更新する。 // multiple_mobius_transform(f): 倍数ゼータ変換を元に戻す。 // divisor_zeta_transform(f): f[k]=sum_{d|k} f[d]へ更新する。 // divisor_mobius_transform(f): 約数ゼータ変換を元に戻す。 // 各(f,sieve)版: sieve.max_value()>=f.size()-1の素数表を再利用し、追加領域O(1)。 // 各(f)版: 素数表も作る。f.size()-1<=INT_MAX、追加領域O(n)。 // // [GCD/LCM畳み込み] // gcd_convolution(f,g): h[k]=sum_{gcd(i,j)=k}f[i]g[j]。gcd(0,k)=k(gcd(0,0)=0)。 // lcm_convolution(f,g): h[k]=sum_{lcm(i,j)=k}f[i]g[j]。lcm(0,k)=0、結果k>=nは切り捨て。 // 両者は同じ長さnの入力(空も可)、O(1+n log log(n+2))時間・O(n+1)領域。値渡しでlvalue入力は保持。 // 各(f,g,sieve)版: sieve.max_value()>=n-1の素数表を再利用する。 // 各(f,g)版: 素数表も作る。n-1<=INT_MAX。T{}は零、環の加減乗算に対応(bool以外)。 // 符号付き整数の全途中結果はTの範囲内、符号なし整数は型の幅の剰余演算。 // // gcd_square(f,sieve)/gcd_square(f): gcd_convolution(f,f)と同じ結果を返す。空も可、値渡し入力1本・変換2回。 // 時間O(1+n log log(n+2))・領域O(n+1)。表あり版はmax_value()>=n-1、表なし版はn-1<=INT_MAX。 // // lcm_square(f,sieve)/lcm_square(f): lcm_convolution(f,f)と同じ結果を返す。空も可、値渡し入力1本・変換2回。 // 時間O(1+n log log(n+2))・領域O(n+1)。表あり版はmax_value()>=n-1、表なし版はn-1<=INT_MAX。 // // [疎な倍数変換] // m=f.size()、rは各keyの素因数を重複込みで数えた総数(以下の両API共通)。 // sparse_multiple_zeta_transform(f,sieve): 正で一意なkeyの全約数を含むfをkey昇順にし、各値を倍数和へ置換。key<=sieve.max_value()、Valは+=対応。O((m+r)log(m+1))時間、O(m+r)補助領域。 // sparse_multiple_mobius_transform(f,sieve): 正で一意なkeyの全約数を含むfをkey昇順にし、倍数和の逆変換を実行。key<=sieve.max_value()、Valは-=対応。O((m+r)log(m+1))時間、O(m+r)補助領域。 // SIRKIT_NAMESPACE_V1: 公開APIはsirkit、既存のgeoはsirkit::geo、内部部品はsirkit::detail。 #include #include #include #include #include #include #include #include #include #include #include #include #include #include // SIRKIT_NAMESPACE_OPEN_V1 namespace sirkit { #ifndef SIRKIT_SET_TRANSFORM_SCALAR_DETAIL_DEFINED #define SIRKIT_SET_TRANSFORM_SCALAR_DETAIL_DEFINED namespace /*SIRKIT_NS_REWRITE_V1:D:cmVpbnNpcms6OmRldGFpbA==*/detail/*SIRKIT_NS_REWRITE_END_V1*/ { #if defined(__GNUC__) && !defined(__clang__) template [[gnu::always_inline]] inline void set_transform_eight(T* out, T* in) { if constexpr (Subtract) out[0] -= in[0]; else out[0] += in[0]; if constexpr (Subtract) out[1] -= in[1]; else out[1] += in[1]; if constexpr (Subtract) out[2] -= in[2]; else out[2] += in[2]; if constexpr (Subtract) out[3] -= in[3]; else out[3] += in[3]; if constexpr (Subtract) out[4] -= in[4]; else out[4] += in[4]; if constexpr (Subtract) out[5] -= in[5]; else out[5] += in[5]; if constexpr (Subtract) out[6] -= in[6]; else out[6] += in[6]; if constexpr (Subtract) out[7] -= in[7]; else out[7] += in[7]; } #endif template inline void set_transform_scalar(std::vector& f) { const std::size_t n = f.size(); if (n >= 8) { for (std::size_t base = 0; base < n; base += 8) { auto add = [&](std::size_t a, std::size_t b) { if constexpr (Subtract) f[base + a] -= f[base + b]; else f[base + a] += f[base + b]; }; if constexpr (Subset) { add(1, 0); add(3, 2); add(5, 4); add(7, 6); add(2, 0); add(3, 1); add(6, 4); add(7, 5); add(4, 0); add(5, 1); add(6, 2); add(7, 3); } else { add(0, 1); add(2, 3); add(4, 5); add(6, 7); add(0, 2); add(1, 3); add(4, 6); add(5, 7); add(0, 4); add(1, 5); add(2, 6); add(3, 7); } } } std::size_t half = n >= 8 ? 8 : 1; #if defined(__GNUC__) && !defined(__clang__) if constexpr (Subset && std::is_trivially_copyable_v && sizeof(T) <= 8) { // 依存する段の順序を保って2段をまとめる。 for (; half >= 8 && half < n / 2; half *= 4) { for (std::size_t base = 0; base < n; base += half * 4) { auto* a = f.data() + base; auto* b = a + half; auto* c = b + half; auto* d = c + half; for (std::size_t j = 0; j < half; j += 8) { set_transform_eight(b+j,a+j); set_transform_eight(d+j,c+j); set_transform_eight(c+j,a+j); set_transform_eight(d+j,b+j); } } } } #endif for (; half < n; half *= 2) { for (std::size_t base = 0; base < n; base += half * 2) { #if defined(__GNUC__) && !defined(__clang__) // 小さな単純型は8要素ずつ展開し、GCCの自動ベクトル化を促す。 if constexpr (std::is_trivially_copyable_v && sizeof(T) <= 8) { auto* out = f.data() + base + (Subset ? half : 0); auto* in = f.data() + base + (Subset ? 0 : half); std::size_t j = 0; for (; half - j >= 8; j += 8) { if constexpr (Subtract) out[j] -= in[j]; else out[j] += in[j]; if constexpr (Subtract) out[j+1] -= in[j+1]; else out[j+1] += in[j+1]; if constexpr (Subtract) out[j+2] -= in[j+2]; else out[j+2] += in[j+2]; if constexpr (Subtract) out[j+3] -= in[j+3]; else out[j+3] += in[j+3]; if constexpr (Subtract) out[j+4] -= in[j+4]; else out[j+4] += in[j+4]; if constexpr (Subtract) out[j+5] -= in[j+5]; else out[j+5] += in[j+5]; if constexpr (Subtract) out[j+6] -= in[j+6]; else out[j+6] += in[j+6]; if constexpr (Subtract) out[j+7] -= in[j+7]; else out[j+7] += in[j+7]; } for (; j < half; ++j) { if constexpr (Subtract) out[j] -= in[j]; else out[j] += in[j]; } } else #endif { for (std::size_t j = 0; j < half; ++j) { auto& out = f[base + j + (Subset ? half : 0)]; auto& in = f[base + j + (Subset ? 0 : half)]; if constexpr (Subtract) out -= in; else out += in; } } } } } } #endif #ifndef SIRKIT_SET_TRANSFORM_SIMD_DETAIL_DEFINED #define SIRKIT_SET_TRANSFORM_SIMD_DETAIL_DEFINED #if !defined(SIRKIT_DISABLE_SIMD) && (defined(__GNUC__) || defined(__clang__)) && (defined(__i386__) || defined(__x86_64__)) namespace /*SIRKIT_NS_REWRITE_V1:D:cmVpbnNpcms6OmRldGFpbA==*/detail/*SIRKIT_NS_REWRITE_END_V1*/ { template [[gnu::always_inline]] inline void set_transform_small_stage(T* f, std::size_t n) { for (std::size_t base=0; base [[gnu::always_inline]] inline void set_transform_small(T* f,std::size_t n) { if(n>=2)set_transform_small_stage(f,n); if(n>=4)set_transform_small_stage(f,n); if(n>=8)set_transform_small_stage(f,n); if(n>=16)set_transform_small_stage(f,n); if(n>=32)set_transform_small_stage(f,n); } template [[gnu::target("avx2"),gnu::always_inline]] inline V set_transform_stage(V v, std::index_sequence) { const V swapped = __builtin_shufflevector(v, v, (I ^ Bit)...); const V mask{static_cast((static_cast(I & Bit) == Subset) ? static_cast(~U{0}) : U{0})...}; if constexpr (Subtract) v -= swapped & mask; else v += swapped & mask; if constexpr (Bit * 2 < sizeof(V) / sizeof(U)) return set_transform_stage(v, std::index_sequence{}); return v; } template [[gnu::target("avx2")]] void set_transform_simd(T* f, std::size_t n) { using U = std::make_unsigned_t; typedef U V __attribute__((vector_size(32))); constexpr std::size_t width = sizeof(V) / sizeof(T); for (std::size_t base = 0; base < n; base += width) { V v; std::memcpy(&v, f + base, sizeof(v)); v = set_transform_stage(v, std::make_index_sequence{}); std::memcpy(f + base, &v, sizeof(v)); } // 3段ずつレジスタ内で伝播し、未変更の端のベクトルは書き戻さない。 std::size_t half = width; for (; half < n / 4; half *= 8) { for (std::size_t base = 0; base < n; base += half * 8) { for (std::size_t j = 0; j < half; j += width) { V v0; std::memcpy(&v0, f + base + half * 0 + j, sizeof(V)); V v1; std::memcpy(&v1, f + base + half * 1 + j, sizeof(V)); V v2; std::memcpy(&v2, f + base + half * 2 + j, sizeof(V)); V v3; std::memcpy(&v3, f + base + half * 3 + j, sizeof(V)); V v4; std::memcpy(&v4, f + base + half * 4 + j, sizeof(V)); V v5; std::memcpy(&v5, f + base + half * 5 + j, sizeof(V)); V v6; std::memcpy(&v6, f + base + half * 6 + j, sizeof(V)); V v7; std::memcpy(&v7, f + base + half * 7 + j, sizeof(V)); if constexpr (Subset) { if constexpr (Subtract) v1 -= v0; else v1 += v0; if constexpr (Subtract) v3 -= v2; else v3 += v2; if constexpr (Subtract) v5 -= v4; else v5 += v4; if constexpr (Subtract) v7 -= v6; else v7 += v6; if constexpr (Subtract) v2 -= v0; else v2 += v0; if constexpr (Subtract) v3 -= v1; else v3 += v1; if constexpr (Subtract) v6 -= v4; else v6 += v4; if constexpr (Subtract) v7 -= v5; else v7 += v5; if constexpr (Subtract) v4 -= v0; else v4 += v0; if constexpr (Subtract) v5 -= v1; else v5 += v1; if constexpr (Subtract) v6 -= v2; else v6 += v2; if constexpr (Subtract) v7 -= v3; else v7 += v3; } if constexpr (!Subset) { if constexpr (Subtract) v0 -= v1; else v0 += v1; if constexpr (Subtract) v2 -= v3; else v2 += v3; if constexpr (Subtract) v4 -= v5; else v4 += v5; if constexpr (Subtract) v6 -= v7; else v6 += v7; if constexpr (Subtract) v0 -= v2; else v0 += v2; if constexpr (Subtract) v1 -= v3; else v1 += v3; if constexpr (Subtract) v4 -= v6; else v4 += v6; if constexpr (Subtract) v5 -= v7; else v5 += v7; if constexpr (Subtract) v0 -= v4; else v0 += v4; if constexpr (Subtract) v1 -= v5; else v1 += v5; if constexpr (Subtract) v2 -= v6; else v2 += v6; if constexpr (Subtract) v3 -= v7; else v3 += v7; } if constexpr (!Subset) std::memcpy(f + base + half * 0 + j, &v0, sizeof(V)); std::memcpy(f + base + half * 1 + j, &v1, sizeof(V)); std::memcpy(f + base + half * 2 + j, &v2, sizeof(V)); std::memcpy(f + base + half * 3 + j, &v3, sizeof(V)); std::memcpy(f + base + half * 4 + j, &v4, sizeof(V)); std::memcpy(f + base + half * 5 + j, &v5, sizeof(V)); std::memcpy(f + base + half * 6 + j, &v6, sizeof(V)); if constexpr (Subset) std::memcpy(f + base + half * 7 + j, &v7, sizeof(V)); } } } for (; half < n / 2; half *= 4) { for (std::size_t base = 0; base < n; base += half * 4) { for (std::size_t j = 0; j < half; j += width) { V v0; std::memcpy(&v0, f + base + half * 0 + j, sizeof(V)); V v1; std::memcpy(&v1, f + base + half * 1 + j, sizeof(V)); V v2; std::memcpy(&v2, f + base + half * 2 + j, sizeof(V)); V v3; std::memcpy(&v3, f + base + half * 3 + j, sizeof(V)); if constexpr (Subset) { if constexpr (Subtract) v1 -= v0; else v1 += v0; if constexpr (Subtract) v3 -= v2; else v3 += v2; if constexpr (Subtract) v2 -= v0; else v2 += v0; if constexpr (Subtract) v3 -= v1; else v3 += v1; } if constexpr (!Subset) { if constexpr (Subtract) v0 -= v1; else v0 += v1; if constexpr (Subtract) v2 -= v3; else v2 += v3; if constexpr (Subtract) v0 -= v2; else v0 += v2; if constexpr (Subtract) v1 -= v3; else v1 += v3; } if constexpr (!Subset) std::memcpy(f + base + half * 0 + j, &v0, sizeof(V)); std::memcpy(f + base + half * 1 + j, &v1, sizeof(V)); std::memcpy(f + base + half * 2 + j, &v2, sizeof(V)); if constexpr (Subset) std::memcpy(f + base + half * 3 + j, &v3, sizeof(V)); } } } for (; half < n; half *= 2) { for (std::size_t base = 0; base < n; base += half * 2) { T* out = f + base + (Subset ? half : 0); const T* in = f + base + (Subset ? 0 : half); for (std::size_t j = 0; j < half; j += width) { V a, b; std::memcpy(&a, out + j, sizeof(a)); std::memcpy(&b, in + j, sizeof(b)); if constexpr (Subtract) a -= b; else a += b; std::memcpy(out + j, &a, sizeof(a)); } } } } } #endif #endif #ifndef SIRKIT_SUPERSET_ZETA_TRANSFORM_DEFINED #define SIRKIT_SUPERSET_ZETA_TRANSFORM_DEFINED template void superset_zeta_transform(std::vector& f) { #ifndef SKIP_RUNTIME_CHECKS if (!f.empty() && !std::has_single_bit(f.size())) throw std::invalid_argument("superset_zeta_transform: length must be a power of two"); #endif #if !defined(SIRKIT_DISABLE_SIMD) && (defined(__GNUC__) || defined(__clang__)) && (defined(__i386__) || defined(__x86_64__)) if constexpr (std::is_integral_v && !std::is_same_v && sizeof(T)<=8) { if (f.size()>=8) { if(f.size()==8){f[0]+=f[1];f[2]+=f[3];f[4]+=f[5];f[6]+=f[7];f[0]+=f[2];f[1]+=f[3];f[4]+=f[6];f[5]+=f[7];f[0]+=f[4];f[1]+=f[5];f[2]+=f[6];f[3]+=f[7];return;} if (f.size()<64) { switch(f.size()) { case 16:/*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_small(f.data(),16);return; case 32:/*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_small(f.data(),32);return; default:return; } } if (__builtin_cpu_supports("avx2")) { /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_simd(f.data(), f.size()); return; } } } #endif /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_scalar(f); } #endif #ifndef SIRKIT_SUPERSET_MOBIUS_TRANSFORM_DEFINED #define SIRKIT_SUPERSET_MOBIUS_TRANSFORM_DEFINED template void superset_mobius_transform(std::vector& f) { #ifndef SKIP_RUNTIME_CHECKS if (!f.empty() && !std::has_single_bit(f.size())) throw std::invalid_argument("superset_mobius_transform: length must be a power of two"); #endif #if !defined(SIRKIT_DISABLE_SIMD) && (defined(__GNUC__) || defined(__clang__)) && (defined(__i386__) || defined(__x86_64__)) if constexpr (std::is_integral_v && !std::is_same_v && sizeof(T)<=8) { if (f.size()>=8) { if(f.size()==8){f[0]-=f[1];f[2]-=f[3];f[4]-=f[5];f[6]-=f[7];f[0]-=f[2];f[1]-=f[3];f[4]-=f[6];f[5]-=f[7];f[0]-=f[4];f[1]-=f[5];f[2]-=f[6];f[3]-=f[7];return;} if (f.size()<64) { switch(f.size()) { case 16:/*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_small(f.data(),16);return; case 32:/*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_small(f.data(),32);return; default:return; } } if (__builtin_cpu_supports("avx2")) { /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_simd(f.data(), f.size()); return; } } } #endif /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_scalar(f); } #endif #ifndef SIRKIT_SUBSET_ZETA_TRANSFORM_DEFINED #define SIRKIT_SUBSET_ZETA_TRANSFORM_DEFINED template void subset_zeta_transform(std::vector& f) { #ifndef SKIP_RUNTIME_CHECKS if (!f.empty() && !std::has_single_bit(f.size())) throw std::invalid_argument("subset_zeta_transform: length must be a power of two"); #endif #if !defined(SIRKIT_DISABLE_SIMD) && (defined(__GNUC__) || defined(__clang__)) && (defined(__i386__) || defined(__x86_64__)) if constexpr (std::is_integral_v && !std::is_same_v && sizeof(T)<=8) { if (f.size()>=8) { if(f.size()==8){f[1]+=f[0];f[3]+=f[2];f[5]+=f[4];f[7]+=f[6];f[2]+=f[0];f[3]+=f[1];f[6]+=f[4];f[7]+=f[5];f[4]+=f[0];f[5]+=f[1];f[6]+=f[2];f[7]+=f[3];return;} if (f.size()<64) { switch(f.size()) { case 16:/*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_small(f.data(),16);return; case 32:/*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_small(f.data(),32);return; default:return; } } if (__builtin_cpu_supports("avx2")) { /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_simd(f.data(), f.size()); return; } } } #endif /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_scalar(f); } #endif #ifndef SIRKIT_SUBSET_MOBIUS_TRANSFORM_DEFINED #define SIRKIT_SUBSET_MOBIUS_TRANSFORM_DEFINED template void subset_mobius_transform(std::vector& f) { #ifndef SKIP_RUNTIME_CHECKS if (!f.empty() && !std::has_single_bit(f.size())) throw std::invalid_argument("subset_mobius_transform: length must be a power of two"); #endif #if !defined(SIRKIT_DISABLE_SIMD) && (defined(__GNUC__) || defined(__clang__)) && (defined(__i386__) || defined(__x86_64__)) if constexpr (std::is_integral_v && !std::is_same_v && sizeof(T)<=8) { if (f.size()>=8) { if(f.size()==8){f[1]-=f[0];f[3]-=f[2];f[5]-=f[4];f[7]-=f[6];f[2]-=f[0];f[3]-=f[1];f[6]-=f[4];f[7]-=f[5];f[4]-=f[0];f[5]-=f[1];f[6]-=f[2];f[7]-=f[3];return;} if (f.size()<64) { switch(f.size()) { case 16:/*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_small(f.data(),16);return; case 32:/*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_small(f.data(),32);return; default:return; } } if (__builtin_cpu_supports("avx2")) { /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_simd(f.data(), f.size()); return; } } } #endif /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::set_transform_scalar(f); } #endif #ifndef SIRKIT_BITWISE_MULTIPLY_DETAIL_DEFINED #define SIRKIT_BITWISE_MULTIPLY_DETAIL_DEFINED namespace /*SIRKIT_NS_REWRITE_V1:D:cmVpbnNpcms6OmRldGFpbA==*/detail/*SIRKIT_NS_REWRITE_END_V1*/ { template inline void bitwise_multiply_assign(T& left, T& right) { if constexpr (std::is_unsigned_v && sizeof(T) < sizeof(unsigned int)) left = static_cast(static_cast(left) * static_cast(right)); else left *= right; } } #endif #ifndef SIRKIT_BITWISE_AND_CONVOLUTION_DEFINED #define SIRKIT_BITWISE_AND_CONVOLUTION_DEFINED template std::vector bitwise_and_convolution(std::vector f, std::vector g) { #ifndef SKIP_RUNTIME_CHECKS if (f.size() != g.size()) throw std::invalid_argument("bitwise_and_convolution: different lengths"); #endif superset_zeta_transform(f); superset_zeta_transform(g); for (std::size_t i = 0; i < f.size(); ++i) /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::bitwise_multiply_assign(f[i], g[i]); superset_mobius_transform(f); return f; } #endif #ifndef SIRKIT_BITWISE_OR_CONVOLUTION_DEFINED #define SIRKIT_BITWISE_OR_CONVOLUTION_DEFINED template std::vector bitwise_or_convolution(std::vector f, std::vector g) { #ifndef SKIP_RUNTIME_CHECKS if (f.size() != g.size()) throw std::invalid_argument("bitwise_or_convolution: different lengths"); #endif subset_zeta_transform(f); subset_zeta_transform(g); for (std::size_t i = 0; i < f.size(); ++i) /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::bitwise_multiply_assign(f[i], g[i]); subset_mobius_transform(f); return f; } #endif #ifndef SIRKIT_BITWISE_AND_SQUARE_DEFINED #define SIRKIT_BITWISE_AND_SQUARE_DEFINED template std::vector bitwise_and_square(std::vector f) { superset_zeta_transform(f); for (std::size_t i = 0; i < f.size(); ++i) /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::bitwise_multiply_assign(f[i], f[i]); superset_mobius_transform(f); return f; } #endif #ifndef SIRKIT_BITWISE_OR_SQUARE_DEFINED #define SIRKIT_BITWISE_OR_SQUARE_DEFINED template std::vector bitwise_or_square(std::vector f) { subset_zeta_transform(f); for (std::size_t i = 0; i < f.size(); ++i) /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::bitwise_multiply_assign(f[i], f[i]); subset_mobius_transform(f); return f; } #endif #ifndef SIRKIT_INTEGER_SIEVE_DEFINED #define SIRKIT_INTEGER_SIEVE_DEFINED struct IntegerSieve { std::vector least_prime_factor; std::vector prime_list; explicit IntegerSieve(int maxn) : least_prime_factor(table_size(maxn), 2) { const std::size_t limit = least_prime_factor.size(); least_prime_factor[0] = 0; if (limit > 1) least_prime_factor[1] = 0; if (limit > 2) prime_list.push_back(2); std::size_t i = 3; for (; i <= (limit - 1) / 3; i += 2) { if (least_prime_factor[i] == 2) { least_prime_factor[i] = static_cast(i); prime_list.push_back(static_cast(i)); } const int first = least_prime_factor[i]; for (std::size_t j = 1; j < prime_list.size(); ++j) { const int prime = prime_list[j]; const std::uint64_t next = static_cast(i) * static_cast(prime); if (next >= limit) break; least_prime_factor[static_cast(next)] = prime; if (prime == first) break; } } for (; i < limit; i += 2) { if (least_prime_factor[i] == 2) { least_prime_factor[i] = static_cast(i); prime_list.push_back(static_cast(i)); } } } IntegerSieve(const IntegerSieve&) = default; IntegerSieve& operator=(const IntegerSieve& other) { if (this != &other) { IntegerSieve copy(other); swap(copy); } return *this; } IntegerSieve(IntegerSieve&& other) noexcept : least_prime_factor(std::move(other.least_prime_factor)), prime_list(std::move(other.prime_list)) { other.least_prime_factor.clear(); other.prime_list.clear(); } IntegerSieve& operator=(IntegerSieve&& other) noexcept { if (this != &other) { least_prime_factor = std::move(other.least_prime_factor); prime_list = std::move(other.prime_list); other.least_prime_factor.clear(); other.prime_list.clear(); } return *this; } void swap(IntegerSieve& other) noexcept { least_prime_factor.swap(other.least_prime_factor); prime_list.swap(other.prime_list); } int max_value() const noexcept { return least_prime_factor.empty() ? -1 : static_cast(least_prime_factor.size() - 1); } template bool is_prime(Int x) const { #ifndef SKIP_RUNTIME_CHECKS if constexpr (std::signed_integral) { if (x < 0) throw std::out_of_range("IntegerSieve::is_prime: negative input"); } if (static_cast(x) >= least_prime_factor.size()) { throw std::out_of_range("IntegerSieve::is_prime: input outside table"); } #endif const std::uint64_t value = static_cast(x); return value >= 2 && static_cast(least_prime_factor[static_cast(value)]) == value; } template std::map prime_factorization(Int x) const { #ifndef SKIP_RUNTIME_CHECKS if (x < 1) throw std::invalid_argument("IntegerSieve::prime_factorization: input must be positive"); #endif std::uint64_t rest = static_cast(x); std::map result; if (rest == 1) return result; const int maximum = max_value(); #ifndef SKIP_RUNTIME_CHECKS if (maximum < 1 || rest > static_cast(maximum) * static_cast(maximum)) { throw std::out_of_range("IntegerSieve::prime_factorization: input exceeds table limit squared"); } #endif const std::uint64_t bound = static_cast(maximum); if (rest > bound) { for (const int prime : prime_list) { const std::uint64_t p = static_cast(prime); if (p * p > rest) break; if (rest % p == 0) { int exponent = 0; do { rest /= p; ++exponent; } while (rest % p == 0); result.emplace(static_cast(prime), exponent); if (rest <= bound) break; } } if (rest > bound) { result.emplace(static_cast(rest), 1); return result; } } while (rest > 1) { const int prime = least_prime_factor[static_cast(rest)]; int exponent = 0; do { rest /= static_cast(prime); ++exponent; } while (rest > 1 && least_prime_factor[static_cast(rest)] == prime); result.emplace(static_cast(prime), exponent); } return result; } template std::vector enumerate_divisors(Int x) const { const auto factors = prime_factorization(x); std::vector result{static_cast(1)}; for (const auto& [prime, exponent] : factors) { const std::size_t previous = result.size(); reserve_multiple(result, static_cast(exponent) + 1); std::uint64_t power = 1; for (int e = 1; e <= exponent; ++e) { power *= static_cast(prime); for (std::size_t i = 0; i < previous; ++i) { result.push_back(static_cast(static_cast(result[i]) * power)); } } } return result; } template std::vector sorted_divisors(Int x) const { auto result = enumerate_divisors(x); std::sort(result.begin(), result.end()); return result; } template std::map divisor_totients(Int x) const { const auto factors = prime_factorization(x); std::vector> values{{static_cast(1), static_cast(1)}}; for (const auto& [prime, exponent] : factors) { const std::size_t previous = values.size(); reserve_multiple(values, static_cast(exponent) + 1); const std::uint64_t p = static_cast(prime); std::uint64_t power = 1; std::uint64_t phi_power = p - 1; for (int e = 1; e <= exponent; ++e) { power *= p; for (std::size_t i = 0; i < previous; ++i) { values.emplace_back( static_cast(static_cast(values[i].first) * power), static_cast(static_cast(values[i].second) * phi_power)); } if (e < exponent) phi_power *= p; } } return std::map(values.begin(), values.end()); } std::vector mobius_table() const { std::vector result(least_prime_factor.size()); if (result.size() > 1) result[1] = 1; for (std::size_t i = 2; i < result.size(); ++i) { const int p = least_prime_factor[i]; const std::size_t quotient = i / static_cast(p); result[i] = least_prime_factor[quotient] == p ? 0 : -result[quotient]; } return result; } std::vector totient_table() const { std::vector result(least_prime_factor.size()); if (result.size() > 1) result[1] = 1; for (std::size_t i = 2; i < result.size(); ++i) { const int p = least_prime_factor[i]; const std::size_t quotient = i / static_cast(p); result[i] = result[quotient] * (least_prime_factor[quotient] == p ? p : p - 1); } return result; } template std::vector power_table(std::int64_t k, int nmax) const { #ifndef SKIP_RUNTIME_CHECKS if (k < 0) throw std::invalid_argument("IntegerSieve::power_table: negative exponent"); if (nmax < 0 || nmax > max_value()) { throw std::out_of_range("IntegerSieve::power_table: input outside table"); } #endif const std::size_t count = table_size(nmax); if (count > std::vector().max_size()) { throw std::length_error("IntegerSieve::power_table: table too large"); } if (k == 0) return std::vector(count, MODINT(1)); std::vector result(count); if (count > 0) result[0] = MODINT(0); if (count > 1) result[1] = MODINT(1); for (std::size_t i = 2; i < count; ++i) { const int p = least_prime_factor[i]; if (static_cast(p) == i) { result[i] = MODINT(p).pow(k); } else { result[i] = result[static_cast(p)] * result[i / static_cast(p)]; } } return result; } private: static std::size_t table_size(int maximum) { #ifndef SKIP_RUNTIME_CHECKS if (maximum < 0) throw std::invalid_argument("IntegerSieve: negative table limit"); #endif const std::uint64_t count = static_cast(maximum) + 1; if (count > std::vector().max_size()) { throw std::length_error("IntegerSieve: table too large"); } return static_cast(count); } template static void reserve_multiple(std::vector& values, std::size_t multiplier) { if (multiplier > values.max_size() / values.size()) { throw std::length_error("IntegerSieve: divisor table too large"); } values.reserve(values.size() * multiplier); } }; #endif #ifndef SIRKIT_INTEGER_TRANSFORM_DETAIL_DEFINED #define SIRKIT_INTEGER_TRANSFORM_DETAIL_DEFINED namespace /*SIRKIT_NS_REWRITE_V1:D:cmVpbnNpcms6OmRldGFpbA==*/detail/*SIRKIT_NS_REWRITE_END_V1*/ { struct IntegerTransform { // 素数pについて、指数を1段進める/戻す伝播を行う。 #if defined(__GNUC__) && !defined(__clang__) template static void propagate(std::vector& a, const PrimeRange& primes) { if constexpr (std::is_trivially_copyable_v && sizeof(T) <= 8) { if (a.size() >= 257) { propagate_expanded(a, primes); return; } } propagate_scalar(a, primes); } template static void propagate_expanded(std::vector& a, const PrimeRange& primes) { if (a.size() <= 2) return; const std::size_t upper = a.size() - 1; auto prime = primes.begin(); const auto end = primes.end(); for (; prime != end; ++prime) { const auto p = static_cast(*prime); if (p > upper / 2) break; const auto count = upper / p; if constexpr (ToMultiples != Subtract) { std::size_t from = 1, to = p; for (; count - from + 1 >= 8; from += 8, to += p * 8) { if constexpr (ToMultiples) a[to + p * 0] += a[from + 0]; else a[from + 0] -= a[to + p * 0]; if constexpr (ToMultiples) a[to + p * 1] += a[from + 1]; else a[from + 1] -= a[to + p * 1]; if constexpr (ToMultiples) a[to + p * 2] += a[from + 2]; else a[from + 2] -= a[to + p * 2]; if constexpr (ToMultiples) a[to + p * 3] += a[from + 3]; else a[from + 3] -= a[to + p * 3]; if constexpr (ToMultiples) a[to + p * 4] += a[from + 4]; else a[from + 4] -= a[to + p * 4]; if constexpr (ToMultiples) a[to + p * 5] += a[from + 5]; else a[from + 5] -= a[to + p * 5]; if constexpr (ToMultiples) a[to + p * 6] += a[from + 6]; else a[from + 6] -= a[to + p * 6]; if constexpr (ToMultiples) a[to + p * 7] += a[from + 7]; else a[from + 7] -= a[to + p * 7]; } for (; from <= count; ++from, to += p) { if constexpr (ToMultiples) a[to] += a[from]; else a[from] -= a[to]; } } else { std::size_t from = count, to = count * p; for (; from >= 8; from -= 8, to -= p * 8) { if constexpr (ToMultiples) a[to - p * 0] -= a[from - 0]; else a[from - 0] += a[to - p * 0]; if constexpr (ToMultiples) a[to - p * 1] -= a[from - 1]; else a[from - 1] += a[to - p * 1]; if constexpr (ToMultiples) a[to - p * 2] -= a[from - 2]; else a[from - 2] += a[to - p * 2]; if constexpr (ToMultiples) a[to - p * 3] -= a[from - 3]; else a[from - 3] += a[to - p * 3]; if constexpr (ToMultiples) a[to - p * 4] -= a[from - 4]; else a[from - 4] += a[to - p * 4]; if constexpr (ToMultiples) a[to - p * 5] -= a[from - 5]; else a[from - 5] += a[to - p * 5]; if constexpr (ToMultiples) a[to - p * 6] -= a[from - 6]; else a[from - 6] += a[to - p * 6]; if constexpr (ToMultiples) a[to - p * 7] -= a[from - 7]; else a[from - 7] += a[to - p * 7]; } for (; from; --from, to -= p) { if constexpr (ToMultiples) a[to] -= a[from]; else a[from] += a[to]; } } } for (; prime != end; ++prime) { const auto p = static_cast(*prime); if (p > upper) break; if constexpr (ToMultiples) { if constexpr (Subtract) a[p] -= a[1]; else a[p] += a[1]; } else { if constexpr (Subtract) a[1] -= a[p]; else a[1] += a[p]; } } } #endif template #if defined(__GNUC__) && !defined(__clang__) static void propagate_scalar(std::vector& a, const PrimeRange& primes) { #else static void propagate(std::vector& a, const PrimeRange& primes) { #endif if (a.size() <= 2) return; const std::size_t upper = a.size() - 1; auto prime = primes.begin(); const auto end = primes.end(); for (; prime != end; ++prime) { const auto p = static_cast(*prime); if (p > upper / 2) break; const auto count = upper / p; if constexpr (ToMultiples != Subtract) { for (std::size_t from = 1, to = p; from <= count; ++from, to += p) { if constexpr (ToMultiples) a[to] += a[from]; else a[from] -= a[to]; } } else { for (std::size_t from = count, to = count * p; from; --from, to -= p) { if constexpr (ToMultiples) a[to] -= a[from]; else a[from] += a[to]; } } } for (; prime != end; ++prime) { const auto p = static_cast(*prime); if (p > upper) break; if constexpr (ToMultiples) { if constexpr (Subtract) a[p] -= a[1]; else a[p] += a[1]; } else { if constexpr (Subtract) a[1] -= a[p]; else a[1] += a[p]; } } } // 小さい範囲は定数表を使い、素数表の確保と初期化を省く。 static std::span prime_view_for(std::size_t size, std::vector& storage) { static constexpr std::array small_primes{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127 }; if (size <= 128) { const auto end = std::lower_bound(small_primes.begin(), small_primes.end(), static_cast(size)); return {small_primes.data(), static_cast(end - small_primes.begin())}; } storage = primes_for(size); return storage; } static std::vector primes_for(std::size_t size) { if (size <= 2) return {}; if (size - 1 > static_cast(std::numeric_limits::max())) throw std::length_error("integer transform: maximum exceeds INT_MAX"); const auto upper = size - 1; std::vector marked(upper / 2 + 1); std::vector answer{2}; for (std::size_t p = 3; p <= upper; p += 2) { if (marked[p / 2]) continue; answer.push_back(static_cast(p)); if (p <= upper / p) for (std::size_t k = p * p / 2; k < marked.size(); k += p) marked[k] = 1; } return answer; } #ifndef SKIP_RUNTIME_CHECKS static void require_sieve(std::size_t size, const IntegerSieve& sieve) { if (size && (sieve.max_value() < 0 || size - 1 > static_cast(sieve.max_value()))) throw std::out_of_range("integer transform: sieve too small"); } static void require_same_size(std::size_t a, std::size_t b) { if (a != b) throw std::invalid_argument("integer convolution: different lengths"); } #endif }; } // namespace reinsirk::detail #endif #ifndef SIRKIT_MULTIPLE_ZETA_DEFINED #define SIRKIT_MULTIPLE_ZETA_DEFINED template void multiple_zeta_transform(std::vector& f, const IntegerSieve& sieve) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_sieve(f.size(), sieve); #endif /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(f, sieve.prime_list); } template void multiple_zeta_transform(std::vector& f) { std::vector storage; const auto primes = /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::prime_view_for(f.size(), storage); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(f, primes); } #endif #ifndef SIRKIT_MULTIPLE_MOEBIUS_DEFINED #define SIRKIT_MULTIPLE_MOEBIUS_DEFINED template void multiple_mobius_transform(std::vector& f, const IntegerSieve& sieve) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_sieve(f.size(), sieve); #endif /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(f, sieve.prime_list); } template void multiple_mobius_transform(std::vector& f) { std::vector storage; const auto primes = /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::prime_view_for(f.size(), storage); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(f, primes); } #endif #ifndef SIRKIT_DIVISOR_ZETA_DEFINED #define SIRKIT_DIVISOR_ZETA_DEFINED template void divisor_zeta_transform(std::vector& f, const IntegerSieve& sieve) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_sieve(f.size(), sieve); #endif /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(f, sieve.prime_list); } template void divisor_zeta_transform(std::vector& f) { std::vector storage; const auto primes = /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::prime_view_for(f.size(), storage); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(f, primes); } #endif #ifndef SIRKIT_DIVISOR_MOEBIUS_DEFINED #define SIRKIT_DIVISOR_MOEBIUS_DEFINED template void divisor_mobius_transform(std::vector& f, const IntegerSieve& sieve) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_sieve(f.size(), sieve); #endif /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(f, sieve.prime_list); } template void divisor_mobius_transform(std::vector& f) { std::vector storage; const auto primes = /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::prime_view_for(f.size(), storage); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(f, primes); } #endif #ifndef SIRKIT_INTEGER_CONVOLUTION_DETAIL_DEFINED #define SIRKIT_INTEGER_CONVOLUTION_DETAIL_DEFINED namespace /*SIRKIT_NS_REWRITE_V1:D:cmVpbnNpcms6OmRldGFpbA==*/detail/*SIRKIT_NS_REWRITE_END_V1*/ { struct IntegerConvolution { template static decltype(auto) product(const T& left, const T& right) { if constexpr (std::is_unsigned_v && sizeof(T) < sizeof(unsigned int)) return static_cast(static_cast(left) * static_cast(right)); else return left * right; } template static void multiply_assign(T& left, T& right) { if constexpr (std::is_unsigned_v && sizeof(T) < sizeof(unsigned int)) left = static_cast(static_cast(left) * static_cast(right)); else left *= right; } template static std::vector compute(std::vector a, std::vector b, const PrimeRange& primes) { if (a.empty()) return a; const T left_zero = a.front(), right_zero = b.front(); bool zero_terms_needed = true; if constexpr (std::equality_comparable) zero_terms_needed = left_zero != T{} || right_zero != T{}; if constexpr (Gcd) { std::vector mixed; if (zero_terms_needed) { mixed.resize(a.size()); for (std::size_t k = 1; k < a.size(); ++k) mixed[k] = product(left_zero, b[k]) + product(a[k], right_zero); } /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(a, primes); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(b, primes); for (std::size_t k = 0; k < a.size(); ++k) multiply_assign(a[k], b[k]); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(a, primes); if (zero_terms_needed) for (std::size_t k = 1; k < a.size(); ++k) a[k] += mixed[k]; } else { T at_zero = product(left_zero, right_zero); if (zero_terms_needed) { T left_sum{}, right_sum{}; for (std::size_t k = 1; k < a.size(); ++k) { left_sum += a[k]; right_sum += b[k]; } at_zero += product(left_zero, right_sum) + product(left_sum, right_zero); } /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(a, primes); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(b, primes); for (std::size_t k = 1; k < a.size(); ++k) multiply_assign(a[k], b[k]); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::propagate(a, primes); a.front() = at_zero; } return a; } template static std::vector square(std::vector a, const PrimeRange& primes) { if (a.empty()) return a; const T zero = a.front(); bool zero_terms_needed = true; if constexpr (std::equality_comparable) zero_terms_needed = zero != T{}; if constexpr (Gcd) { std::vector mixed; if (zero_terms_needed) { mixed.resize(a.size()); for (std::size_t k = 1; k < a.size(); ++k) mixed[k] = product(zero, a[k]) + product(a[k], zero); } IntegerTransform::propagate(a, primes); for (std::size_t k = 0; k < a.size(); ++k) multiply_assign(a[k], a[k]); IntegerTransform::propagate(a, primes); if (zero_terms_needed) for (std::size_t k = 1; k < a.size(); ++k) a[k] += mixed[k]; } else { T at_zero = product(zero, zero); if (zero_terms_needed) { T sum{}; for (std::size_t k = 1; k < a.size(); ++k) sum += a[k]; at_zero += product(zero, sum) + product(sum, zero); } IntegerTransform::propagate(a, primes); for (std::size_t k = 1; k < a.size(); ++k) multiply_assign(a[k], a[k]); IntegerTransform::propagate(a, primes); a.front() = at_zero; } return a; } }; } // namespace reinsirk::detail #endif #ifndef SIRKIT_GCDCONV_DEFINED #define SIRKIT_GCDCONV_DEFINED template std::vector gcd_convolution(std::vector f, std::vector g, const IntegerSieve& sieve) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_same_size(f.size(), g.size()); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_sieve(f.size(), sieve); #endif return /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerConvolution::compute(std::move(f), std::move(g), sieve.prime_list); } template std::vector gcd_convolution(std::vector f, std::vector g) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_same_size(f.size(), g.size()); #endif std::vector storage; const auto primes = /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::prime_view_for(f.size(), storage); return /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerConvolution::compute(std::move(f), std::move(g), primes); } #endif #ifndef SIRKIT_LCMCONV_DEFINED #define SIRKIT_LCMCONV_DEFINED template std::vector lcm_convolution(std::vector f, std::vector g, const IntegerSieve& sieve) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_same_size(f.size(), g.size()); /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_sieve(f.size(), sieve); #endif return /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerConvolution::compute(std::move(f), std::move(g), sieve.prime_list); } template std::vector lcm_convolution(std::vector f, std::vector g) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_same_size(f.size(), g.size()); #endif std::vector storage; const auto primes = /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::prime_view_for(f.size(), storage); return /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerConvolution::compute(std::move(f), std::move(g), primes); } #endif #ifndef SIRKIT_GCD_SQUARE_DEFINED #define SIRKIT_GCD_SQUARE_DEFINED template std::vector gcd_square(std::vector f, const IntegerSieve& sieve) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_sieve(f.size(), sieve); #endif return /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerConvolution::square(std::move(f), sieve.prime_list); } template std::vector gcd_square(std::vector f) { std::vector storage; const auto primes = /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::prime_view_for(f.size(), storage); return /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerConvolution::square(std::move(f), primes); } #endif #ifndef SIRKIT_LCM_SQUARE_DEFINED #define SIRKIT_LCM_SQUARE_DEFINED template std::vector lcm_square(std::vector f, const IntegerSieve& sieve) { #ifndef SKIP_RUNTIME_CHECKS /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::require_sieve(f.size(), sieve); #endif return /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerConvolution::square(std::move(f), sieve.prime_list); } template std::vector lcm_square(std::vector f) { std::vector storage; const auto primes = /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerTransform::prime_view_for(f.size(), storage); return /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::IntegerConvolution::square(std::move(f), primes); } #endif #ifndef SIRKIT_INTERNAL_SPARSE_INTEGER_TRANSFORM_DEFINED #define SIRKIT_INTERNAL_SPARSE_INTEGER_TRANSFORM_DEFINED namespace /*SIRKIT_NS_REWRITE_V1:D:cmVpbnNpcms6OmRldGFpbA==*/detail/*SIRKIT_NS_REWRITE_END_V1*/ { // 内部用。密な範囲は位置配列、疎な範囲は素数別の伝播列を使う。 template void sparse_integer_transform(std::vector>& f, const IntegerSieve& sieve) { if (f.empty()) return; // 1..mが順番に並ぶ場合は、添字を直接使い並べ替えと位置配列を省く。 const std::size_t dense_size = f.size(); if (f.front().first == Int{1} && static_cast(f.back().first) == dense_size) { bool consecutive = true; for (std::size_t i = 1; i + 1 < dense_size; ++i) { if (static_cast(f[i].first) != i + 1) { consecutive = false; break; } } if (consecutive) { #ifndef SKIP_RUNTIME_CHECKS if (sieve.max_value() < 0 || dense_size > static_cast(sieve.max_value())) throw std::out_of_range("sparse integer transform: key out of range"); #endif auto prime = sieve.prime_list.begin(); const auto end = sieve.prime_list.end(); for (; prime != end; ++prime) { const auto p = static_cast(*prime); if (p > dense_size / 2) break; const auto count = dense_size / p; if constexpr (Inverse) { std::size_t from = 1, to = p; #if defined(__GNUC__) && !defined(__clang__) if constexpr (std::is_trivially_copyable_v && sizeof(Val) <= 8) { for (; count - from + 1 >= 8; from += 8, to += p * 8) { f[from - 1].second -= f[to - 1].second; f[from].second -= f[to + p * 1 - 1].second; f[from + 1].second -= f[to + p * 2 - 1].second; f[from + 2].second -= f[to + p * 3 - 1].second; f[from + 3].second -= f[to + p * 4 - 1].second; f[from + 4].second -= f[to + p * 5 - 1].second; f[from + 5].second -= f[to + p * 6 - 1].second; f[from + 6].second -= f[to + p * 7 - 1].second; } } #endif for (; from <= count; ++from, to += p) f[from - 1].second -= f[to - 1].second; } else { std::size_t from = count, to = count * p; #if defined(__GNUC__) && !defined(__clang__) if constexpr (std::is_trivially_copyable_v && sizeof(Val) <= 8) { for (; from >= 8; from -= 8, to -= p * 8) { f[from - 1].second += f[to - 1].second; f[from - 2].second += f[to - p * 1 - 1].second; f[from - 3].second += f[to - p * 2 - 1].second; f[from - 4].second += f[to - p * 3 - 1].second; f[from - 5].second += f[to - p * 4 - 1].second; f[from - 6].second += f[to - p * 5 - 1].second; f[from - 7].second += f[to - p * 6 - 1].second; f[from - 8].second += f[to - p * 7 - 1].second; } } #endif for (; from; --from, to -= p) f[from - 1].second += f[to - 1].second; } } for (; prime != end; ++prime) { const auto p = static_cast(*prime); if (p > dense_size) break; if constexpr (Inverse) f[0].second -= f[p - 1].second; else f[0].second += f[p - 1].second; } return; } } const auto by_key = [](const auto& a, const auto& b) { return a.first < b.first; }; if (!std::is_sorted(f.begin(), f.end(), by_key)) std::sort(f.begin(), f.end(), by_key); #ifndef SKIP_RUNTIME_CHECKS if (sieve.max_value() < 0 || f.front().first <= 0 || static_cast(f.back().first) > static_cast(sieve.max_value())) { throw std::out_of_range("sparse integer transform: key out of range"); } #endif const std::size_t m = f.size(); const auto largest = static_cast(f.back().first); constexpr auto absent = std::numeric_limits::max(); auto propagate = [&](std::size_t src, std::size_t dst) { if constexpr (Inverse) f[dst].second -= f[src].second; else f[dst].second += f[src].second; }; // 範囲をmの4倍以下に制限し、値域に比例する記憶量を避ける。 if (largest <= std::numeric_limits::max() - 1 && (largest / m < 4 || (largest / m == 4 && largest % m == 0))) { const auto n = static_cast(largest); std::vector position; if (n >= position.max_size()) { throw std::length_error("sparse integer transform: position capacity"); } position.assign(n + 1, absent); for (std::size_t i = 0; i < m; ++i) { const auto key = static_cast(f[i].first); #ifndef SKIP_RUNTIME_CHECKS if (position[key] != absent) { throw std::invalid_argument("sparse integer transform: duplicate key"); } #endif position[key] = i; } for (const auto raw_prime : sieve.prime_list) { const auto p = static_cast(raw_prime); if (p > n) break; const auto limit = n / p; auto visit = [&](std::size_t q) { const auto src = position[q * p]; if (src == absent) return; const auto dst = position[q]; #ifndef SKIP_RUNTIME_CHECKS if (dst == absent) { throw std::invalid_argument("sparse integer transform: missing divisor"); } #endif propagate(src, dst); }; if constexpr (Inverse) { for (std::size_t q = 1; q <= limit; ++q) visit(q); } else { for (std::size_t q = limit; q != 0; --q) visit(q); } } return; } struct Transfer { std::size_t src, dst, next; }; std::vector head(m, absent); std::vector transfers; if (m <= transfers.max_size() / 4) transfers.reserve(m * 4); else transfers.reserve(m); // 最大8回だけ探索し、衝突が続けば二分探索へ戻す。 std::vector slots; if (m > slots.max_size() / 4) { throw std::length_error("sparse integer transform: lookup capacity"); } const auto slot_count = std::bit_ceil(m * 2); slots.assign(slot_count, absent); const auto mask = slot_count - 1; const auto hash_shift = std::numeric_limits::digits - std::bit_width(mask); auto hash_key = [&](std::uintmax_t key) { const auto h = static_cast(key) * UINT64_C(0x9e3779b97f4a7c15); return static_cast(h >> hash_shift); }; std::array small_position; small_position.fill(absent); for (std::size_t i = 0; i < m; ++i) { #ifndef SKIP_RUNTIME_CHECKS if (i != 0 && f[i - 1].first == f[i].first) { throw std::invalid_argument("sparse integer transform: duplicate key"); } #endif const auto key = static_cast(f[i].first); if (key < small_position.size()) small_position[static_cast(key)] = i; auto at = hash_key(key); for (unsigned probe = 0; probe != 8; ++probe) { if (slots[at] == absent) { slots[at] = i; break; } at = (at + 1) & mask; } } auto locate = [&](std::uintmax_t key) { if (key < small_position.size()) { const auto index = small_position[static_cast(key)]; #ifndef SKIP_RUNTIME_CHECKS if (index == absent) { throw std::invalid_argument("sparse integer transform: missing divisor"); } #endif return index; } auto at = hash_key(key); for (unsigned probe = 0; probe != 8; ++probe) { const auto index = slots[at]; if (index == absent) break; if (static_cast(f[index].first) == key) return index; at = (at + 1) & mask; } const auto it = std::lower_bound(f.begin(), f.end(), key, [](const auto& item, std::uintmax_t value) { return static_cast(item.first) < value; }); #ifndef SKIP_RUNTIME_CHECKS if (it == f.end() || static_cast(it->first) != key) { throw std::invalid_argument("sparse integer transform: missing divisor"); } #endif return static_cast(it - f.begin()); }; for (std::size_t step = 0; step < m; ++step) { // 先頭への連結でゼータは降順、メビウスは昇順に伝播する。 const auto i = Inverse ? m - 1 - step : step; using Factor = std::make_unsigned_t; const auto original = static_cast(f[i].first); auto remaining = original; while (remaining > 1) { const auto p = static_cast( sieve.least_prime_factor[static_cast(remaining)]); const auto prime_index = locate(p); const auto dst = locate(original / p); if (transfers.size() == transfers.max_size()) { throw std::length_error("sparse integer transform: transfer capacity"); } transfers.push_back({i, dst, head[prime_index]}); head[prime_index] = transfers.size() - 1; do remaining /= p; while (remaining > 1 && static_cast(sieve.least_prime_factor[static_cast(remaining)]) == p); } } for (const auto first : head) { for (auto at = first; at != absent; at = transfers[at].next) { const auto& transfer = transfers[at]; propagate(transfer.src, transfer.dst); } } } } // namespace reinsirk::detail #endif #ifndef SIRKIT_SPARSE_FAST_INTEGER_ZETA_DEFINED #define SIRKIT_SPARSE_FAST_INTEGER_ZETA_DEFINED template void sparse_multiple_zeta_transform(std::vector>& f, const IntegerSieve& sieve) { /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::sparse_integer_transform(f, sieve); } #endif #ifndef SIRKIT_SPARSE_FAST_INTEGER_MOEBIUS_DEFINED #define SIRKIT_SPARSE_FAST_INTEGER_MOEBIUS_DEFINED template void sparse_multiple_mobius_transform(std::vector>& f, const IntegerSieve& sieve) { /*SIRKIT_NS_REWRITE_V1:R:cmVpbnNpcms6OmRldGFpbA==*/::sirkit::detail/*SIRKIT_NS_REWRITE_END_V1*/::sparse_integer_transform(f, sieve); } #endif } // namespace sirkit // SIRKIT_NAMESPACE_CLOSE_V1 // SIRKIT_NAMESPACE_END_V1 namespace sirkit {} using namespace sirkit; // SPDX-License-Identifier: CC0-1.0 // Verify I/O: Verify/current/common/fast_io.hpp // SPDX-License-Identifier: CC0-1.0 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifndef SIRKIT_VERIFY_FAST_IO_DEFINED #define SIRKIT_VERIFY_FAST_IO_DEFINED // VerifyInput(file=stdin): 非所有のFILEから読む。別の入力方式と混用しない。 // >> 整数: 64bit以下の十進整数を読む。検査省略時は値域内の正しい入力を前提とする。 // >> char/string: 空白を飛ばし、1文字/空白までの文字列を読む。 // >> 浮動小数点: 十進文字列を変換する。通常のCロケールで使う。 // bool / !: 直前までの読み取りが成功しているか/失敗したかを返す。 class VerifyInput { static constexpr std::size_t buffer_size = 1 << 17; std::FILE* file_; std::array buffer_; std::size_t position_ = 0, size_ = 0; bool good_ = true; int peek() { if (position_ == size_) { size_ = std::fread(buffer_.data(), 1, buffer_size, file_); buffer_[size_] = 0; // 補充後の末尾は常に数字でない番兵。 position_ = 0; if (size_ == 0) return EOF; } return buffer_[position_]; } int skip_space() { int c; while ((c = peek()) != EOF && c <= ' ') ++position_; if (c == EOF) good_ = false; return c; } public: explicit VerifyInput(std::FILE* file = stdin) : file_(file) {} VerifyInput(const VerifyInput&) = delete; VerifyInput& operator=(const VerifyInput&) = delete; explicit operator bool() const noexcept { return good_; } bool operator!() const noexcept { return !good_; } template requires (std::is_integral_v && sizeof(T) <= sizeof(std::uint64_t) && !std::is_same_v) VerifyInput& operator>>(T& result) { if (!good_) return *this; int c = skip_space(); if (c == EOF) return *this; bool negative = false; if (c == '-' || c == '+') { negative = c == '-'; ++position_; c = peek(); } if (c == EOF) { good_ = false; return *this; } #ifndef SKIP_RUNTIME_CHECKS if (c < '0' || c > '9') { good_ = false; return *this; } // 先頭の0を除けば、20桁以下の末尾直前の値はuint64_tに収まる。 while (c == '0') { ++position_; c = peek(); } std::uint64_t previous = 0; unsigned last_digit = 0; std::size_t digits = 0; #endif std::uint64_t value = 0; #ifdef SKIP_RUNTIME_CHECKS // バッファ末尾の番兵で内側の範囲判定を省き、数字が境界をまたぐときだけ補充する。 for (;;) { const unsigned char* first = buffer_.data() + position_; const unsigned char* cursor = first; while (static_cast(*cursor - '0') < 10) { value = value * 10 + static_cast(*cursor - '0'); ++cursor; } position_ += static_cast(cursor - first); if (position_ != size_) break; c = peek(); if (c == EOF) break; } #else while (c >= '0' && c <= '9') { previous = value; last_digit = static_cast(c - '0'); if (digits <= 20) ++digits; value = value * 10 + static_cast(c - '0'); ++position_; c = peek(); } #endif #ifndef SKIP_RUNTIME_CHECKS constexpr auto maximum = std::numeric_limits::max(); if ((c != EOF && c > ' ') || digits > 20 || (digits == 20 && (previous > maximum / 10 || (previous == maximum / 10 && last_digit > maximum % 10)))) { good_ = false; return *this; } std::uint64_t limit = static_cast(std::numeric_limits::max()); if constexpr (std::is_signed_v) limit += negative; else if (negative && value != 0) good_ = false; if (value > limit) good_ = false; if (!good_) return *this; #endif if constexpr (std::is_signed_v) { constexpr std::uint64_t minimum_magnitude = static_cast(std::numeric_limits::max()) + 1; // -(最小値)は評価せず、絶対値が最大値+1のときだけ最小値を使う。 result = negative ? (value == minimum_magnitude ? std::numeric_limits::min() : static_cast(-static_cast(value))) : static_cast(value); } else result = static_cast(value); return *this; } VerifyInput& operator>>(char& result) { if (!good_) return *this; const int c = skip_space(); if (c != EOF) { result = static_cast(c); ++position_; } return *this; } VerifyInput& operator>>(std::string& result) { if (!good_) return *this; int c = skip_space(); if (c == EOF) return *this; result.clear(); for (;;) { const std::size_t first = position_; while (position_ < size_ && buffer_[position_] > ' ') ++position_; result.append(reinterpret_cast(buffer_.data() + first), position_ - first); if (position_ != size_ || peek() == EOF) break; } return *this; } template requires std::is_floating_point_v VerifyInput& operator>>(T& result) { std::string token; *this >> token; if (!good_) return *this; #ifndef SKIP_RUNTIME_CHECKS char* end = nullptr; const long double value = std::strtold(token.c_str(), &end); if (end != token.c_str() + token.size()) good_ = false; else result = static_cast(value); #else result = static_cast(std::strtold(token.c_str(), nullptr)); #endif return *this; } }; // VerifyOutput(file=stdout): 非所有のFILEへ書く。破棄時にflushし、FILEは閉じない。 // << 整数/char/文字列/浮動小数点: 値を出力する。整数は64bit以下に対応する。 // fixed(digits): 浮動小数点を小数点以下digits桁で出力する(digits>=0)。 // flush(): バッファの内容をFILEへ渡す。bool / !で書き込み失敗を確認できる。 class VerifyOutput { static constexpr std::size_t buffer_size = 1 << 17; std::FILE* file_; std::array buffer_; std::size_t size_ = 0; int precision_ = 6; bool fixed_ = false, good_ = true; void write(std::string_view text) { while (!text.empty() && good_) { if (size_ == buffer_.size()) flush(); const auto count = std::min(text.size(), buffer_.size() - size_); std::memcpy(buffer_.data() + size_, text.data(), count); size_ += count; text.remove_prefix(count); } } public: explicit VerifyOutput(std::FILE* file = stdout) : file_(file) {} VerifyOutput(const VerifyOutput&) = delete; VerifyOutput& operator=(const VerifyOutput&) = delete; ~VerifyOutput() { flush(); } explicit operator bool() const noexcept { return good_; } bool operator!() const noexcept { return !good_; } VerifyOutput& fixed(int digits) { if (digits < 0) throw std::invalid_argument("negative output precision"); fixed_ = true; precision_ = digits; return *this; } void flush() noexcept { std::size_t written = 0; while (written < size_ && good_) { const auto count = std::fwrite(buffer_.data() + written, 1, size_ - written, file_); if (count == 0) good_ = false; written += count; } size_ = 0; } template requires (std::is_integral_v && sizeof(T) <= sizeof(std::uint64_t) && !std::is_same_v) VerifyOutput& operator<<(T value) { if constexpr (std::is_same_v) return *this << static_cast('0' + value); else { constexpr std::size_t capacity = std::numeric_limits::digits10 + 3; if (buffer_.size() - size_ < capacity) flush(); if (!good_) return *this; const auto end = std::to_chars(buffer_.data() + size_, buffer_.data() + size_ + capacity, value).ptr; size_ = static_cast(end - buffer_.data()); return *this; } } VerifyOutput& operator<<(char value) { if (size_ == buffer_.size()) flush(); if (good_) buffer_[size_++] = value; return *this; } VerifyOutput& operator<<(std::string_view value) { write(value); return *this; } VerifyOutput& operator<<(const std::string& value) { write(value); return *this; } VerifyOutput& operator<<(const char* value) { write(value); return *this; } template requires std::is_floating_point_v VerifyOutput& operator<<(T value) { char local[128]; const char* format = fixed_ ? "%.*Lf" : "%.*Lg"; const int count = std::snprintf(local, sizeof(local), format, precision_, static_cast(value)); if (count < 0) good_ = false; else if (static_cast(count) < sizeof(local)) write(std::string_view(local, static_cast(count))); else { std::vector text(static_cast(count) + 1); std::snprintf(text.data(), text.size(), format, precision_, static_cast(value)); write(std::string_view(text.data(), static_cast(count))); } return *this; } }; inline VerifyInput verify_in; inline VerifyOutput verify_out; #endif #include int main() { std::int64_t n{}; verify_in >> n; int bound = 1; while (std::int64_t{bound} * bound < n) ++bound; IntegerSieve sieve(bound); int nim_sum = 0; for (const auto& factor : sieve.prime_factorization(n)) nim_sum ^= factor.second; verify_out << (nim_sum ? "Alice\n" : "Bob\n"); }