結果
| 問題 | No.3441 Sort Permutation 2 |
| コンテスト | |
| ユーザー |
 zoidzium (zz)
|
| 提出日時 | 2026-02-06 21:50:06 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 41,215 bytes |
| 記録 | |
| コンパイル時間 | 4,230 ms |
| コンパイル使用メモリ | 361,044 KB |
| 実行使用メモリ | 16,336 KB |
| 最終ジャッジ日時 | 2026-02-06 21:50:49 |
| 合計ジャッジ時間 | 18,992 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 10 WA * 31 |
ソースコード
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ull = unsigned long long;
using ll = long long;
using xy = pair<ll, ll>;
using coord = pair<double, double>;
using bs8 = bitset<8>;
using bs16 = bitset<16>;
using bs32 = bitset<32>;
using bs64 = bitset<64>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vxy = vector<xy>;
using vvxy = vector<vxy>;
using vcoord = vector<coord>;
using vvcoord = vector<vcoord>;
#define rep(var, n) for (ll var = 0; var < (ll)(n); var++)
#define cnt(var, n, m) for (ll var = (n); var <= (ll)(m); var++)
#define rcnt(var, n, m) for (ll var = (n); var >= (ll)(m); var--)
#define each(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define reach(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define MOD107 1000000007
#define MOD998 998244353
#define MOD897 897581057
#define MOD880 880803841
#define ZINIT 1
#if __has_include("zout.h")
#include "zout.h"
#else
namespace zz_print {
class dbg {
public:
static inline string margin = "", separated = "", indentS = "";
static inline int hierarchical = 0, topHier = 0, precision = 6;
static inline bool unprint = false, exponential = false;
static void setFloat(const int prec, const bool expo) {
precision = prec;
exponential = expo;
}
template <int hier = 0, int sep = 2, int mgn = 1, typename... Args>
static void zout(Args&&... args) {}
};
} // namespace zz_print
using namespace zz_print;
#endif
namespace zz_time {
using Clock = std::chrono::steady_clock;
inline Clock::time_point start_time() {
static const Clock::time_point st = Clock::now();
return st;
}
inline ll elapsed_ms() {
return std::chrono::duration_cast<std::chrono::milliseconds>(Clock::now() - start_time()).count();
}
inline bool within(ll limit_ms) { return (elapsed_ms() < limit_ms); }
inline bool timeout(ll limit_ms) { return (elapsed_ms() >= limit_ms); }
} // namespace zz_time
using namespace zz_time;
namespace zz_random {
struct Xoshiro256 {
static inline ull rotl(ull x, int k) { return (x << k) | (x >> (64 - k)); }
static inline ull splitmix64(ull& x) {
ull z = (x += 0x9e3779b97f4a7c15ULL);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
}
ull s[4];
explicit Xoshiro256(ull seed = 1) {
ull x = seed;
for (size_t i = 0; i < 4; i++) s[i] = splitmix64(x);
}
inline ull next() {
ull res = rotl(s[1] * 5, 7) * 9, t = s[1] << 17;
s[2] ^= s[0], s[3] ^= s[1], s[1] ^= s[2], s[0] ^= s[3], s[2] ^= t;
s[3] = rotl(s[3], 45);
return res;
}
inline ull operator()() { return next(); }
/// integer [0, n)
inline ll intn(const ll n = 2) { return (ll)(next() % (ull)n); }
/// integer [l, r]
inline ll range(const ll l, const ll r) { return l + intn(r - l + 1); }
/// real (0, 1)
inline double real() { return (next() >> 11) * (1.0 / (1ULL << 53)); }
inline double real(const double r) { return real() * r; }
inline double real(const double l, const double r) { return (l + real() * (r - l)); }
// Box–Muller 用キャッシュ
bool has_spare = false;
double spare;
/// 標準正規分布 N(0,1)
inline double normal01() {
if (has_spare) {
has_spare = false;
return spare;
}
double u = 0.0, v;
while (u <= 0.0) u = real(); // (0,1)
v = real();
double r = sqrt(-2.0 * log(u)), theta = 2.0 * M_PI * v;
spare = r * sin(theta), has_spare = true;
return r * cos(theta);
}
/// 正規分布 N(mean, stddev^2)
inline double normal(const double mean, const double stddev) { return mean + stddev * normal01(); }
};
} // namespace zz_random
using namespace zz_random;
namespace zz_numeric {
xy gcdEX(ll a, ll b, ll& d) {
d = abs(b);
if (a == 0) return xy{0, 1 - 2 * (b < 0)};
vxy vec;
vl rvs;
while (a != 0 || b != 0) {
rvs.push_back(abs(a) < abs(b));
if (rvs.back()) swap(a, b);
if (b == 0) {
d = abs(a);
vec.emplace_back(1 - 2 * (a < 0), 0);
break;
}
vec.emplace_back(a, b);
swap(a, b);
b %= a;
}
if (rvs.back()) swap(vec.back().first, vec.back().second);
for (size_t i = vec.size() - 1; i > 0; i--) {
vec[i - 1] = xy{vec[i].second, vec[i].first - (vec[i - 1].first / vec[i - 1].second) * vec[i].second};
if (rvs[i - 1]) swap(vec[i - 1].first, vec[i - 1].second);
}
return vec[0];
}
xy gcdEX(ll a, ll b) {
ll d;
return gcdEX(a, b, d);
}
xy gcdEX(xy ab, ll& d) { return gcdEX(ab.first, ab.second, d); }
xy gcdEX(xy ab) { return gcdEX(ab.first, ab.second); }
ll gcd(ll a, ll b) {
ll d;
gcdEX(a, b, d);
return d;
}
ll gcd(xy ab) { return gcd(ab.first, ab.second); }
ll lcm(ll a, ll b) {
ll d = gcd(a, b);
return ((a / d) * b);
}
ll lcm(xy ab) { return lcm(ab.first, ab.second); }
ll gcd(vl vec) {
size_t n = vec.size(), m = 1;
while (m < n) {
for (size_t i = 0; (i + m) < n; i += 2 * m) vec[i] = gcd(vec[i], vec[i + m]);
m <<= 1;
}
return vec[0];
}
ll lcm(vl vec) {
size_t n = vec.size(), m = 1;
while (m < n) {
for (size_t i = 0; (i + m) < n; i += 2 * m) vec[i] = lcm(vec[i], vec[i + m]);
m <<= 1;
}
return vec[0];
}
ll modinv(ll x, ll mod) {
assert(x != 0);
ll d;
xy ans = gcdEX(x, mod, d);
assert(d == 1);
ans.first %= mod, ans.first += mod & -(ans.first < 0);
return ans.first;
}
ll modexp(ll x, ll n, ll mod) {
if (n == 0) return 1;
if (x == 0) return 0;
ll ans = 1;
if (n < 0) {
x = modinv(x, mod), n *= -1;
}
while (n > 0) {
if (n & 1) ans = (ans * x) % mod;
x = (x * x) % mod, n >>= 1;
}
return ans;
}
} // namespace zz_numeric
using namespace zz_numeric;
namespace zz_mod {
template <ll mod>
class pp {
public:
ll val;
explicit pp(ll x = 0, bool flush = true) {
val = x;
if (flush) val %= mod, val += mod & -(val < 0);
}
pp<mod> flip() const { return pp<mod>(((mod - val) & -(val > 0)), false); }
pp<mod> inv() const { return pp<mod>(modinv(val, mod), false); };
pp<mod> exp(const ll n) const { return pp<mod>(modexp(val, n, mod), false); };
pp<mod>& fliped() {
val = ((mod - val) & -(val > 0));
return (*this);
};
pp<mod>& inved() {
val = modinv(val, mod);
return (*this);
};
pp<mod>& exped(const ll n) {
val = modexp(val, n, mod);
return (*this);
};
pp<mod>& operator+=(const ll x) {
val = ((__int128)val + x) % mod, val += mod & -(val < 0);
return (*this);
};
pp<mod>& operator-=(const ll x) {
val = ((__int128)val - x) % mod, val += mod & -(val < 0);
return (*this);
};
pp<mod>& operator*=(const ll x) {
val = ((__int128)val * x) % mod, val += mod & -(val < 0);
return (*this);
};
pp<mod>& operator/=(const ll x) {
val = ((__int128)val * modinv(x, mod)) % mod, val += mod & -(val < 0);
return (*this);
};
pp<mod>& operator+=(const pp<mod> a) {
val += a.val, val -= mod & -(val >= mod);
return (*this);
};
pp<mod>& operator-=(const pp<mod> a) {
val -= a.val, val += mod & -(val < 0);
return (*this);
};
pp<mod>& operator*=(const pp<mod> a) {
val = ((__int128)val * a.val) % mod;
return (*this);
};
pp<mod>& operator/=(const pp<mod> a) {
val = ((__int128)val * modinv(a.val, mod)) % mod;
return (*this);
};
friend pp<mod> operator+(pp<mod> a, const ll x) {
a += x;
return a;
}
friend pp<mod> operator+(const ll x, pp<mod> a) {
a += x;
return a;
}
friend pp<mod> operator+(pp<mod> a, const pp<mod> b) {
a += b;
return a;
}
friend pp<mod> operator-(pp<mod> a, const ll x) {
a -= x;
return a;
}
friend pp<mod> operator-(const ll x, pp<mod> a) {
a -= x, a.fliped();
return a;
}
friend pp<mod> operator-(pp<mod> a, const pp<mod> b) {
a -= b;
return a;
}
friend pp<mod> operator*(pp<mod> a, const ll x) {
a *= x;
return a;
}
friend pp<mod> operator*(const ll x, pp<mod> a) {
a *= x;
return a;
}
friend pp<mod> operator*(pp<mod> a, const pp<mod> b) {
a *= b;
return a;
}
friend pp<mod> operator/(pp<mod> a, const ll x) {
a /= x;
return a;
}
friend pp<mod> operator/(const ll x, pp<mod> a) {
a.inved() *= x;
return a;
}
friend pp<mod> operator/(pp<mod> a, const pp<mod> b) {
a /= b;
return a;
}
};
template <ll mod>
class modfactor {
public:
static inline vl modfactor_invs = vl{}, modfactor_nums = vl{}, modfactor_dens = vl{};
void set(const size_t n) {
assert(n >= 1);
modfactor_invs.resize(n + 1, 1);
modfactor_nums.resize(n + 1, 1);
modfactor_dens.resize(n + 1, 1);
modfactor_invs[0] = 1, modfactor_invs[1] = 1;
modfactor_nums[0] = 1, modfactor_nums[1] = 1;
modfactor_dens[0] = 1, modfactor_dens[1] = 1;
for (size_t i = 2; i <= n; i++) {
modfactor_nums[i] = ((__int128)modfactor_nums[i - 1] * i) % mod;
modfactor_invs[i] = (mod - ((__int128)(mod / i) * modfactor_invs[mod % i])) % mod;
modfactor_invs[i] += mod & -(modfactor_invs[i] < 0);
modfactor_dens[i] = ((__int128)modfactor_dens[i - 1] * modfactor_invs[i]) % mod;
}
}
modfactor(const size_t n) { set(n); }
void resize(const size_t n) {
if (modfactor_invs.size() < (n + 1)) set(n);
}
ll inv(const size_t i) const { return modfactor_invs[i]; }
ll factorial(const size_t i) const { return modfactor_nums[i]; }
ll factorial_inv(const size_t i) const { return modfactor_dens[i]; }
ll P(const size_t n, const size_t m) const {
if (n <= m) return factorial(n);
return ((__int128)factorial(n) * factorial_inv(n - m)) % mod;
}
ll C(const size_t n, const size_t m) const {
if (n < m) return 1;
ll den = ((__int128)factorial_inv(n - m) * factorial_inv(m)) % mod;
return ((__int128)factorial(n) * den) % mod;
}
};
} // namespace zz_mod
using namespace zz_mod;
namespace zz_prime {
class prime {
public:
static inline vl sieves = vl{};
static constexpr array<ll, 14> pre_trial_division =
array<ll, 14>{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
static void set(const ll n) {
sieves = vl(n + 1, 1);
for (size_t i = 2; i <= n; i++) {
if (sieves[i] != 1) continue;
size_t j = 2 * i;
while (j <= n) {
if (sieves[j] == 1) sieves[j] = i;
j += i;
}
}
}
prime(const size_t n) { set(n); }
static void resize(const size_t n) {
if (sieves.size() < (n + 1)) set(n);
}
static bool millerRabin(const ll n) {
if (n < 2) return false;
if (n == 2) return true;
if ((n & 1) == 0) return false;
vl a = vl{2, 7, 61};
if (n >= 4759123141) a = vl{2, 325, 9375, 28178, 450775, 9780504, 1795265022};
size_t m = a.size();
for (size_t i = 0; i < m; i++) {
if (a[i] >= n) break;
size_t d = n - 1;
while ((d & 1) == 0) d >>= 1;
ll x = 1, b = a[i] % n, c = d;
while (c > 0) {
if (c & 1) x = ((__int128)x * b) % n;
b = ((__int128)b * b) % n, c >>= 1;
}
if (x == 1 || x == (n - 1)) continue;
bool OK = false;
while (d < (n - 1)) {
if (x == (n - 1)) {
OK = true;
break;
}
x = ((__int128)x * x) % n, d <<= 1;
}
if (OK) continue;
return false;
}
return true;
}
static bool isPrime(const ll x) {
if (sieves.size() <= x) return millerRabin(x);
if (x < 2) return false;
return (sieves[x] == 1);
}
static vxy pollardsRho(ll x) {
if (x < 2) return vxy();
vl prms;
Xoshiro256 rnd;
function<ll(ll, const ll, const ll)> F = [&rnd](ll x, const ll c, const ll m) -> ll {
return (((__int128)x * x + c) % m);
};
function<void(ll)> Pollards = [&rnd, &F, &prms, &Pollards](const ll n) {
if (n < 2) return;
if (millerRabin(n)) {
prms.push_back(n);
return;
}
ll r = sqrtl(n);
if ((r * r) == n) {
Pollards(r), Pollards(r);
return;
}
while (true) {
ll a = rnd.range(2, n - 1), b = a, c = rnd.range(1, n - 1), d = 1, loopCnt = 0;
do {
loopCnt++;
ll e = 1, k = 64;
while (k > 0) {
a = F(a, c, n), b = F(F(b, c, n), c, n);
ll tmp = ((__int128)e * abs(a - b)) % n;
if (tmp == 0) break;
e = tmp, k--;
}
d = gcd(e, n);
} while (d == 1 && loopCnt < 20);
if (loopCnt >= 20) continue;
if (d != n) {
Pollards(d), Pollards(n / d);
return;
}
}
};
while ((x & 1) == 0) {
x >>= 1, prms.push_back(2);
}
for (size_t i = 0; i < pre_trial_division.size(); i++) {
if (x < pre_trial_division[i]) break;
while ((x % pre_trial_division[i]) == 0) {
x /= pre_trial_division[i];
prms.push_back(pre_trial_division[i]);
}
}
Pollards(x);
vxy ans;
sort(prms.begin(), prms.end());
for (size_t i = 0; i < prms.size(); i++) {
if (ans.empty() || ans.back().first != prms[i]) {
ans.emplace_back(prms[i], 1);
} else {
ans.back().second++;
}
}
return ans;
}
static vxy factorization(ll x) {
if (sieves.size() <= x) return pollardsRho(x);
vl prms;
if (x < 2) return vxy();
while (sieves[x] != 1) {
x /= sieves[x], prms.push_back(sieves[x]);
}
if (x != 1) prms.push_back(x);
sort(prms.begin(), prms.end());
vxy ans;
for (size_t i = 0; i < prms.size(); i++) {
if (ans.empty() || ans.back().first != prms[i]) {
ans.emplace_back(prms[i], 1);
} else {
ans.back().second++;
}
}
return ans;
}
static vl divisor(const vxy& fac, const bool srt) {
vl ans;
function<void(ll, ll)> func = [&ans, &fac, &func](ll at, ll e) -> void {
if (at == fac.size()) return;
ll a = 1;
for (size_t _i = 0; _i <= fac[at].second; _i++) {
if (a != 1) ans.push_back(e * a);
func(at + 1, e * a), a *= fac[at].first;
}
};
func(0, 1);
if (srt) sort(ans.begin(), ans.end());
return ans;
}
static vl divisor(const ll n, const bool srt) { return divisor(factorization(n), srt); }
};
} // namespace zz_prime
using namespace zz_prime;
namespace zz_ganer {
ll ganer_prefix(span<xy> vec, const ll mod) {
size_t n = vec.size();
for (size_t i = 0; i < n; i++) {
for (size_t j = 0; j < i; j++) {
ll d = gcd(vec[i].second, vec[j].second);
if ((vec[i].first - vec[j].first) % d != 0) return -1;
vec[i].second /= d, vec[j].second /= d;
ll di = gcd(vec[i].second, d), dj = d / di;
do {
d = gcd(di, dj), di *= d, dj /= d;
} while (d != 1);
vec[i].second *= di, vec[j].second *= dj, vec[i].first %= vec[i].second, vec[j].first %= vec[j].second;
}
}
ll lcm_val = 1;
each(ite, vec) lcm_val = ((__int128)lcm_val * ite->second) % mod;
return lcm_val;
}
template <ll m = 1>
ll ganer(vxy vec, bool pos = false, bool prefix = true) {
ll n = vec.size(), mod = m;
bool zero_possible = true;
for (size_t i = 0; i < n; i++) {
if (vec[i].first > 0) {
zero_possible = false;
break;
}
}
if (prefix) {
ll pre_ans = ganer_prefix(vec, m);
if (pre_ans == -1) return -1;
if (pos && zero_possible) return pre_ans;
}
if (n == 0) return -1;
if (mod <= 1) {
mod = 1;
for (size_t i = 0; i < n; i++) mod *= vec[i].second;
}
vl coef(n + 1, 1), cval(n + 1, 0);
vec.emplace_back(0, mod);
for (size_t i = 0; i < n; i++) {
ll r = vec[i].first, p = vec[i].second;
// xy ans = gcdEX(coef[i], p);
// ll ta = (r - cval[i]) % p, tb = ans.first % p;
ll ta = (r - cval[i]) % p, tb = modinv(coef[i], p);
ta += p & -(ta < 0), tb += p & -(tb < 0);
ll t = ((__int128)ta * tb) % p;
cnt(j, i + 1, n) {
cval[j] = (cval[j] + (__int128)t * coef[j]) % vec[j].second;
coef[j] = ((__int128)coef[j] * p) % vec[j].second;
}
}
return cval.back();
}
} // namespace zz_ganer
using namespace zz_ganer;
namespace zz_poly {
template <const ll mod = 998244353>
class poly {
public:
vl fps;
static inline size_t show_size = 7;
static inline constexpr array<array<array<ll, 24>, 2>, 3> roots = array<array<array<ll, 24>, 2>, 3>{
array<array<ll, 24>, 2>{
array<ll, 24>{1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469,
476477967, 166035806, 258648936, 584193783, 63912897, 350007156, 666702199, 968855178,
629671588, 24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432},
array<ll, 24>{1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158,
304459705, 685443576, 381598368, 335559352, 129292727, 358024708, 814576206, 708402881,
283043518, 3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224}},
array<array<ll, 24>, 2>{
array<ll, 24>{1, 897581056, 200527991, 850960045, 227655573, 685177417, 661961559, 717889083,
688546301, 64431346, 762907769, 781659575, 604882016, 471181658, 242773703, 313099125,
288794207, 732004569, 437566725, 430897771, 279727937, 91704119, 523358721, 872686320},
array<ll, 24>{1, 897581056, 697053066, 442470459, 502631723, 192192108, 366473218, 285218810,
627498913, 632928577, 715124372, 829482092, 895669752, 835819291, 210274124, 7242324,
530138839, 365592405, 712687518, 812501856, 244025573, 353112847, 793229247, 354917575}},
array<array<ll, 24>, 2>{
array<ll, 24>{1, 880803840, 121444121, 547680885, 836988352, 170630252, 547743738, 390590270,
755881750, 119481987, 622213777, 634844223, 496183605, 872875137, 41469254, 551868471,
219288049, 198000217, 579409128, 733691905, 566136041, 374515633, 402082372, 273508579},
array<ll, 24>{1, 880803840, 759359720, 339414624, 282082127, 83908436, 623501316, 879302015,
26105166, 708522529, 769895303, 843755407, 710708181, 623500536, 528308065, 542164623,
817679620, 571049407, 409417309, 504998132, 352282463, 252040680, 400443141, 109748732}}};
friend std::ostream& operator<<(std::ostream& os, poly<mod>& ply) {
string s = "[ ";
size_t n = min<size_t>(ply.size(), show_size);
for (size_t i = 0; i < n; i++) s += " " + to_string(ply[i]) + " ";
if (n < ply.size()) s += " ~ ";
return os << s << " ]";
}
const ll at(const size_t n) const {
assert(n < size());
return fps[n];
}
ll& at(const size_t n) {
assert(n < size());
return fps[n];
}
const ll operator[](const size_t n) const { return at(n); }
ll& operator[](const size_t n) { return at(n); }
poly<mod>& shift(const ll m) {
if (m == 0) return (*this);
ll n = size();
if (m > 0) {
vl vec(n + m, 0);
for (size_t i = 0; i < n; i++) vec[i + m] = fps[i];
swap(vec, fps);
} else if (n > -m) {
n += m;
vl vec(n, 0);
for (size_t i = 0; i < n; i++) vec[i] = fps[-m + i];
swap(vec, fps);
} else {
fps.clear();
}
return (*this);
}
const size_t degree() const { return max<ll>(0, fps.size() - 1); }
const size_t size() const { return fps.size(); }
poly<mod>& resize(const size_t n, const ll elm = 0) {
fps.resize(n, elm);
return (*this);
}
poly<mod>& redegree(const size_t n, const ll elm = 0) {
fps.resize(n + 1, elm);
return (*this);
}
poly<mod>& shrink() {
size_t n = size();
while (n > 0 && at(n - 1) == 0) n--;
resize(n);
return (*this);
}
poly(size_t n = 0, const ll elm = 0) { resize(n, elm); }
explicit poly(span<const ll> vec) {
ll n = vec.size();
resize(n);
for (size_t i = 0; i < n; i++) at(i) += vec[i];
}
static ll getModType() {
if (mod == MOD998) return 0;
if (mod == MOD897) return 1;
if (mod == MOD880) return 2;
return -1;
}
poly<mod>& flip() {
size_t n = size();
for (size_t i = 0; i < n; i++) fps[i] = (fps[i] ? mod - fps[i] : 0);
return (*this);
}
poly<mod>& operator+=(span<const ll> ply) {
size_t n = ply.size();
if (size() < n) resize(n);
for (size_t i = 0; i < n; i++) {
fps[i] += ply[i];
if (fps[i] >= mod) fps[i] -= mod;
}
return (*this);
}
poly<mod>& operator+=(const poly<mod>& ply) { return ((*this) += ply.fps); }
friend poly<mod> operator+(poly<mod> plyA, span<const ll> plyB) { return (plyA += plyB); }
friend poly<mod> operator+(span<const ll> plyA, poly<mod> plyB) { return (plyB += plyA); }
friend poly<mod> operator+(poly<mod> plyA, const poly<mod>& plyB) { return (plyA += plyB); }
poly<mod>& operator-=(span<const ll> ply) {
size_t n = ply.size();
if (size() < n) resize(n);
for (size_t i = 0; i < n; i++) {
fps[i] -= ply[i];
if (fps[i] < 0) fps[i] += mod;
}
return (*this);
}
poly<mod>& operator-=(const poly<mod>& ply) { return ((*this) -= ply.fps); }
friend poly<mod> operator-(poly<mod> plyA, span<const ll> plyB) { return (plyA -= plyB); }
friend poly<mod> operator-(const vl& plyA, const poly<mod>& plyB) { return (poly<mod>(plyA) -= plyB.fps); }
friend poly<mod> operator-(poly<mod> plyA, const poly<mod>& plyB) { return (plyA -= plyB.fps); }
static void furie2_bit_rev(span<ll> a) {
size_t n = a.size();
for (size_t i = 1, j = 0; i < n; i++) {
size_t bit = (n >> 1);
for (; j & bit; bit >>= 1) j ^= bit;
j |= bit;
if (i < j) swap(a[i], a[j]);
}
}
static void furie2_buttfly(span<ll> a, bool rvs = false) {
ll typ = getModType(), n = a.size(), Rt, tmp;
for (size_t m = 1, b = 1; m < n; m <<= 1, b++) {
for (size_t i = 0; i < n; i += (m << 1)) {
Rt = 1;
for (size_t j = 0; j < m; j++) {
// dbg::zout("m=", m, j, roots[typ][rvs][b], Rt);
tmp = (a[i + j + m] * Rt) % mod;
// dbg::zout(" a=", a[i + j], a[i + j + m], tmp);
a[i + j + m] = a[i + j] + (mod - tmp), a[i + j + m] -= mod & -(a[i + j + m] >= mod);
a[i + j] += tmp, a[i + j] -= mod & -(a[i + j] >= mod);
// dbg::zout(" a=", a[i + j], a[i + j + m]);
Rt = (Rt * roots[typ][rvs][b]) % mod;
}
}
}
if (rvs) {
n = a.size();
ll nInv = modinv(n, mod);
for (size_t i = 0; i < n; i++) a[i] = (a[i] * nInv) % mod;
}
return;
}
void conv_normal(vl a, vl b, vl& c) {
assert(mod == 998244353 || mod == 897581057 || mod == 880803841);
c.clear();
size_t n = (a.size() + b.size()), m = 1, blen = 0;
if (n == 0) return;
while (m < n) {
m <<= 1, blen++;
}
a.resize(m), b.resize(m);
furie2_bit_rev(a), furie2_bit_rev(b);
furie2_buttfly(a), furie2_buttfly(b);
c.resize(m);
for (size_t i = 0; i < m; i++) c[i] = ((__int128)a[i] * b[i]) % mod;
furie2_bit_rev(c);
furie2_buttfly(c, true), c.resize(n - 1);
}
void conv_ganer(vl a998, vl b998, vl& c) {
c.clear();
size_t n = (a998.size() + b998.size()), m = 1, blen = 0;
if (n == 0) return;
while (m < n) {
m <<= 1, blen++;
}
a998.resize(m), b998.resize(m);
poly<mod>::furie2_bit_rev(a998), poly<mod>::furie2_bit_rev(b998);
vl a897(m), b897(m), a880(m), b880(m);
copy(a998.begin(), a998.end(), a897.begin());
copy(b998.begin(), b998.end(), b897.begin());
copy(a998.begin(), a998.end(), a880.begin());
copy(b998.begin(), b998.end(), b880.begin());
poly<MOD998>::furie2_buttfly(a998);
poly<MOD998>::furie2_buttfly(b998);
poly<MOD897>::furie2_buttfly(a897);
poly<MOD897>::furie2_buttfly(b897);
poly<MOD880>::furie2_buttfly(a880);
poly<MOD880>::furie2_buttfly(b880);
vvl C(3, vl(m));
for (size_t i = 0; i < m; i++) {
C[0][i] = ((__int128)a998[i] * b998[i]) % MOD998;
C[1][i] = ((__int128)a897[i] * b897[i]) % MOD897;
C[2][i] = ((__int128)a880[i] * b880[i]) % MOD880;
}
poly<mod>::furie2_bit_rev(C[0]);
poly<MOD998>::furie2_buttfly(C[0], true);
C[0].resize(n - 1);
poly<mod>::furie2_bit_rev(C[1]);
poly<MOD897>::furie2_buttfly(C[1], true);
C[1].resize(n - 1);
poly<mod>::furie2_bit_rev(C[2]);
poly<MOD880>::furie2_buttfly(C[2], true);
C[2].resize(n - 1);
c.resize(n - 1);
for (size_t i = 0; i < (n - 1); i++) {
c[i] = ganer<mod>(vxy{xy{C[0][i], MOD998}, xy{C[1][i], MOD897}, xy{C[2][i], MOD880}}, false, false);
}
}
void prod(const vl& a, const vl& b, vl& c) {
size_t n = a.size(), m = b.size();
bool naive_flg = (min<size_t>(n, m) <= 65);
// naive_flg = false;
if (naive_flg) {
vl d(n + m - 1, 0);
for (size_t i = 0; i < n; i++)
for (size_t j = 0; j < m; j++) d[i + j] = (d[i + j] + (__int128)a[i] * b[j]) % mod;
swap(d, c);
} else if (getModType() != -1)
conv_normal(a, b, c);
else
conv_ganer(a, b, c);
}
poly<mod>& operator*=(const ll x) {
size_t n = size();
for (size_t i = 0; i < n; i++) fps[i] = ((__int128)fps[i] * x) % mod;
return (*this);
}
friend poly<mod> operator*(poly<mod> plyA, const ll x) { return (plyA *= x); }
friend poly<mod> operator*(const ll x, poly<mod> plyA) { return (plyA *= x); }
poly<mod>& operator*=(const vl& plyA) {
prod(fps, plyA, fps);
return (*this);
}
poly<mod>& operator*=(const poly<mod>& plyA) {
prod(fps, plyA.fps, fps);
return (*this);
}
friend poly<mod> operator*(poly<mod> plyA, const vl& x) { return (plyA *= x); }
friend poly<mod> operator*(const vl& x, poly<mod> plyA) { return (plyA *= x); }
friend poly<mod> operator*(poly<mod> plyA, const poly<mod>& plyB) { return (plyA *= plyB); }
poly<mod> inv() const {
// dbg::zout("fps=", fps);
assert(!fps.empty() && fps[0]);
size_t n = size();
poly<mod> plyG(1, modinv(fps[0], mod));
poly<mod> ply2_FG;
size_t m = 1;
vl plyF(1, fps[0]);
while (m < n) {
m <<= 1;
if (m > n) m = n;
if (plyF.size() < m) {
plyF.resize(m);
for (size_t i = plyG.size(); i < m; i++) plyF[i] = fps[i];
}
// dbg::zout("m=", m);
plyF.resize(m), plyG.resize(m, 0);
// dbg::zout("plyF=", plyF);
// dbg::zout("plyG=", plyG.fps);
ply2_FG = plyF * plyG;
ply2_FG.resize(m);
// dbg::zout("ply2_FG=", ply2_FG.fps);
ply2_FG.flip();
ply2_FG.fps[0] += 2;
if (ply2_FG.fps[0] >= mod) ply2_FG.fps[0] -= mod;
// dbg::zout("ply2_FG=", ply2_FG.fps);
plyG *= ply2_FG;
plyG.resize(m);
}
return plyG;
}
poly<mod>& operator/=(ll x) {
x = modinv(x, mod);
return ((*this) *= x);
}
friend poly<mod> operator/(poly<mod> plyA, const ll x) { return (plyA /= x); }
poly<mod>& operator/=(const poly<mod>& plyA) { return ((*this) *= plyA.inv()); }
friend poly<mod> operator/(poly<mod> plyA, const poly<mod>& plyB) { return (plyA /= plyB); }
poly<mod> differential() const {
size_t n = size();
poly<mod> ply;
if (n == 0) return ply;
ply.resize(n - 1);
for (size_t i = 0; i < n - 1; i++) ply.fps[i] = ((__int128)fps[i + 1] * (i + 1)) % mod;
return ply;
}
poly<mod> integral() const {
poly<mod> ply(1, 0);
ll n = size();
ply.resize(n + 1);
for (size_t i = 0; i < n; i++) ply.fps[i + 1] = ((__int128)fps[i] * modinv(i + 1, mod)) % mod;
return ply;
}
poly<mod> log() {
assert(!fps.empty() && fps[0] == 1);
poly<mod> plyF = differential() / (*this);
plyF.resize(size());
plyF = plyF.integral();
plyF.resize(size());
return plyF;
}
poly<mod> exp() {
assert(!fps.empty() && fps[0] == 0);
poly<mod> plyG(1, 1), plyF;
while (plyG.size() < size()) {
plyG.resize(min<ll>(plyG.size() * 2, size()));
while (plyF.size() < plyG.size()) plyF.fps.push_back(fps[plyF.size()]);
poly<mod> ply1F_G = (plyF - plyG.log());
ply1F_G.fps[0]++;
if (ply1F_G.fps[0] >= mod) ply1F_G.fps[0] -= mod;
plyG = plyG * ply1F_G;
plyG.resize(plyF.size());
}
return plyG;
}
vector<poly<mod>> get_quotientRemainder(const poly<mod>& plyB) const {
ll n = size(), m = plyB.size();
vector<poly<mod>> plys(2);
if (n < m) {
plys[1] = *this;
return plys;
}
poly<mod> RplyA, RplyB;
reach(ite, fps) RplyA.fps.push_back(*ite);
reach(ite, plyB.fps) RplyB.fps.push_back(*ite);
RplyA.resize(n - m + 1, 0), RplyB.resize(n - m + 1, 0);
poly<mod> Rply3 = (RplyA / RplyB);
Rply3.resize(n - m + 1);
for (size_t i = 0; i < n - m + 1; i++) plys[0].fps.push_back(Rply3[n - m - i]);
poly<mod> ply3 = plyB * plys[0];
plys[1] = (this->fps - ply3);
plys[1].resize(m - 1);
return plys;
}
ll get_bostanMori(poly<mod> plyD, ll n) {
assert(plyD.size() > 0);
poly<mod> plyH;
poly<mod> plyN = (*this);
plyN.resize(plyD.size());
while (n) {
plyH = plyD;
ll m = plyH.size() / 2;
for (size_t i = 0; i < m; i++) plyH[2 * i + 1] = (plyD[2 * i + 1] != 0 ? mod - plyD[2 * i + 1] : 0);
plyN *= plyH;
plyD = plyD * plyH;
plyH.resize((plyD.size() + 1) / 2);
for (size_t i = 0; i < plyH.size(); i++) plyH[i] = plyD[2 * i];
swap(plyD, plyH);
if (n % 2 == 0) {
plyH.resize((plyN.size() + 1) / 2);
for (size_t i = 0; i < plyH.size(); i++) plyH[i] = plyN[2 * i];
} else {
plyH.resize(plyN.size() / 2);
for (size_t i = 0; i < plyH.size(); i++) plyH[i] = plyN[2 * i + 1];
}
swap(plyH, plyN);
n >>= 1;
}
return ((__int128)plyN[0] * modinv(plyD[0], mod)) % mod;
}
poly<mod>& pow(ll k) {
if (k == 0) {
fps = vl(size(), 0);
fps[0] = 1;
return (*this);
}
size_t n = size();
ll m = 0;
for (size_t i = 0; i < n; i++) {
if (fps[i] != 0) break;
m++;
}
if (n == m) return (*this);
// dbg::zout(vl{(ll)n, m});
ll a = fps[m];
// dbg::zout(n, m, a, fps);
shift(-m);
// dbg::zout(n, m, a, fps);
if (a != 1) (*this) /= a;
*this = ((*this).log() * k).exp();
if (a != 1) {
a = modexp(a, k, mod);
(*this) *= a;
}
shift(m * k);
resize(n);
return *this;
}
};
} // namespace zz_poly
using namespace zz_poly;
namespace zz_segtree {
template <typename S>
class segtree {
public:
const size_t N;
vector<S> vecS;
size_t head;
bool getyet = true;
void build() {
size_t l = head >> 1, r = (head + N - 1) >> 1;
while (l > 0) {
for (size_t i = l; i <= r; i++) vecS[i] = vecS[i << 1] * vecS[(i << 1) + 1];
l >>= 1, r >>= 1;
}
}
segtree(const size_t n) : N(n) {
head = 1;
while (head < N) head <<= 1;
vecS = vector<S>(head << 1, S::e());
for (size_t i = 0; i < head; i++) vecS[i + head] = S::init();
}
template <typename... Arg>
S s(Arg... arg) {
return S(arg...);
}
void setS(size_t i, const S s) {
assert(i < N);
i += head;
vecS[i] = s;
if (getyet) return;
i >>= 1;
while (i > 0) {
vecS[i] = vecS[i << 1] * vecS[(i << 1) + 1];
i >>= 1;
}
}
S get(size_t l, size_t r) {
assert(l <= r && r <= N);
if (l == r) return S::e();
if (getyet) {
getyet = false, build();
}
S ans_l = S::e(), ans_r = S::e();
l += head, r += head;
while (l < r) {
if (l & 1) ans_l &= vecS[l++];
if (r & 1) ans_r *= vecS[--r];
l >>= 1, r >>= 1;
}
return (ans_l * ans_r);
}
};
template <typename S, typename F>
class lazy_segtree {
public:
const size_t N;
vector<S> vecS;
vector<F> vecF;
size_t head, Nb;
bool fyet = true;
private:
void update(const size_t i, const F add) {
vecS[i] *= add;
if (i < head) vecF[i] *= add;
}
void updates(size_t l, size_t r, const F add) {
l += head, r += head;
while (l < r) {
if (l & 1) update(l++, add);
if (r & 1) update(--r, add);
l >>= 1, r >>= 1;
}
}
S calc(size_t l, size_t r) {
l += head, r += head;
S ans_l = S::e(), ans_r = S::e();
while (l < r) {
if (l & 1) ans_l &= vecS[l++];
if (r & 1) ans_r *= vecS[--r];
l >>= 1, r >>= 1;
}
return (ans_l * ans_r);
}
void give(const size_t i) {
update(i << 1, vecF[i]), update((i << 1) + 1, vecF[i]);
vecF[i] = F::id();
}
void gives(size_t l, size_t r) {
l += head, r += head;
for (size_t i = Nb; i > 0; i--) {
if (((l >> i) << i) != l) give(l >> i);
if (((r >> i) << i) != r) give(r >> i);
}
}
void collect(const size_t i) {
if (i < head) vecS[i] = vecS[i << 1] * vecS[(i << 1) + 1];
}
void collects(size_t l, size_t r) {
l += head, r += head;
for (size_t i = 1; i <= Nb; i++) {
if (((l >> i) << i) != l) collect(l >> i);
if (((r >> i) << i) != r) collect(r >> i);
}
}
public:
void build() {
size_t l = head >> 1, r = (head + N - 1) >> 1;
while (l > 0) {
for (size_t i = l; i <= r; i++) vecS[i] = vecS[i << 1] * vecS[(i << 1) + 1];
l >>= 1, r >>= 1;
}
}
void setS(const size_t at, const S s) {
assert(at < N);
if (fyet) {
vecS[at + head] = s;
return;
}
gives(at, at + 1);
vecS[at + head] = s;
collects(at, at + 1);
}
void setF(const size_t l, const size_t r, const F f) {
assert(l < r && r <= N);
if (fyet) {
fyet = false, build();
}
gives(l, r);
updates(l, r, f);
collects(l, r);
}
S get(const size_t l, const size_t r) {
assert(l <= r && r <= N);
if (l == r) return S::e();
if (fyet) {
fyet = false, build();
}
gives(l, r);
return calc(l, r);
}
lazy_segtree(const size_t _N) : N(_N) {
Nb = 0;
while ((1 << Nb) < N) Nb++;
head = (1 << Nb);
vecS = vector<S>(head << 1, S::e());
vecF = vector<F>(head, F::id());
for (size_t i = 0; i < head; i++) vecS[i + head] = S::init();
}
template <typename... Arg>
S s(Arg... arg) {
return S(arg...);
}
template <typename... Arg>
F f(Arg... arg) {
return F(arg...);
}
};
struct F_affine {
ll a, b;
F_affine(const ll _a = 1, const ll _b = 0) : a(_a), b(_b) {}
static constexpr F_affine id() noexcept { return F_affine(); };
F_affine operator*=(const F_affine add) {
a *= add.a, b = add.a * b + add.b;
return (*this);
}
};
struct S_min {
ll val;
S_min(const ll _val = LONG_LONG_MAX) : val(_val) {}
static constexpr S_min e() noexcept { return S_min(); };
static constexpr S_min init() noexcept { return S_min(); };
S_min& operator*=(const F_affine add) {
val = add.a * val + add.b;
return (*this);
}
S_min& operator*=(const S_min add) {
val = min<ll>(val, add.val);
return (*this);
}
S_min& operator&=(const S_min old) {
val = min<ll>(val, old.val);
return (*this);
}
friend S_min operator*(const S_min add, S_min s) {
s *= add;
return s;
}
};
struct S_max {
ll val;
S_max(const ll _val = -LONG_LONG_MAX) : val(_val) {}
static constexpr S_max e() noexcept { return S_max(); };
static constexpr S_max init() noexcept { return S_max(); };
S_max& operator*=(const F_affine add) {
val = add.a * val + add.b;
return (*this);
}
S_max& operator*=(const S_max add) {
val = max<ll>(val, add.val);
return (*this);
}
S_max& operator&=(const S_max old) {
val = max<ll>(val, old.val);
return (*this);
}
friend S_max operator*(const S_max add, S_max s) {
s *= add;
return s;
}
};
struct S_sum {
ll val, len;
S_sum(const ll _val = 0, const ll _len = 0) : val(_val), len(_len) {}
static constexpr S_sum e() noexcept { return S_sum(); };
static constexpr S_sum init() noexcept { return S_sum(0, 1); };
S_sum& operator*=(const F_affine add) {
val = add.a * val + add.b * len;
return (*this);
}
S_sum& operator*=(const S_sum add) {
val += add.val, len += add.len;
return (*this);
}
S_sum& operator&=(const S_sum old) {
val += old.val, len += old.len;
return (*this);
}
friend S_sum operator*(const S_sum add, S_sum s) {
s *= add;
return s;
}
};
struct F_affineMOD998 {
ll a, b;
F_affineMOD998(const ll _a = 1, const ll _b = 0) : a(_a), b(_b) {}
static constexpr F_affineMOD998 id() noexcept { return F_affineMOD998(); };
F_affineMOD998 operator*=(const F_affineMOD998 add) {
a = (a * add.a) % MOD998, b = ((__int128)add.a * b + add.b) % MOD998;
return (*this);
}
};
struct S_sumMOD998 {
ll val, len;
S_sumMOD998(const ll _val = 0, const ll _len = 0) : val(_val), len(_len) {}
static constexpr S_sumMOD998 e() noexcept { return S_sumMOD998(); };
static constexpr S_sumMOD998 init() noexcept { return S_sumMOD998(0, 1); };
S_sumMOD998& operator*=(const F_affineMOD998 add) {
val = ((__int128)add.a * val + (__int128)add.b * len) % MOD998;
return (*this);
}
S_sumMOD998& operator*=(const S_sumMOD998 add) {
val += add.val, val -= MOD998 & -(val >= MOD998);
len += add.len, len -= MOD998 & -(len >= MOD998);
return (*this);
}
S_sumMOD998& operator&=(const S_sumMOD998 old) {
val += old.val, val -= MOD998 & -(val >= MOD998);
len += old.len, len -= MOD998 & -(len >= MOD998);
return (*this);
}
friend S_sumMOD998 operator*(const S_sumMOD998 add, S_sumMOD998 s) {
s *= add;
return s;
}
};
struct F_linerMOD998 {
ll n, r;
bool on;
F_linerMOD998(const ll _n = 1, const ll _r = 0, const bool _on = false) : n(_n), r(_r), on(_on) {}
static constexpr F_linerMOD998 id() noexcept { return F_linerMOD998(); };
F_linerMOD998 operator*=(const F_linerMOD998 add) {
if (add.on) {
n = add.n, r = add.r, on = true;
}
return (*this);
}
};
struct S_linerMOD998 {
ll n, r, len;
S_linerMOD998(const ll _n = 1, const ll _r = 0, const ll _len = 0) : n(_n), r(_r), len(_len) {}
static constexpr S_linerMOD998 e() noexcept { return S_linerMOD998(); };
static constexpr S_linerMOD998 init() noexcept { return S_linerMOD998(1, 0, 1); };
S_linerMOD998& operator*=(const F_linerMOD998 add) {
// dbg::zout(" | S{", n, r, len, "} *=F{", add.n, add.r, add.on, "}");
if (!add.on) return (*this);
if (len == 1 || add.n == 0) {
n = add.n;
r = add.r;
return (*this);
} else if (add.n == 1) {
n = 1;
r = (len * add.r) % MOD998;
return (*this);
}
n = modexp(add.n, len, MOD998);
ll num = ((MOD998 + 1 - modexp(add.n, len, MOD998)) * add.r) % MOD998;
ll den = MOD998 + 1 - add.n;
// dbg::zout(" | num/den=", num, den);
r = (num * modinv(den, MOD998)) % MOD998;
return (*this);
}
S_linerMOD998& operator*=(const S_linerMOD998 add) {
r = (r + (__int128)n * add.r) % MOD998, n = ((__int128)n * add.n) % MOD998;
len += add.len;
return (*this);
}
S_linerMOD998& operator&=(const S_linerMOD998 old) {
n = ((__int128)old.n * n) % MOD998, r = (old.r + (__int128)old.n * r) % MOD998;
len += old.len;
return (*this);
}
friend S_linerMOD998 operator*(const S_linerMOD998 add, S_linerMOD998 s) {
s *= add;
return s;
}
ll func(const ll x) { return ((__int128)n * x + r) % MOD998; };
};
using segtree_min = segtree<S_min>;
using segtree_max = segtree<S_max>;
using segtree_sum = segtree<S_sum>;
using segtree_sumMOD998 = segtree<S_sumMOD998>;
using segtree_linerMOD998 = segtree<S_linerMOD998>;
using lazy_segtree_min = lazy_segtree<S_min, F_affine>;
using lazy_segtree_max = lazy_segtree<S_max, F_affine>;
using lazy_segtree_sum = lazy_segtree<S_sum, F_affine>;
using lazy_segtree_sumMOD998 = lazy_segtree<S_sumMOD998, F_affineMOD998>;
using lazy_segtree_linerMOD998 = lazy_segtree<S_linerMOD998, F_linerMOD998>;
} // namespace zz_segtree
using namespace zz_segtree;
/////////////////////////////////////////////////
int main() {
// dbg::unprint = true;
ll N;
cin >> N;
vl A(N);
rep(i, N) cin >> A[i];
vl ans(N, 0), ans2(N, 0);
vl token(N, 0);
rep(i, N) {
if (token[i] == 1) continue;
ll at = i;
token[at] = 1;
ll nxt_at = A[at] - 1;
vl vec(1, at);
while (token[nxt_at] == 0) {
vec.push_back(nxt_at);
at = nxt_at;
token[at] = 1;
nxt_at = A[at] - 1;
}
vec.push_back(i);
ll M = vec.size() - 1;
set<ll> SET;
rep(j, M) {
ll E = abs(vec[j] - vec[j + 1]);
SET.emplace(E);
ans[E]++;
}
each(ite, SET) ans2[*ite]++;
// dbg::zout(i, vec);
// dbg::zout(i, SET);
// dbg::zout(i, ans);
// dbg::zout(i, ans2, "\n");
}
vl ans3(N, 0), ans4(N, 0);
cnt(i, 1, N - 1) {
ll at = i;
while (at < N) {
ans3[i] += ans[at];
ans4[i] += ans2[at];
at += i;
}
}
// dbg::zout(1, ans);
// dbg::zout(2, ans2);
// dbg::zout(3, ans3);
// dbg::zout(4, ans4);
cnt(i, 1, N - 1) cout << ans3[i] - ans4[i] << endl;
return 0;
}