#260670 (C++14) No.696 square1001 and Permutation 5

提出ソース

結果

問題	No.696 square1001 and Permutation 5
ユーザー	square1001
提出日時	2018-05-26 20:48:38
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA (最新) AC (最初)
実行時間	-
コード長	7,940 bytes
コンパイル時間	1,082 ms
コンパイル使用メモリ	86,328 KB
実行使用メモリ	42,720 KB
最終ジャッジ日時	2024-06-30 07:17:59
合計ジャッジ時間	10,403 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	WA	-
testcase_01	AC	15 ms 16,000 KB
testcase_02	AC	15 ms 15,960 KB
testcase_03	AC	18 ms 16,000 KB
testcase_04	AC	21 ms 16,000 KB
testcase_05	AC	27 ms 16,236 KB
testcase_06	AC	50 ms 16,576 KB
testcase_07	AC	93 ms 17,104 KB
testcase_08	AC	248 ms 19,172 KB
testcase_09	AC	804 ms 28,084 KB
testcase_10	AC	1,785 ms 42,612 KB
testcase_11	AC	1,718 ms 35,344 KB
testcase_12	AC	16 ms 16,000 KB
testcase_13	AC	15 ms 15,872 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifndef ___CLASS_BIGINT
#define ___CLASS_BIGINT

// +----------------------------------
// | BigInteger Library Version 2.0
// | Author: square1001 (+ E869120)
// | Date: July 24th, 2016
// | Last Revision: May 24th, 2018
// | Language: C++11 / C++14
// +---------------------------------

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

typedef __uint128_t unsigned128;

template <uint32_t mod> class modint {
	// Assertion: mod < 2^31
private:
	uint32_t n;
	static const int shifts = 62;
	static const uint64_t multiplier = (1ull << shifts) / mod;
public:
	modint() : n(0) {};
	modint(uint32_t n_) : n(n_) {};
	modint& operator=(const uint32_t x) { n = x; return *this; }
	modint& operator+=(const modint& x) { n = (n + x.n < mod ? n + x.n : n + x.n - mod); return *this; }
	modint& operator-=(const modint& x) { n = (mod + n - x.n < mod ? mod + n - x.n : n - x.n); return *this; }
	modint& operator*=(const modint& x) {
		uint64_t w = 1ull * n * x.n;
		w -= (uint64_t)((unsigned128(w) * multiplier) >> shifts) * mod;
		n = (w < mod ? w : w - mod);
		return *this;
	}
	modint operator+(const modint& x) const { return modint(*this) += x; }
	modint operator-(const modint& x) const { return modint(*this) -= x; }
	modint operator*(const modint& x) const { return modint(*this) *= x; }
	int get() const { return n; }
};

