結果
| 問題 | No.696 square1001 and Permutation 5 |
| コンテスト | |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2026-07-26 00:18:43 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 212 ms / 10,000 ms |
| + 316µs | |
| コード長 | 21,140 bytes |
| 記録 | |
| コンパイル時間 | 1,278 ms |
| コンパイル使用メモリ | 128,012 KB |
| 実行使用メモリ | 8,504 KB |
| 最終ジャッジ日時 | 2026-07-26 00:18:49 |
| 合計ジャッジ時間 | 3,385 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 12 |
ソースコード
#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }
#include <cassert>
#include <utility>
namespace nachia{
// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
long long x = 1, y = 0;
while(b){
long long u = a / b;
std::swap(a-=b*u, b);
std::swap(x-=y*u, y);
}
return std::make_pair(x, a);
}
} // namespace nachia
namespace nachia{
template<unsigned int MOD>
struct StaticModint{
private:
using u64 = unsigned long long;
unsigned int x;
public:
using my_type = StaticModint;
template< class Elem >
static Elem safe_mod(Elem x){
if(x < 0){
if(0 <= x+MOD) return x + MOD;
return MOD - ((-(x+MOD)-1) % MOD + 1);
}
return x % MOD;
}
StaticModint() : x(0){}
StaticModint(const my_type& a) : x(a.x){}
StaticModint& operator=(const my_type&) = default;
template< class Elem >
StaticModint(Elem v) : x(safe_mod(v)){}
unsigned int operator*() const { return x; }
my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
bool operator==(const my_type& r) const { return x == r.x; }
my_type pow(unsigned long long i) const {
my_type a = *this, res = 1;
while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
return res;
}
my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
unsigned int val() const { return x; }
int hval() const { return int(x > MOD/2 ? x - MOD : x); }
static constexpr unsigned int mod() { return MOD; }
static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};
} // namespace nachia
namespace nachia{
template<unsigned int MOD>
struct PrimitiveRoot{
using u64 = unsigned long long;
static constexpr u64 powm(u64 a, u64 i) {
u64 res = 1, aa = a;
for( ; i; i /= 2){
if(i & 1) res = res * aa % MOD;
aa = aa * aa % MOD;
}
return res;
}
static constexpr bool ExamineVal(unsigned int g){
u64 t = MOD - 1;
for(u64 d=2; d*d<=t; d+=1+(d&1)) if(t % d == 0){
if(powm(g, (MOD - 1) / d) == 1) return false;
while(t % d == 0) t /= d;
}
if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false;
return true;
}
static constexpr unsigned int GetVal(){
for(u64 x=2; x<MOD; x++) if(ExamineVal(x)) return x;
return 0;
}
static const unsigned int val = GetVal();
};
} // namespace nachia
namespace nachia {
template<class mint>
struct NttInterface{
template<class Iter>
void Butterfly(Iter, int) const {}
template<class Iter>
void IButterfly(Iter, int) const {}
template<class Iter>
void BitReversal(Iter a, int N) const {
for(int i=0, j=0; j<N; j++){
if(i < j) std::swap(a[i], a[j]);
for(int k = N>>1; k > (i^=k); k>>=1);
}
}
};
} // namespace nachia
namespace nachia{
int Popcount(unsigned long long c){
#ifdef __GNUC__
return __builtin_popcountll(c);
#else
c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
c = (c * (~0ull/257)) >> 56;
return c;
#endif
}
// please ensure x != 0
int MsbIndex(unsigned long long x){
assert(x != 0ull);
#ifdef __GNUC__
return 63 - __builtin_clzll(x);
#else
using u64 = unsigned long long;
int q = (x >> 32) ? 32 : 0;
auto m = x >> q;
constexpr u64 hi = 0x88888888;
constexpr u64 mi = 0x11111111;
m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 31;
q += (m & 0xf) << 2;
q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf;
return q;
#endif
}
// please ensure x != 0
int LsbIndex(unsigned long long x){
assert(x != 0ull);
#ifdef __GNUC__
return __builtin_ctzll(x);
#else
return MsbIndex(x & -x);
#endif
}
}
#include <iterator>
#include <array>
namespace nachia{
template <class mint>
struct NttFromAcl : NttInterface<mint> {
using u32 = unsigned int;
using u64 = unsigned long long;
static int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (u32)(n)) x++;
return x;
}
static constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
struct fft_info {
static constexpr u32 g = nachia::PrimitiveRoot<mint::mod()>::val;
static constexpr int rank2 = bsf_constexpr(mint::mod()-1);
using RootTable = std::array<mint, rank2+1>;
RootTable root, iroot, rate3, irate3;
fft_info(){
root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for(int i=rank2-1; i>=0; i--){
root[i] = root[i+1] * root[i+1];
iroot[i] = iroot[i+1] * iroot[i+1];
}
mint prod = 1, iprod = 1;
for(int i=0; i<=rank2-3; i++){
rate3[i] = root[i+3] * prod;
irate3[i] = iroot[i+3] * iprod;
prod *= iroot[i+3];
iprod *= root[i+3];
}
}
};
template<class RandomAccessIterator>
void Butterfly(RandomAccessIterator a, int n) const {
int h = ceil_pow2(n);
static const fft_info info;
int len = 0;
if((h-len)%2 == 1){
int p = 1 << (h-len-1);
for(int i=0; i<p; i++){
mint l = a[i], r = a[i+p];
a[i] = l+r; a[i+p] = l-r;
}
len++;
}
for( ; len < h; len += 2){
int p = 1 << (h-len-2);
mint rot = 1, imag = info.root[2];
u64 mod2 = u64(mint::mod()) * mint::mod();
for(int s=0; s<(1<<len); s++){
if(s) rot *= info.rate3[LsbIndex(~(u32)(s-1))];
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = (s << (h-len)) + p;
for(int i=offset-p; i<offset; i++){
u64 a0 = u64(a[i].val());
u64 a1 = u64(a[i+p].val()) * rot.val();
u64 a2 = u64(a[i+2*p].val()) * rot2.val();
u64 a3 = u64(a[i+3*p].val()) * rot3.val();
u64 a1na3imag = u64(mint(a1 + mod2 - a3).val()) * imag.val();
u64 na2 = mod2 - a2;
a[i] = a0 + a2 + a1 + a3;
a[i+1*p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i+2*p] = a0 + na2 + a1na3imag;
a[i+3*p] = a0 + na2 + (mod2 - a1na3imag);
}
}
}
}
template<class RandomAccessIterator>
void IButterfly(RandomAccessIterator a, int n) const {
int h = ceil_pow2(n);
static const fft_info info;
constexpr int MOD = mint::mod();
int len = h;
for( ; 1 < len; len -= 2){
int p = 1 << (h-len);
mint irot = 1, iimag = info.iroot[2];
for(int s=0; s<(1<<(len-2)); s++){
if(s) irot *= info.irate3[LsbIndex(~(u32)(s-1))];
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = (s << (h-len+2)) + p;
for(int i=offset-p; i<offset; i++){
u64 a0 = a[i].val();
u64 a1 = a[i+p].val();
u64 a2 = a[i+2*p].val();
u64 a3 = a[i+3*p].val();
u64 a2na3iimag = mint((a2 + MOD - a3) * iimag.val()).val();
a[i] = a0 + a1 + a2 + a3;
a[i+p] = (a0 + (MOD - a1) + a2na3iimag) * irot.val();
a[i+2*p] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val();
a[i+3*p] = (a0 + (MOD - a1) + (MOD - a2na3iimag)) * irot3.val();
}
}
}
if(len == 1){
int p = 1 << (h-len);
for(int i=0; i<p; i++){
mint l = a[i], r = a[i+p];
a[i] = l+r; a[i+p] = l-r;
}
}
}
};
} // namespace nachia
namespace nachia {
struct BigintDecMulManager {
using Int = int;
using Arr = std::vector<Int>;
using u32 = unsigned int;
using i64 = long long;
static const Int B = 1000000000;
static const u32 MOD0 = 0x1c000001;
static const u32 MOD1 = 0x6c000001;
static const u32 MOD2 = 0x78000001;
static const u32 I0_M1 = 1540148431;
static const u32 I01_M2 = 1050399624;
static const u32 I1_M2 = 10;
static const u32 IB_M1 = 1575545083;
static const u32 IB_M2 = 65929464;
template<u32 MOD>
static std::vector<u32> convMod(int z, int n, const Arr& a, const Arr& b){
using Mint = StaticModint<MOD>;
static auto ntt = NttFromAcl<Mint>();
std::vector<Mint> a2(z);
for(int i=0; i<(int)a.size(); i++) a2[i] = a[i];
std::vector<Mint> b2(z);
for(int i=0; i<(int)b.size(); i++) b2[i] = b[i];
Mint c = Mint(z).inv();
ntt.Butterfly(a2.begin(), z);
ntt.Butterfly(b2.begin(), z);
for(int i=0; i<z; i++) a2[i] *= b2[i] * c;
ntt.IButterfly(a2.begin(), z);
std::vector<u32> res(n);
for(int i=0; i<n; i++) res[i] = a2[i].val();
return res;
}
template<u32 M>
static inline StaticModint<M> SubMod(u32 a, u32 b){
return StaticModint<M>::raw(a<b ? a+M-b : a-b);
}
static Arr BigintDecMul(const Arr& a, const Arr& b){
int n = a.size() + b.size();
int n2 = 1; while(n2 < n) n2 *= 2;
auto c0 = convMod<MOD0>(n2, n-1, a, b);
auto c1 = convMod<MOD1>(n2, n-1, a, b);
auto c2 = convMod<MOD2>(n2, n-1, a, b);
std::vector<i64> c(n+1);
using MintB = StaticModint<B>;
using Mint1 = StaticModint<MOD1>;
using Mint2 = StaticModint<MOD2>;
auto i0m1 = Mint1::raw(I0_M1);
auto i01m2 = Mint2::raw(I01_M2);
auto ibm1 = Mint1::raw(IB_M1);
auto ibm2 = Mint2::raw(IB_M2);
auto i1m2 = Mint2::raw(I1_M2);
auto m01_b = MintB::raw(MOD0) * MintB(MOD1);
for(int i=0; i<n-1; i++){
u32 d0to1 = (i0m1 * SubMod<MOD1>(c1[i], c0[i])).val();
Mint2 x01m2 = Mint2::raw(c0[i]) + Mint2::raw(MOD0) * Mint2::raw(d0to1);
MintB x01mB = MintB::raw(c0[i]) + MintB::raw(MOD0) * MintB(d0to1);
MintB xmB = x01mB + m01_b * MintB((i01m2 * SubMod<MOD2>(c2[i], x01m2.val())).val());
c[i] += xmB.val();
Mint1 y1 = SubMod<MOD1>(c1[i], xmB.val()) * ibm1;
Mint2 y2 = SubMod<MOD2>(c2[i], xmB.val()) * ibm2;
i64 y12 = (i64)y1.val() + (i64)MOD1 * (i64)(i1m2 * SubMod<MOD2>(y2.val(), y1.val())).val();
c[i+1] += y12 % B; c[i+2] += y12 / B;
}
Arr res(n);
for(int i=0; i<n; i++){
res[i] = c[i]%B;
c[i+1] += c[i]/B;
}
if(res.back() == 0) res.pop_back();
return res;
}
};
};
namespace nachia {
struct BigintDec{
using Int = int;
using Arr = std::vector<Int>;
BigintDec() : sign(0), A(0) {}
BigintDec(int z){
if(z == 0){ sign = 0; }
else if(z < 0){ sign = -1; A = Arr(1, -z); }
else{ sign = 1; A = Arr(1, z); }
}
BigintDec(const std::string& s) : sign(1) {
auto it = s.begin();
if(it != s.end()){
if(*it == '-'){ sign = -1; it++; }
else if(*it == '+'){ it++; }
}
while(it != s.end() && *it == '0') it++;
if(it == s.end()){ sign = 0; }
else {
auto f = (s.end() - it);
int e = int((f-1) / 9);
int d = int((f-1) % 9);
A.assign(e + 1, 0);
for( ; it!=s.end(); it++){
assert('0' <= *it && *it <= '9');
A[e] = A[e] * 10 + (*it - '0');
d--; if(d < 0){ d = 8; e -= 1; }
}
}
}
BigintDec operator+(const BigintDec& r) const {
if(r.isZero()) return *this;
if(isZero()) return r;
auto x = (sign == r.sign) ?
uintSum(*this, r) : uintDiff(*this, r);
x.sign *= sign;
return x;
}
BigintDec operator-() const { return raw(-sign, A); }
BigintDec operator-(const BigintDec& r) const {
if(r.isZero()) return *this;
if(isZero()) return -r;
auto x = (sign == r.sign) ?
uintDiff(*this, r) : uintSum(*this, r);
x.sign *= sign;
return x;
}
BigintDec operator*(const BigintDec& r) const {
if(isZero() || r.isZero()) return Zero();
return raw(sign * r.sign, uintMul(*this, r));
}
std::pair<BigintDec, BigintDec> divrem(const BigintDec& r) const {
assert(!r.isZero());
if(isZero() || CmpAbs(*this, r) == 1) return { Zero(), *this };
auto invr = r.invFlex(len()+1);
auto a2 = (*this * invr).shiftRight(len() + r.len() + 2);
a2.sign = sign * r.sign;
auto rem = (*this) - (r * a2);
if(CmpAbs(r, rem) >= 0){
rem = rem - r;
a2 = a2 + BigintDec("1");
}
return std::make_pair(std::move(a2), std::move(rem));
}
BigintDec operator/(const BigintDec& r){
assert(!r.isZero());
return divrem(r).first;
}
BigintDec& operator*=(int x){
if(x == 0) return (*this) = Zero();
i64 y = std::abs(x);
i64 c = 0;
for(int i=0; i<len(); i++){
c += A[i] * y;
A[i] = c % B; c /= B;
}
if(c >= B){ A.push_back(c % B); c /= B; }
if(c) A.push_back(c);
if(x < 0) sign = -sign;
return *this;
}
static BigintDec Zero(){ return BigintDec(); }
bool isZero() const { return sign == 0; }
std::string toString() const {
if(isZero()) return "0";
std::string s;
for(int i=0; i<len()-1; i++){
int a = A[i];
for(int d=0; d<9; d++){ s.push_back('0'+a%10); a /= 10; }
}
for(Int a=A[len()-1]; a!=0; a/=10) s.push_back('0'+a%10);
if(sign < 0) s.push_back('-');
std::reverse(s.begin(), s.end());
return s;
}
bool operator<(const BigintDec& r) const {
if(sign != r.sign) return sign < r.sign;
return CmpAbs(*this, r) == sign;
}
bool operator>(const BigintDec& r) const { return r < *this; }
bool operator<=(const BigintDec& r) const { return !(r < *this); }
bool operator>=(const BigintDec& r) const { return !(*this < r); }
bool operator==(const BigintDec& r) const { return sign == r.sign && A == r.A; }
bool operator!=(const BigintDec& r) const { return !(*this == r); }
private:
using Self = BigintDec;
using i64 = long long;
int sign;
std::vector<Int> A;
static const int B = 1000000000;
int len() const { return int(A.size()); }
Int dig(int z) const { return z < len() ? A[z] : 0; }
Int& operator[](int z){ return A[z]; }
const Int& operator[](int z) const { return A[z]; }
static int CmpUintPos(const Self& l, const Self& r){
if(l.len() != r.len()) return std::max(l.len(), r.len()) - 1;
for(int i=l.len()-1; i>=0; i--) if(l[i] != r[i]) return i;
return -1;
}
static int CmpAbs(const Self& l, const Self& r){
int k = CmpUintPos(l, r);
if(k < 0) return 0;
return l.dig(k) < r.dig(k) ? 1 : -1;
}
static Self raw(int sign, Arr a){
if(a.empty()) sign = 0;
while(!a.empty() && a.back() == 0) a.pop_back();
Self res; res.sign = sign; res.A = std::move(a);
return res;
}
static Self uintDiff2(const Self& l, const Self& r, int k){
Arr A(k + 1);
for(int i=0; i<=k; i++) A[i] = l[i];
int j = std::min(k+1, r.len());
Int v = 0;
for(int i=0; i<j; i++){
v = v + A[i] - r[i];
if(v < 0){ A[i] = v + B; v = -1; }
else { A[i] = v; v = 0; }
}
for(int i=j; v!=0; i++){
v = v + A[i];
if(v < 0){ A[i] = v + B; v = -1; }
else { A[i] = v; v = 0; }
}
return raw(1, std::move(A));
}
static Self uintDiff(const Self& l, const Self& r){
int k = CmpUintPos(l, r);
if(k == -1) return Zero();
if(l.dig(k) > r.dig(k)) return uintDiff2(l, r, k);
auto x = uintDiff2(r, l, k); x.sign = -x.sign;
return x;
}
static Self uintSum(const Self& l, const Self& r){
if(l.len() > r.len()) return uintSum(r, l);
Arr A(r.len() + 1);
for(int i=0; i<l.len(); i++) A[i] = l[i];
Int v = 0;
for(int i=0; i<r.len(); i++){
v = v + A[i] + r[i];
if(B <= v){ A[i] = v - B; v = 1; }
else { A[i] = v; v = 0; }
}
if(v != 0) A[r.len()] = v; else A.pop_back();
return raw(1, std::move(A));
}
static Arr uintMul(const Self& l, const Self& r){
if(l.len() >= 30 && r.len() >= 30){
return BigintDecMulManager::BigintDecMul(l.A, r.A);
}
int z = l.len() + r.len();
Arr a(z);
for(int i=0; i<l.len(); i++) for(int j=0; j<r.len(); j++){
i64 x = (i64)(l[i]) * r[j] + a[i+j];
a[i+j] = x % B; a[i+j+1] += x / B;
}
if(a.back() == 0) a.pop_back();
return a;
}
Self shiftLeft(int delta) const {
if(isZero()) return Zero();
Arr a(len() + delta);
for(int i=0; i<len(); i++) a[i+delta] = A[i];
return raw(sign, std::move(a));
}
Self shiftRight(int delta) const {
if(len() <= delta) return Zero();
Arr a(len() - delta);
for(int i=delta; i<len(); i++) a[i-delta] = A[i];
return raw(sign, std::move(a));
}
Self shiftToLength(int tg) const {
return len() < tg ? shiftLeft(tg - len())
: shiftRight(len() - tg);
}
void negate(){ sign = -sign; }
Self invFlex(int prec) const {
Int t = B / (A[len()-1] + 1);
auto a2 = *this; a2 *= t;
auto b2 = a2.invPrec(prec);
b2 *= t;
return b2;
}
Self invPrec(int prec){
if(prec == 1){
Int b = A[len()-1];
Arr a(3); a[2] = 1; a[1] = i64(B) * B / b - B;
return raw(sign, std::move(a));
}
int subp = (prec + 1) / 2;
auto b = invPrec(subp);
auto ab = (shiftToLength(prec+1) * b).shiftRight(subp+1);
auto ab2 = Self("2").shiftLeft(prec+1) - ab;
return (ab2 * b).shiftRight(subp + 1);
}
};
}
namespace {
std::istream& operator>>(std::istream& i, nachia::BigintDec& d){
std::string s; i >> s;
d = nachia::BigintDec(s);
return i;
}
std::ostream& operator<<(std::ostream& o, const nachia::BigintDec& d){
return o << d.toString();
}
}
namespace nachia {
template <class T> struct FenwickTree {
public:
FenwickTree() : _n(0){}
explicit FenwickTree(int n, T ZERO = T(0)) : _n(n), a(n, ZERO){}
void add(int p, T x){
assert(0 <= p && p < _n);
p++;
while(p <= _n){
a[p-1] += T(x);
p += p & -p;
}
}
T sum(int r){
return sumr(r);
}
T sum(int l, int r){
return sumr(r) - sumr(l);
}
private:
int _n;
std::vector<T> a;
T sumr(int r){
T s = 0;
while(r > 0){
s += a[r-1];
r -= r & -r;
}
return s;
}
};
} // namespace nachia
namespace nachia {
template<class T> using PointAddRangeSumFwt = FenwickTree<T>;
} // namespace nachia
using Int = nachia::BigintDec;
void testcase(){
ll N; cin >> N;
V<ll> P(N); REP(i,N){ cin >> P[i]; P[i]--; }
nachia::PointAddRangeSumFwt<ll> ds(N);
V<ll> A(N);
REP(i,N){
A[i] = P[i] - ds.sum(0, P[i]);
ds.add(P[i], 1);
}
auto dfs = [&](auto& dfs, ll l, ll r) -> pair<Int, Int> {
if(l + 1 == r) return { Int(A[l]), Int(N-l) };
ll m = (l + r) / 2;
auto [al, bl] = dfs(dfs, l, m);
auto [ar, br] = dfs(dfs, m, r);
return { al * br + ar, bl * br };
};
cout << (dfs(dfs, 0, N).first + 1).toString() << "\n";
}
int main(){
cin.tie(0)->sync_with_stdio(0);
testcase();
return 0;
}