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

提出ソース
結果

問題	No.696 square1001 and Permutation 5
ユーザー	square1001
提出日時	2022-08-20 13:47:36
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	459 ms / 10,000 ms
コード長	15,604 bytes
コンパイル時間	1,945 ms
コンパイル使用メモリ	100,760 KB
実行使用メモリ	55,404 KB
最終ジャッジ日時	2024-10-09 06:41:24
合計ジャッジ時間	4,985 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	455 ms 55,404 KB
testcase_01	AC	3 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	3 ms 5,248 KB
testcase_04	AC	3 ms 5,248 KB
testcase_05	AC	6 ms 5,248 KB
testcase_06	AC	14 ms 5,248 KB
testcase_07	AC	30 ms 7,424 KB
testcase_08	AC	69 ms 12,176 KB
testcase_09	AC	212 ms 27,796 KB
testcase_10	AC	459 ms 55,392 KB
testcase_11	AC	304 ms 46,304 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma GCC optimize("O3")

#ifndef NAMESPACE_CONVOLUTION
#define NAMESPACE_CONVOLUTION

#include <cstdint>
#include <algorithm>

namespace convolution {
	/*
		MODINT CLASS FOR DOING NUMBER THEORETIC TRANSFORM (NTT)
		- arrays of 4 different mod-integers
		- works well with compiler option -O3, because it optimizes for MOD[i] = a * 2^k + 1 for small a
		  * MOD[i]: mod values
		  * GARNER[i]: equals MOD[s]^-1 (mod MOD[t]), for (s, t) = (0, 1), (0, 2), (1, 2), (0, 3), (1, 3), (2, 3)
		
		BENCHMARK (2022.8.19)
		- AtCoder: 4.148 seconds for 10^9 multiplications with -O3
		- ideone.com: 3.204 seconds for 5*10^8 multiplications with -O3
	*/
	class ntt_modint {
	public:
		alignas(32) std::int64_t x[4];
		alignas(32) static constexpr std::int64_t MOD[4] = {
			(51LL << 25) + 1LL, (54LL << 25) + 1LL, (60LL << 25) + 1LL, (63LL << 25) + 1LL
		};
		alignas(32) static constexpr std::int64_t GARNER[6] = {
			18LL,
			(5LL << 27) + 7LL, 10LL,
			(189LL << 23) + 6LL, 7LL, 21LL
		};
		explicit ntt_modint() {
			x[0] = 0LL; x[1] = 0LL; x[2] = 0LL; x[3] = 0LL;
		}
		explicit ntt_modint(std::int64_t x0_, std::int64_t x1_, std::int64_t x2_, std::int64_t x3_) {
			x[0] = x0_; x[1] = x1_; x[2] = x2_; x[3] = x3_;
			for (int i = 0; i < 4; i++) {
				x[i] = (x[i] >= 0 ? x[i] % MOD[i] : (MOD[i] - (-x[i] % MOD[i]))) % MOD[i];
			}
		}
		ntt_modint& operator+=(const ntt_modint& m) {
			for (int i = 0; i < 4; i++) {
				x[i] += m.x[i];
				x[i] -= (x[i] >= MOD[i] ? MOD[i] : 0LL);
			}
			return (*this);
		}
		ntt_modint& operator-=(const ntt_modint& m) {
			for (int i = 0; i < 4; i++) {
				x[i] -= m.x[i];
				x[i] += (x[i] < 0LL ? MOD[i] : 0LL);
			}
			return (*this);
		}
		ntt_modint& operator*=(const ntt_modint& m) {
			for (int i = 0; i < 4; i++) {
				x[i] = x[i] * m.x[i] % MOD[i];
			}
			return (*this);
		}
		ntt_modint operator+(const ntt_modint& m) const {
			return ntt_modint(*this) += m;
		}
		ntt_modint operator-(const ntt_modint& m) const {
			return ntt_modint(*this) -= m;
		}
		ntt_modint operator*(const ntt_modint& m) const {
			return ntt_modint(*this) *= m;
		}
		__int128_t get() const {
			std::int64_t v[4];
			int idx = 0;
			for (int i = 0; i < 4; i++) {
				v[i] = x[i];
				for (int j = 0; j < i; j++) {
					v[i] = GARNER[idx++] * (v[i] - v[j] + MOD[i]) % MOD[i];
				}
			}
			__int128_t res = v[0];
			__int128_t mul = 1;
			for (int i = 0; i < 3; i++) {
				mul *= MOD[i];
				res += v[i + 1] * mul;
			}
			return res;
		}
	};
	constexpr std::int64_t ntt_modint::MOD[4];
	constexpr std::int64_t ntt_modint::GARNER[6];
	
	/*
		FUNCTION FOR NUMBER-THEORETIC TRANSFORM - FORWARD DIRECTION
		- do NTT in forward direction for an array x of size (1 << level)
	*/
	void forward_ntt(int level, ntt_modint* x) {
		ntt_modint f[25];
		f[23] = ntt_modint(40, 103, 170, 551); // 2^25-th root for each mod (note: 23 = 25 - 2)
		for (int i = 22; i >= 0; i--) {
			f[i] = f[i + 1] * f[i + 1];
		}
		for (int i = 0; i <= 23; i++) {
			f[i] *= ntt_modint(-1, -1, -1, -1);
		}
		int s = (1 << level);
		for (int i = level - 1; i >= 0; i--) {
			ntt_modint mult(1, 1, 1, 1);
			for (int j = 0; j < s; j += (2 << i)) {
				for (int k = j; k < j + (1 << i); k++) {
					ntt_modint xl = x[k];
					ntt_modint xr = x[k + (1 << i)];
					x[k] = xl + mult * xr;
					x[k + (1 << i)] = xl - mult * xr;
				}
				mult *= f[__builtin_ctz(~(j >> (i + 1)))];
			}
		}
	}
	
	/*
		FUNCTION FOR NUMBER-THEORETIC TRANSFORM - REVERSE DIRECTION
		- do NTT in reverse direction for an array x of size (1 << level)
	*/
	void reverse_ntt(int level, ntt_modint* x) {
		ntt_modint f[25];
		f[23] = ntt_modint(983983719, 1213823434, 698721702, 1392661172); // inverse of 2^25-th root for each mod (note: 23 = 25 - 2)
		for (int i = 22; i >= 0; i--) {
			f[i] = f[i + 1] * f[i + 1];
		}
		for (int i = 0; i <= 23; i++) {
			f[i] *= ntt_modint(-1, -1, -1, -1);
		}
		int s = (1 << level);
		for (int i = 0; i < level; i++) {
			ntt_modint mult(1, 1, 1, 1);
			for (int j = 0; j < s; j += (2 << i)) {
				for (int k = j; k < j + (1 << i); k++) {
					ntt_modint xl = x[k];
					ntt_modint xr = x[k + (1 << i)];
					x[k] = xl + xr;
					x[k + (1 << i)] = (xl - xr) * mult;
				}
				mult *= f[__builtin_ctz(~(j >> (i + 1)))];
			}
		}
		ntt_modint inv2 = ntt_modint((ntt_modint::MOD[0] + 1) / 2, (ntt_modint::MOD[1] + 1) / 2, (ntt_modint::MOD[2] + 1) / 2, (ntt_modint::MOD[3] + 1) / 2);
		ntt_modint powinv(1, 1, 1, 1);
		for (int i = 0; i < level; i++) {
			powinv *= inv2;
		}
		for (int i = 0; i < s; i++) {
			x[i] *= powinv;
		}
	}
	
	/*
		FUNCTION FOR CONVOLUTION
		- convolves two arrays a and b, and returns the output in array c
		  * sa = (size of array a)
		  * sb = (size of array b)
		  * outputs the array c of size sa+sb-1
		- works for 0 <= c[i] < 13196394894239664472536019622531432449 (~ 1.32 * 10^37)
	*/
	void convolve(int sa, int sb, std::int64_t *a, std::int64_t *b, __int128_t *c) {
		if (sa < sb) {
			std::swap(sa, sb);
			std::swap(a, b);
		}
		if (sb <= 48) {
			ntt_modint *va = new ntt_modint[sa];
			ntt_modint *vb = new ntt_modint[sb];
			ntt_modint *vc = new ntt_modint[sa + sb - 1];
			for (int i = 0; i < sa; i++) {
				va[i] = ntt_modint(a[i], a[i], a[i], a[i]);
			}
			for (int i = 0; i < sb; i++) {
				vb[i] = ntt_modint(b[i], b[i], b[i], b[i]);
			}
			for (int i = 0; i < sa; i++) {
				for (int j = 0; j < sb; j++) {
					vc[i + j] += va[i] * vb[j];
				}
			}
			for (int i = 0; i < sa + sb - 1; i++) {
				c[i] = vc[i].get();
			}
			delete[] va;
			delete[] vb;
			delete[] vc;
		}
		else {
			for (int i = 0; i < sa + sb - 1; i++) {
				c[i] = 0;
			}
			int level = 0;
			while ((1 << level) < sb) {
				level += 1;
			}
			ntt_modint *va = new ntt_modint[2 << level];
			ntt_modint *vb = new ntt_modint[2 << level];
			for (int i = 0; i < sb; i++) {
				vb[i] = ntt_modint(b[i], b[i], b[i], b[i]);
			}
			forward_ntt(level + 1, vb);
			for (int i = 0; i < sa; i += (1 << level)) {
				int limit = std::min(sa - i, 1 << level);
				for (int j = 0; j < limit; j++) {
					va[j] = ntt_modint(a[i + j], a[i + j], a[i + j], a[i + j]);
				}
				for (int j = limit; j < (2 << level); j++) {
					va[j] = ntt_modint();
				}
				forward_ntt(level + 1, va);
				for (int j = 0; j < (2 << level); j++) {
					va[j] *= vb[j];
				}
				reverse_ntt(level + 1, va);
				for (int j = 0; j < limit + sb - 1; j++) {
					c[i + j] += va[j].get();
				}
			}
			delete[] va;
			delete[] vb;
		}
	}
}

#endif // NAMESPACE_CONVOLUTION

#ifndef CLASS_BASIC_INTEGER
#define CLASS_BASIC_INTEGER

#include <cstdint>
#include <algorithm>

class basic_integer {
public:
	static constexpr int BASE_DIGITS = 14;
	static constexpr std::int64_t BASE = 100'000'000'000'000LL;
	int size_;
	int capacity_;
	std::int64_t *x;
	// constructor #1: default constructor, set value = 0
	basic_integer() : size_(1), capacity_(1) {
		x = new std::int64_t[1];
		x[0] = std::int64_t(0);
	}
	// constructor #2: copy constructor
	basic_integer(const basic_integer& b) : size_(b.size_), capacity_(b.capacity_) {
		x = new std::int64_t[capacity_];
		for (int i = 0; i < capacity_; i++) {
			x[i] = b.x[i];
		}
	}
	// copy operator
	basic_integer& operator=(const basic_integer& b) {
		size_ = b.size_;
		capacity_ = b.capacity_;
		delete[] x;
		x = new std::int64_t[capacity_];
		for (int i = 0; i < capacity_; i++) {
			x[i] = b.x[i];
		}
		return (*this);
	}
	// destructor
	~basic_integer() {
		delete[] x;
	}
	// root function #1: change capacity
	void change_capacity(int new_capacity_) {
		if (capacity_ == new_capacity_) {
			return;
		}
		int limit = std::min(capacity_, new_capacity_);
		std::int64_t *tx = new std::int64_t[limit];
		for (int i = 0; i < limit; i++) {
			tx[i] = x[i];
		}
		delete[] x;
		x = new std::int64_t[new_capacity_];
		for (int i = 0; i < limit; i++) {
			x[i] = tx[i];
		}
		delete[] tx;
		for (int i = limit; i < new_capacity_; i++) {
			x[i] = 0LL;
		}
		capacity_ = new_capacity_;
	}
	// root function #2: digits(), returns the number of digits
	int digits() const {
		std::int64_t v = x[size_ - 1];
		int digit = 0;
		do {
			digit += 1;
			v /= 10;
		} while (v != 0LL);
		return digit + (size_ - 1) * BASE_DIGITS;
	}
	// root function #3. comparison function
	int compare(const basic_integer& b) const {
		// if self < b, returns -1
		// if self == b, returns 0
		// if self > b, returns +1
		if (size_ != b.size_) {
			return (size_ < b.size_ ? -1 : +1);
		}
		for (int i = size_ - 1; i >= 0; i--) {
			if (x[i] != b.x[i]) {
				return (x[i] < b.x[i] ? -1 : +1);
			}
		}
		return 0;
	}
	// operator #1. += operator
	basic_integer& operator+=(const basic_integer& b) {
		change_capacity(std::max(capacity_, b.capacity_));
		for (int i = 0; i < b.size_; i++) {
			x[i] += b.x[i];
		}
		size_ = std::max(size_, b.size_);
		for (int i = 0; i < size_ - 1; i++) {
			if (x[i] >= BASE) {
				x[i] -= BASE;
				x[i + 1] += 1;
			}
			else if (i >= b.size_) {
				break;
			}
		}
		if (x[size_ - 1] >= BASE) {
			if (size_ == capacity_) {
				change_capacity(capacity_ * 2);
			}
			x[size_ - 1] -= BASE;
			x[size_] += 1;
			size_ += 1;
		}
		return (*this);
	}
	// operator #2. -= operator
	basic_integer& operator-=(const basic_integer& b) {
		for (int i = 0; i < b.size_; i++) {
			x[i] -= b.x[i];
		}
		for (int i = 0; i < size_; i++) {
			if (x[i] < 0) {
				x[i] += BASE;
				x[i + 1] -= 1;
			}
			else if (i >= b.size_) {
				break;
			}
		}
		while (size_ >= 2 && x[size_ - 1] == 0) {
			size_ -= 1;
		}
		int new_capacity_ = capacity_;
		while (size_ <= new_capacity_ / 2) {
			new_capacity_ /= 2;
		}
		change_capacity(new_capacity_);
		return (*this);
	}
	// operator #3. *= operator
	basic_integer& operator*=(const basic_integer& b) {
		__int128_t *c = new __int128_t[size_ + b.size_ - 1];
		convolution::convolve(size_, b.size_, x, b.x, c);
		int new_size_ = size_ + b.size_;
		int new_capacity_ = std::max(capacity_, b.capacity_);
		if (new_size_ > new_capacity_) {
			new_capacity_ *= 2;
		}
		change_capacity(new_capacity_);
		__int128_t carry = 0;
		for (int i = 0; i < size_ + b.size_ - 1; i++) {
			carry += c[i];
			x[i] = carry % BASE;
			carry /= BASE;
		}
		x[size_ + b.size_ - 1] = carry;
		while (new_size_ >= 2 && x[new_size_ - 1] == 0) {
			new_size_ -= 1;
		}
		size_ = new_size_;
		while (size_ <= new_capacity_ / 2) {
			new_capacity_ /= 2;
		}
		change_capacity(new_capacity_);
		return (*this);
	}
};

#endif // CLASS_BASIC_INTEGER

#ifndef CLASS_BIG_INTEGER
#define CLASS_BIG_INTEGER

#include <string>
#include <algorithm>
#include <stdexcept>

class big_integer {
private:
	basic_integer content;
	bool negative;
public:
	big_integer() : content(basic_integer()), negative(false) {};
	// constructor by string (e.g. "123", "4567", "0089", "0")
	big_integer(const std::string& s) {
		// check the validity
		if (!(s != "" && (('0' <= s[0] && s[0] <= '9') || s[0] == '-'))) {
			throw std::invalid_argument("big_integer: string does not represent an integer");
		}
		int l = (s[0] != '-' ? 0 : 1);
		for (int i = l; i < int(s.size()); i++) {
			if (!('0' <= s[i] && s[i] <= '9')) {
				throw std::invalid_argument("big_integer: string does not represent an integer");
			}
		}
		while (s[l] == '0' && l != int(s.size()) - 1) {
			l += 1;
		}
		content.size_ = (int(s.size()) - l + basic_integer::BASE_DIGITS - 1) / basic_integer::BASE_DIGITS;
		content.capacity_ = 1;
		while (content.capacity_ < content.size_) {
			content.capacity_ <<= 1;
		}
		content.x = new std::int64_t[content.capacity_];
		for (int i = 0; i < content.capacity_; i++) {
			content.x[i] = 0LL;
		}
		for (int i = l; i < int(s.size()); i++) {
			int pos = (int(s.size()) - i - 1) / basic_integer::BASE_DIGITS;
			content.x[pos] = content.x[pos] * 10 + int(s[i] - '0');
		}
		negative = (s[0] == '-' && (content.size_ >= 2 || content.x[0] != 0LL) ? true : false);
	}
	// to_string() : convert integer to string
	std::string to_string() const {
		int digit = content.digits();
		std::string res(digit + (negative ? 1 : 0), '?');
		if (negative) {
			res[0] = '-';
		}
		for (int i = 0; i < content.size_; i++) {
			std::int64_t v = content.x[i];
			int limit = std::min(basic_integer::BASE_DIGITS * (i + 1), digit);
			for (int j = basic_integer::BASE_DIGITS * i; j < limit; j++) {
				res[digit - j - (negative ? 0 : 1)] = char(v % 10 + '0');
				v /= 10;
			}
		}
		return res;
	}
	// digits() : returns the number of digits
	int digits() const {
		return content.digits();
	}
	// comparison operator #1. == operator
	bool operator==(const big_integer& b) const {
		return (negative == b.negative && content.compare(b.content) == 0);
	}
	// comparison operator #2. != operator
	bool operator!=(const big_integer& b) const {
		return (negative != b.negative || content.compare(b.content) != 0);
	}
	// comparison operator #3. < operator
	bool operator<(const big_integer& b) const {
		return (negative == b.negative ? content.compare(b.content) == -1 : negative);
	}
	// comparison operator #4. > operator
	bool operator>(const big_integer& b) const {
		return (negative == b.negative ? content.compare(b.content) == +1 : b.negative);
	}
	// comparison operator #5. <= operator
	bool operator<=(const big_integer& b) const {
		return (negative == b.negative ? content.compare(b.content) != +1 : negative);
	}
	// comparison operator #6. >= operator
	bool operator>=(const big_integer& b) const {
		return (negative == b.negative ? content.compare(b.content) != -1 : b.negative);
	}
	// operator A1. += operator
	big_integer& operator+=(const big_integer& b) {
		if (negative == b.negative) {
			content += b.content;
		}
		else if (content.compare(b.content) == -1) {
			content = (basic_integer(b.content) -= content);
			negative = !negative;
		}
		else {
			content -= b.content;
			if (negative && content.size_ == 1 && content.x[0] == 0) {
				negative = false;
			}
		}
		return (*this);
	}
	// operator A2. -= operator
	big_integer& operator-=(const big_integer& b) {
		if (negative != b.negative) {
			content += b.content;
		}
		else if (content.compare(b.content) == -1) {
			content = (basic_integer(b.content) -= content);
			negative = !negative;
		}
		else {
			content -= b.content;
			if (negative && content.size_ == 1 && content.x[0] == 0) {
				negative = false;
			}
		}
		return (*this);
	}
	// operator A3. *= operator
	big_integer& operator*=(const big_integer& b) {
		content *= b.content;
		negative = (negative ? !b.negative : b.negative);
		if (negative && content.size_ == 1 && content.x[0] == 0) {
			negative = false;
		}
		return (*this);
	}
	// operator B1. + operator
	big_integer operator+(const big_integer& b) const {
		return big_integer(*this) += b;
	}
	// operator B2. - operator
	big_integer operator-(const big_integer& b) const {
		return big_integer(*this) -= b;
	}
	// operator B3. * operator
	big_integer operator*(const big_integer& b) const {
		return big_integer(*this) *= b;
	}
};

#endif


#include <string>
#include <vector>
#include <iostream>
using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> p(n), bit(n);
	vector<big_integer> a(n), b(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] = big_integer(to_string(x));
		b[i] = big_integer(to_string(i + 1));
	}
	for (int i = 1; i < n; i <<= 1) {
		for (int j = 0; j + i < n; j += 2 * i) {
			a[j] = a[j] + b[j] * a[j + i];
			b[j] = b[j] * b[j + i];
		}
	}
	cout << (a[0] + big_integer("1")).to_string() << endl;
	return 0;
}
yukicoder

結果

テストケース

ソースコード