class bigint {
private:
	int size_;
	std::vector<int> arr;
	void resize(int target) {
		size_ = target;
		arr.resize(size_);
	}
public:
	static const int maxdigit = 4; // maxdigit <= 4
	static const int maxvalue = 10000; // maxvalue = 10^maxdigit
	bigint() : size_(1), arr(std::vector<int>({ 0 })) {};
	bigint(const std::string& s) {
		size_ = 1;
		while (size_ < (s.size() + maxdigit - 1) / maxdigit) size_ <<= 1;
		arr = std::vector<int>(size_, 0);
		for (int i = s.size() - 1; i >= 0; --i) {
			arr[i / maxdigit] = arr[i / maxdigit] * 10 + (s[s.size() - i - 1] - '0');
		}
	}
	bigint(long long x) {
		(*this) = x;
	}
	bigint(const bigint& x) {
		(*this) = x;
	}
	int size() const {
		return size_;
	}
	int digit() const {
		for (int i = size_ - 1; i >= 0; --i) {
			if (arr[i] != 0) continue;
			int mul = 1;
			for (int j = 0; j < maxdigit; ++j) {
				mul *= 10;
				if (arr[j] < mul) return maxdigit * i + j;
			}
		}
		return 1; // exception to val = 0
	}
	std::string to_string() const {
		std::string ret(size_ * maxdigit, '-');
		int mx = 0;
		for (int i = 0; i < size_; ++i) {
			int x = arr[i];
			for (int j = 0; j < maxdigit; ++j) {
				if (x % 10 != 0) mx = i * maxdigit + j;
				ret[size_ * maxdigit - i * maxdigit - j - 1] = x % 10 + '0';
				x /= 10;
			}
		}
		return ret.substr(size_ * maxdigit - mx - 1);
	}
	bigint& operator=(const long long x) {
		long long subx = x;
		int usesize = 0;
		while (subx > 0) subx /= maxvalue, usesize++;
		size_ = 1;
		while (size_ < usesize) size_ <<= 1;
		arr = std::vector<int>(size_, 0);
		subx = x;
		for (int i = 0; i < size_; ++i) {
			arr[i] = subx % maxvalue;
			subx /= maxvalue;
		}
		return *this;
	}
	bigint& operator+=(const bigint& x) {
		// Time complexity: linear
		if (x.size_ > size_) resize(x.size_);
		int carry = 0;
		for (int i = 0; i < x.size_; ++i) {
			if ((arr[i] += x.arr[i] + carry) >= maxvalue) arr[i] -= maxvalue, carry = 1;
			else carry = 0;
		}
		if (carry == 1) resize(size_ << 1), arr[size_ >> 1] = 1;
		return *this;
	}
	bigint& operator-=(const bigint& x) {
		// Time complexity: linear
		// Assertion: this >= x. Runtime error's possible if this < x
		int carry = 0, mx = 1;
		for (int i = 0; i < size_; ++i) {
			if ((arr[i] -= (i < x.size_ ? x.arr[i] : 0) + carry) < 0) arr[i] += maxvalue, carry = 1;
			while (arr[i] != 0 && mx < i + 1) mx *= 2;
		}
		if (mx != size_) resize(mx);
		return *this;
	}
	bigint& operator*=(const bigint& x) {
		// Time complexity: linearithmic
		// Assertion: mod1 <= mod2
		const int mod1 = 167772161, root1 = 3;
		const int mod2 = 469762049, root2 = 3;
		int magic = 104391568; // = binpow(mod1, mod2 - 2, mod2);
		resize(std::max(size_, x.size_) * 2);
		std::vector<modint<mod1> > a1(size_), x1(size_);
		std::vector<modint<mod2> > a2(size_), x2(size_);
		for (int i = 0; i < size_; ++i) a1[i] = arr[i], a2[i] = arr[i];
		for (int i = 0; i < x.size_; ++i) x1[i] = x.arr[i], x2[i] = x.arr[i];
		fourier_transform(size_, a1, root1, false);
		fourier_transform(size_, a2, root2, false);
		fourier_transform(size_, x1, root1, false);
		fourier_transform(size_, x2, root2, false);
		for (int i = 0; i < size_; ++i) a1[i] *= x1[i], a2[i] *= x2[i];
		fourier_transform(size_, a1, root1, true);
		fourier_transform(size_, a2, root2, true);
		long long carry = 0; int mx = 1;
		for (int i = 0; i < size_; ++i) {
			long long val = 1LL * (a2[i].get() - a1[i].get() + mod2) * magic % mod2 * mod1 + a1[i].get();
			arr[i] = (val + carry) % maxvalue;
			carry = (val + carry) / maxvalue;
			while (arr[i] != 0 && mx < i + 1) mx *= 2;
		}
		if (mx != size_) resize(mx);
		return *this;
	}
	friend bool operator<(const bigint& x1, const bigint& x2) {
		if (x1.size_ != x2.size_) return x1.size_ < x2.size_;
		for (int i = x1.size_ - 1; i >= 0; --i) {
			if (x1.arr[i] != x2.arr[i]) return x1.arr[i] < x2.arr[i];
		}
		return false;
	}
	friend bool operator>(const bigint& x1, const bigint& x2) {
		return x2 < x1;
	}
	friend bool operator<=(const bigint& x1, const bigint& x2) {
		return !(x1 > x2);
	}
	friend bool operator>=(const bigint& x1, const bigint& x2) {
		return !(x1 < x2);
	}
	friend bool operator==(const bigint& x1, const bigint& x2) {
		return !(x1 < x2 || x1 > x2);
	}
	friend bool operator!=(const bigint& x1, const bigint& x2) {
		return x1 < x2 || x1 > x2;
	}
	friend bigint operator+(const bigint& x1, const bigint& x2) {
		bigint res = x1;
		res += x2;
		return res;
	}
	friend bigint operator-(const bigint& x1, const bigint& x2) {
		bigint res = x1;
		return res -= x2;
	}
	friend bigint operator*(const bigint& x1, const bigint& x2) {
		bigint res = x1;
		res *= x2;
		return res;
	}
	friend std::istream& operator >> (std::istream& is, bigint& x) {
		std::string s;
		is >> s;
		x = bigint(s);
		return is;
	}
	friend std::ostream& operator<<(std::ostream& os, const bigint& x) {
		os << x.to_string();
		return os;
	}
	int binpow(int a, int b, int mod) {
		int ret = 1;
		while (b) {
			if (b & 1) ret = 1LL * ret * a % mod;
			a = 1LL * a * a % mod;
			b >>= 1;
		}
		return ret;
	}
	template <unsigned mod> void fourier_transform(int sz, std::vector<modint<mod> >& f, int primitive_root, bool inverse) {
		// O(n log n) Number Theoretic Transform
		for (int i = 0, j = 1; j < sz - 1; ++j) {
			for (int k = sz >> 1; k >(i ^= k); k >>= 1);
			if (i < j) std::swap(f[i], f[j]);
		}
		modint<mod> root = binpow(primitive_root, (mod - 1) / sz, mod);
		std::vector<modint<mod> > pw(sz + 1); pw[0] = 1;
		for (int i = 1; i <= sz; i++) pw[i] = pw[i - 1] * root;
		for (int b = 1; b < sz; b <<= 1) {
			int qs = sz / (b * 2);
			for (int i = 0; i < sz; i += b * 2) {
				for (int j = i; j < i + b; ++j) {
					modint<mod> nf = pw[(inverse ? b * 2 - j + i : j - i) * qs] * f[j + b];
					f[j + b] = f[j] - nf;
					f[j] += nf;
				}
			}
		}
		if (inverse) {
			modint<mod> mul = binpow(sz, mod - 2, mod);
			for (int i = 0; i < sz; ++i) f[i] *= mul;
		}
	}
};

#endif

#include <iostream>
#include <algorithm>
using namespace std;
int n, p[100009], bit[100009]; bigint a[100009], b[100009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i];
	for (int i = n - 1; i >= 0; i--) {
		int x = 0;
		for (int j = p[i] - 1; j >= 1; j -= j & (-j)) x += bit[j];
		for (int j = p[i]; j < n; j += j & (-j)) bit[j]++;
		a[n - i - 1] = x;
		b[i] = i + 1;
	}
	int s = 1;
	while (2 << s < n) s++;
	for (int i = 0; i <= s; i++) {
		for (int j = 0; j + (1 << i) < n; j += (2 << i)) {
			bigint c = b[j] * a[j + (1 << i)];
			a[j] += c;
			b[j] *= b[j + (1 << i)];
		}
	}
	cout << a[0] + 1 << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード