提出 #1862762


ソースコード 拡げる

Copy

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;

template<typename Arithmetic, typename Integral>
std::enable_if_t< std::is_unsigned<Integral>::value, Arithmetic>
ipow(Arithmetic bace, Integral n)
{
	//繰り返し二条法
	auto res = (Arithmetic)(1);
	while (n > 0) {
		if (n & 1) res *= bace;
		bace *= bace;
		n >>= 1;
	}
	return res;
}
constexpr bool is_prime(uint32_t N)
{
	if (N <= 1) {
		return false;
	}
	for (size_t i = 2; i*i <= N; ++i)
	{
		if (N%i == 0) {
			return false;
		}
	}
	return true;
}
template <uint64_t MOD> class mint_base;
//mint_base_base型用の累乗関数
template <uint64_t MOD> constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept;
//mod計算を自動で行う整数テンプレートクラス
template <uint64_t MOD_ = 1000000007>
class mint_base
{
public:
	static constexpr auto MOD = MOD_;
	static_assert(!(MOD <= 2), "MOD cannot be below 2.");
	static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない
	static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない
	constexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v += other;
	}
	constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v -= other;
	}
	constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v *= other;
	}
	constexpr auto operator/(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v /= other;
	}
	constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept
	{
		a += other.a;
		if (MOD <= a) { a -= MOD; };
		return *this;
	}
	constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept
	{
		if (a >= other.a) {
			a -= other.a;
		}
		else {
			a = (a + MOD) - other.a;
		}
		return *this;
	}
	constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept
	{
#if 1
		a *= other.a;
		a %= MOD;
#else
		//MOD <= (MAXUINT64 / 2)条件下
		uint64_t b = other.a, v = 0;
		while (b > 0) {
			if (b & 1) {
				v += a;
				if (v >= MOD)v -= MOD;
			}
			a += a;
			if (MOD <= a)a -= MOD;
			b >>= 1;
		}
		a = v;
#endif
		return *this;
	}
	constexpr mint_base<MOD>& operator/=(const mint_base<MOD> &other) noexcept
	{
		return *this *= ~other;
	}
	constexpr mint_base<MOD> operator+()const noexcept { return *this; }
	constexpr mint_base<MOD> operator-()const noexcept
	{
		return{ MOD - a, mod_value_tag{} };
	}
	constexpr mint_base<MOD>& operator++() noexcept
	{
		if (MOD <= ++a) { a = 0; };
		return *this;
	}
	constexpr mint_base<MOD>& operator--() noexcept
	{
		if (a <= 0) { a = MOD; };
		--a;
		return *this;
	}
	constexpr mint_base<MOD> operator++(int) noexcept
	{
		auto tmp = *this;
		++*this;
		return tmp;
	}
	constexpr mint_base<MOD> operator--(int) noexcept
	{
		auto tmp = *this;
		--*this;
		return tmp;
	}
	constexpr mint_base<MOD> operator~()const noexcept
	{
		return ipow(*this, e_phi - 1);
	}
	constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept
	{
		a = other.a;
		return *this;
	}
	constexpr explicit operator uint64_t()const noexcept
	{
		return a;
	}
	constexpr explicit operator unsigned()const noexcept
	{
		return (unsigned)a;
	}
	static constexpr uint64_t getmod() noexcept
	{
		return MOD;
	}
	constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {}
	constexpr mint_base()noexcept : a(0) {}
	struct mod_value_tag {};
	constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {}
private:
	static constexpr uint64_t get_e_phi()noexcept {
		//オイラー値の導出
		uint64_t temp = MOD;
		uint64_t m_ = MOD;
		for (uint64_t i = 2; i * i <= m_; ++i)
		{
			if (m_ % i == 0)
			{
				temp = temp / i * (i - 1);
				for (; m_ % i == 0; m_ /= i);
			}
		}
		if (m_ != 1)temp = temp / m_ * (m_ - 1);
		return temp;
	}
	static constexpr uint64_t e_phi = get_e_phi();//オイラー値
	uint64_t a;
};
//mint_base型用の累乗関数
template<uint64_t MOD>constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept
{
	mint_base<MOD> res = 1;
	while (n > 0)
	{
		if (n & 1)res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}
//mint_baseの階乗計算
//O(x)時間が必要のため、fact_set関数を推奨する。
template<uint64_t MOD>constexpr mint_base<MOD> fact(mint_base<MOD> x)noexcept
{
	mint_base<MOD> res(1);
	for (uint64_t i = 1; i <= (uint64_t)x; ++i)
	{
		res *= i;
	}
	return res;
}
//mint_baseの階乗計算
//0からxまでの階乗を返す
//O(x)時間が必要
template<uint64_t MOD>std::vector<mint_base<MOD>> fact_set(mint_base<MOD> x = mint_base<MOD>(-1))
{
	mint_base<MOD> res(1);
	std::vector<mint_base<MOD>> set((uint64_t)(x)+1);
	set[0] = 1;
	for (uint64_t i = 1; i <= (uint64_t)x; ++i)
	{
		res *= i;
		set[i] = res;
	}
	return res;
}
//mint_base型のstreamへの出力
template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i)
{
	os << (uint64_t)i;
	return os;
}
//mint_base型のstreamからの入力
template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i)
{
	uint64_t tmp;
	is >> tmp;
	i = tmp;
	return is;
}
typedef mint_base<1000000007> mint;
namespace mint_literal {
	constexpr mint operator""_mi(unsigned long long x)noexcept {
		return mint(x);
	}
}
using namespace mint_literal;
//mint_baseの階乗計算
//0からxまでの階乗を返す
//O(N)
template<int32_t X, uint64_t MOD = mint::MOD>
/*constexpr*/ std::array<mint_base<MOD>, X + 1> fact_set_c()
{
	mint_base<MOD> res(1);
	std::array<mint_base<MOD>, X + 1> set;
	set[0] = 1;
	for (int32_t i = 1; i <= X; ++i)
	{
		res *= i;
		set[i] = res;
	}
	return set;
}
template<typename RET = mint, typename Integral>
RET combination(Integral all, Integral get)
{
	assert(all >= get);
	get = std::min(all - get, get);
#if 1
	//時間計算量O(logMOD)
	static const auto fact_v = fact_set_c<100001>();
	return fact_v[all] / (fact_v[get] * fact_v[all - get]);
#elif 0
	//時間計算量O(1)
	//空間計算量、初期化時間計算量O(N^2)
	constexpr int32_t ALL_MAX = 10'000;
	static std::vector<RET> DP_comb[ALL_MAX + 1];
	if (!DP_comb[all].empty())
	{
		return DP_comb[all][get];
	}

	if (DP_comb[0].empty())
	{
		DP_comb[0].resize(1);
		DP_comb[0][0] = (RET)1;
		DP_comb[1].resize(1);
		DP_comb[1][0] = (RET)1;
	}
	for (int32_t i = 2; i <= all; i++)
	{
		if (DP_comb[i].empty())
		{
			int32_t size = i / 2 + 1;
			DP_comb[i].resize(size);
			DP_comb[i][0] = (RET)1;
			for (int32_t j = 1; j < size - 1; j++)
			{
				DP_comb[i][j] = DP_comb[i - 1][j - 1] + DP_comb[i - 1][j];
			}
			DP_comb[i][size - 1] = DP_comb[i - 1][size - 2] + DP_comb[i - 1][(i & 1) ? (size - 1) : (size - 2)];
		}
	}
	return DP_comb[all][get];
#else
	//時間計算量O(get * logMOD)
	RET ret = (RET)1;
	for (Integral i = 1; i <= get; ++i)
	{
		ret *= all + 1 - i;
		ret /= i;
	}
	return ret;
#endif
}



int32_t N;

mint num[2000][2001][2];//01

int32_t parent[2001];
std::vector< int32_t> child[2001];
int32_t input[2001];
int32_t child_all[2001];
bool used[2001];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	for (size_t i = 1; i <= N; i++)
	{
		in>>parent[i];
		input[parent[i]]++;
		child[parent[i]].push_back(i);
	}

	std::queue<int32_t> pos;
	for (size_t i = 1; i <= N; i++)
	{
		if (input[i]==0) {
			pos.push(i);
		}
	}

	for (;;)
	{
		auto now = pos.front(); pos.pop();
		if (used[now]) {
			continue;
		}
		used[now] = true;
		child_all[now] = 0;
		for (auto& c : child[now]) {
			child_all[now] += child_all[c]+1;
		}
		num[now][0][1]= num[now][0][0]= ipow(mint(2), (unsigned)child_all[now]);

		for (int32_t i = 1; i < 2001; i++)
		{
			num[now][i][1] = 0;
			for (size_t k = 0; k < child[now].size(); k++)
			{
				mint tmp = 1;
				for (size_t t = 0; t < child[now].size(); t++)
				{
					if (t != k) {
						tmp *= num[child[now][t]][i-1][0];
					}
				}
				tmp *= num[child[now][k]][i-1][1];
				num[now][i][1] += tmp;
			}
			num[now][i][0] = (num[now][0][0]- num[now][i][1])*2;
			num[now][i][1] *= 2;
		}

		if (now == 0) { break; }
		pos.push(parent[now]);
	}

	mint res = 0;

	for (int32_t i = 0; i < 2001; i++)
	{
		res+=num[0][i][1];
	}
	out << res << endl;

	return 0;
}
#endif


#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;

int32_t N;
int32_t A[50];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N;
	for (size_t i = 0; i < N; i++)
	{
		in >> A[i];
	}
	int32_t abs_max = 0;
	for (size_t i = 0; i < N; i++)
	{
		if (std::abs(A[abs_max]) < std::abs(A[i])) { abs_max = i; }
	}

	if (A[abs_max] == 0) {
		out << 0 << endl; return 0;
	}
	out << 2 * N<<endl;
	if (A[abs_max] > 0) {
		out << abs_max + 1<<' '<<  N << endl;
		out << abs_max + 1 << ' '<<  N << endl;

		for (size_t i = 1; i < N-1; i++)
		{
			out << N << ' ' << N << endl;
			out << N << ' '<<  i+1 << endl;
		}
		out << N << ' ' << N << endl;
		out << N << ' ' << N << endl;
	}
	else {
		out << abs_max + 1<<' '<<  1 << endl;
		out << abs_max + 1 << ' ' << 1 << endl;

		for (size_t i = N - 2; i > 0;--i)
		{
			out << 1 << ' ' << 1 << endl;
			out << 1 << ' ' << i + 1 << endl;
		}
		out << 1 << ' ' << 1 << endl;
		out << 1 << ' ' << 1 << endl;
	}

	return 0;
}
#endif

#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;

int32_t N,K;
int32_t num[200001];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N>>K;
	for (size_t i = 0; i < N; i++)
	{
		int32_t a;
		in >> a;
		num[a]++;
	}
	std::sort(num, num + 200001);

	int32_t sum = 0;
	for (size_t i = 0; i <= 200000-K; i++)
	{
		sum += num[i];
	}

	out << sum << endl;


	return 0;
}
#endif

提出情報

提出日時
問題 E - Smuggling Marbles
ユーザ eiya
言語 C++14 (GCC 5.4.1)
得点 0
コード長 11556 Byte
結果
実行時間 3156 ms
メモリ 64500 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
Subtask1 0 / 400 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt
All 0 / 600 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s1_14.txt, s1_15.txt, s1_16.txt, s1_17.txt, s2_01.txt, s2_02.txt, s2_03.txt, s2_04.txt, s2_05.txt, s2_06.txt, s2_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt, s2_29.txt, s2_30.txt, s2_31.txt, s2_32.txt
ケース名 結果 実行時間 メモリ
00_example_01.txt 1 ms 384 KB
00_example_02.txt 1 ms 512 KB
00_example_03.txt 2 ms 1152 KB
s1_01.txt 9 ms 21376 KB
s1_02.txt 15 ms 18432 KB
s1_03.txt 25 ms 37632 KB
s1_04.txt 2 ms 3328 KB
s1_05.txt 5 ms 15232 KB
s1_06.txt 3156 ms 62848 KB
s1_07.txt 2290 ms 18688 KB
s1_08.txt 42 ms 62976 KB
s1_09.txt 13 ms 18688 KB
s1_10.txt 50 ms 62848 KB
s1_11.txt 15 ms 18688 KB
s1_12.txt 31 ms 39168 KB
s1_13.txt 4 ms 4352 KB
s1_14.txt 22 ms 61184 KB
s1_15.txt 51 ms 62720 KB
s1_16.txt 48 ms 61696 KB
s1_17.txt 51 ms 62208 KB
s2_01.txt 99 ms 384 KB
s2_02.txt 97 ms 384 KB
s2_03.txt 95 ms 384 KB
s2_04.txt 97 ms 384 KB
s2_05.txt 98 ms 384 KB
s2_06.txt 96 ms 384 KB
s2_07.txt 96 ms 384 KB
s2_08.txt 97 ms 384 KB
s2_09.txt 96 ms 384 KB
s2_10.txt 96 ms 384 KB
s2_11.txt 132 ms 64500 KB
s2_12.txt 119 ms 62848 KB
s2_13.txt 97 ms 384 KB
s2_14.txt 98 ms 384 KB
s2_15.txt 95 ms 384 KB
s2_16.txt 97 ms 384 KB
s2_17.txt 102 ms 13824 KB
s2_18.txt 98 ms 384 KB
s2_19.txt 97 ms 384 KB
s2_20.txt 96 ms 384 KB
s2_21.txt 97 ms 384 KB
s2_22.txt 96 ms 384 KB
s2_23.txt 97 ms 384 KB
s2_24.txt 98 ms 384 KB
s2_25.txt 96 ms 384 KB
s2_26.txt 98 ms 384 KB
s2_27.txt 98 ms 384 KB
s2_28.txt 98 ms 384 KB
s2_29.txt 96 ms 384 KB
s2_30.txt 96 ms 384 KB
s2_31.txt 96 ms 384 KB
s2_32.txt 95 ms 384 KB