#1074006 (C++17) No.3055 Simple Chicken Game

提出ソース
結果

問題	No.3055 Simple Chicken Game
ユーザー	ecottea
提出日時	2025-04-17 15:58:17
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	60 ms / 2,000 ms
コード長	16,786 bytes
コンパイル時間	4,585 ms
コンパイル使用メモリ	285,168 KB
実行使用メモリ	38,528 KB
最終ジャッジ日時	2025-04-17 15:58:25
合計ジャッジ時間	6,028 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 30
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifndef HIDDEN_IN_VS // 折りたたみ用

// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS

// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;

// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>;	using pll = pair<ll, ll>;	using pil = pair<int, ll>;	using pli = pair<ll, int>;
using vi = vector<int>;		using vvi = vector<vi>;		using vvvi = vector<vvi>;	using vvvvi = vector<vvvi>;
using vl = vector<ll>;		using vvl = vector<vl>;		using vvvl = vector<vvl>;	using vvvvl = vector<vvvl>;
using vb = vector<bool>;	using vvb = vector<vb>;		using vvvb = vector<vvb>;
using vc = vector<char>;	using vvc = vector<vc>;		using vvvc = vector<vvc>;
using vd = vector<double>;	using vvd = vector<vd>;		using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;

// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;

// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;

// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定

// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline T getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod

// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }

#endif // 折りたたみ用


#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;

#ifdef _MSC_VER
#include "localACL.hpp"
#endif

//using mint = modint998244353;
//using mint = static_modint<(int)1e9 + 7>;
using mint = modint; // mint::set_mod(m);

namespace atcoder {
	inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
	inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif


#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif


//【有理数】（の改変）
/*
* Frac<T>() : O(1)
*	0 で初期化する．
*	制約：T は int, ll, __int128, boost::multiprecision::int256_t 等
*
* Frac<T>(T num) : O(1)
*	num で初期化する．
*
* Frac<T>(T num, T dnm) : O(1)
*	num / dnm で初期化する（分母は自動的に正にする）
*
* a == b, a != b, a < b, a > b, a <= b, a >= b : O(1)
*	大小比較を行う（分母が共通の場合は積はとらない）
*
* a + b, a - b, a * b, a / b : O(1)
*	加減乗除を行う（和と差については，分母が共通の場合は積はとらない）
*	一方が整数でも構わない．複合代入演算子も使用可．
*
* reduction() : O(log min(num, dnm))
*	自身の約分を行う．
*
* together(Frac& a, Frac& b) : O(log min(a.dnm, b.dnm))
*	a と b を通分する．
*
* together(vector<Frac>& as) : O(|as| log dnm)
*	as を通分する．
*
* T floor() : O(1)
*	自身の floor を返す．
*
* T ceil() : O(1)
*	自身の ceil を返す．
*
* Frac absolute() : O(1)
*	自身の絶対値を返す．
*
* bool integerQ() : O(1)
*	自身が整数かを返す．
*/
template <class T = ll>
struct Frac {
	// 分子，分母
	T num, dnm;

	// コンストラクタ
	Frac() : num(0), dnm(1) {}
	Frac(T num) : num(num), dnm(1) {}
	Frac(T num_, T dnm_) : num(num_), dnm(dnm_) {
		// verify : https://atcoder.jp/contests/abc244/tasks/abc244_h

		Assert(dnm != 0);
		if (dnm < 0) { num *= -1; dnm *= -1; }
	}

	// 代入
	Frac(const Frac& b) = default;
	Frac& operator=(const Frac& b) = default;

	// キャスト
	operator double() const { return (double)num / (double)dnm; }

	// 比較
	bool operator==(const Frac& b) const {
		// 分母が等しいときはオーバーフロー防止のために掛け算はせず比較する．
		if (dnm == b.dnm) return num == b.num;
		return num * b.dnm == b.num * dnm;
	}
	bool operator!=(const Frac& b) const { return !(*this == b); }
	bool operator<(const Frac& b) const {
		// verify : https://atcoder.jp/contests/abc308/tasks/abc308_c

		// 分母が等しいときはオーバーフロー防止のために掛け算はせず比較する．
		if (dnm == b.dnm) return num < b.num;
		return (num * b.dnm < b.num * dnm);
	}
	bool operator>=(const Frac& b) const { return !(*this < b); }
	bool operator>(const Frac& b) const { return b < *this; }
	bool operator<=(const Frac& b) const { return !(*this > b); }

	// 整数との比較
	bool operator==(T b) const { return num == b * dnm; }
	bool operator!=(T b) const { return num != b * dnm; }
	bool operator<(T b) const { return num < b * dnm; }
	bool operator>=(T b) const { return num >= b * dnm; }
	bool operator>(T b) const { return num > b * dnm; }
	bool operator<=(T b) const { return num <= b * dnm; }
	friend bool operator==(T a, const Frac& b) { return a * b.dnm == b.num; }
	friend bool operator!=(T a, const Frac& b) { return a * b.dnm != b.num; }
	friend bool operator<(T a, const Frac& b) { return a * b.dnm < b.num; }
	friend bool operator>=(T a, const Frac& b) { return a * b.dnm >= b.num; }
	friend bool operator>(T a, const Frac& b) { return a * b.dnm > b.num; }
	friend bool operator<=(T a, const Frac& b) { return a * b.dnm <= b.num; }

	// 四則演算
	Frac& operator+=(const Frac& b) {
		// verify : https://www.codechef.com/problems/ARCTR

		// 分母が等しいときはオーバーフロー防止のために掛け算はせず加算する．
		if (dnm == b.dnm) num += b.num;
		else { num = num * b.dnm + b.num * dnm; dnm *= b.dnm; }
		return *this;
	}
	Frac& operator-=(const Frac& b) {
		// verify : https://www.codechef.com/problems/ARCTR

		// 分母が等しいときはオーバーフロー防止のために掛け算はせず加算する．
		if (dnm == b.dnm) num -= b.num;
		else { num = num * b.dnm - b.num * dnm; dnm *= b.dnm; }
		return *this;
	}
	Frac& operator*=(const Frac& b) { num *= b.num; dnm *= b.dnm; return *this; }
	Frac& operator/=(const Frac& b) {
		// verify : https://atcoder.jp/contests/abc301/tasks/abc301_g

		Assert(b.num != 0);
		num *= b.dnm; dnm *= b.num;
		if (dnm < 0) { num *= -1; dnm *= -1; }
		return *this;
	}
	Frac operator+(const Frac& b) const { Frac a = *this; return a += b; }
	Frac operator-(const Frac& b) const { Frac a = *this; return a -= b; }
	Frac operator*(const Frac& b) const { Frac a = *this; return a *= b; }
	Frac operator/(const Frac& b) const { Frac a = *this; return a /= b; }
	Frac operator+() const { return Frac(*this); }
	Frac operator-() const { return Frac(*this) *= Frac(-1); }

	// 整数との四則演算
	Frac& operator+=(T c) { num += dnm * c; return *this; }
	Frac& operator-=(T c) { num -= dnm * c; return *this; }
	Frac& operator*=(T c) { num *= c; return *this; }
	Frac& operator/=(T c) {
		Assert(c != T(0));
		dnm *= c;
		if (dnm < 0) { num *= -1; dnm *= -1; }
		return *this;
	}
	Frac operator+(T c) const { Frac a = *this; return a += c; }
	Frac operator-(T c) const { Frac a = *this; return a -= c; }
	Frac operator*(T c) const { Frac a = *this; return a *= c; }
	Frac operator/(T c) const { Frac a = *this; return a /= c; }
	friend Frac operator+(T c, const Frac& a) { return a + c; }
	friend Frac operator-(T c, const Frac& a) { return Frac(c) - a; }
	friend Frac operator*(T c, const Frac& a) { return a * c; }
	friend Frac operator/(T c, const Frac& a) { return Frac(c) / a; }

	// 約分を行う．
	void reduction() {
		// verify : https://atcoder.jp/contests/abc229/tasks/abc229_h

		auto g = gcd(num, dnm);
		//auto g = boost::math::gcd(num, dnm);
		num /= g; dnm /= g;
	}

#ifdef _MSC_VER
	friend ostream& operator<<(ostream& os, const Frac& a) { os << a.num << '/' << a.dnm; return os; }
#endif
};


//【座標圧縮】O(n log n)
/*
* a[0..n) を座標圧縮した結果を a_cp[0..n) に格納し，その値域の大きさを返す．
* また xs[j] に圧縮された座標 j に対応する元の座標を格納する．
*
* a に重複する要素がなければ，a_cp[i] は a[i] が昇順で何番目かを表し，
* xs[j] は昇順で j 番目の要素が何かを表す．
*/
template <class T>
int coordinate_compression(const vector<T>& a, vi& a_cp, vector<T>* xs = nullptr) {
	// verify : https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_o

	int n = sz(a);
	if (xs == nullptr) xs = new vector<T>;

	// *xs : a の x 座標のユニークな昇順列
	*xs = a;
	uniq(*xs);

	// a[i] が xs において何番目かを求める．
	a_cp.resize(n);
	rep(i, n) a_cp[i] = lbpos(*xs, a[i]);

	return sz(*xs);
}


vl naive(int n) {
	using F = Frac<__int128>;
	using vF = vector<F>;
	
	map<string, int> nxt;

	auto to_str = [&](vi a) {
		string s;
		repe(x, a) {
			if (x > 1000) s += "+";
			else if (x < -1000) s += "-";
			else s += "0";
		}
		return s;
	};

	function<vF(vi, int)> rf = [&](vi a, int k) {
		string s = to_str(a);

		if (k == n) {
			vi a_cp;
			coordinate_compression(a, a_cp);

			vF f(n);
			rep(i, n) f[i] = F(n - a_cp[i]);

//			dump("a:", a, "k:", k, "f:", f);

			return f;
		}

		a.push_back((int)1e9 - k - 1);
		vF fP = rf(a, k + 1);
		a.pop_back();

		a.push_back(-(int)1e9 - k - 1);
		vF fN = rf(a, k + 1);
		a.pop_back();
		
		a.push_back(0 - k - 1);
		vF f0 = rf(a, k + 1);
		a.pop_back();

		vF f1(n);
		rep(i, n) f1[i] = (fP[i] + fN[i]) / F(2);

		vF f;
		if (f0[k] == f1[k]) {
			nxt[s] = 2;

			f.resize(n);
			rep(i, n) f[i] = (f0[i] + f1[i]) / F(2);
		}
		else if (f0[k] < f1[k]) {
			nxt[s] = 0;

			f = move(f0);
		}
		else {
			nxt[s] = 1;

			f = move(f1);
		}
		rep(i, n) f[i].reduction();

//		dump("a:", a, "k:", k, "f:", f);

		return f;
	};
	vF f = rf(vi(), 0);
//	dump(f);
	
	vl res(n);
	rep(i, n) {
		f[i] *= powi(2, 2 * n - 2 - i);
		res[i] = (ll)(f[i].num / f[i].dnm);
	}

//	dumpel(nxt);

	int cnt2 = 0;
	function<void(vi, int)> rf2 = [&](vi a, int k) {
		cnt2++;

		string s = to_str(a);
//		dump(s, nxt[s]);

		if (k == n) {
			return;
		}

		if (nxt[s] == 2) {
			a.push_back((int)1e9 - k - 1);
			rf2(a, k + 1);
			a.pop_back();

			a.push_back(-(int)1e9 - k - 1);
			rf2(a, k + 1);
			a.pop_back();

			a.push_back(0 - k - 1);
			rf2(a, k + 1);
			a.pop_back();
		}
		else if (nxt[s] == 0) {
			a.push_back(0 - k - 1);
			rf2(a, k + 1);
			a.pop_back();
		}
		else {
			a.push_back((int)1e9 - k - 1);
			rf2(a, k + 1);
			a.pop_back();

			a.push_back(-(int)1e9 - k - 1);
			rf2(a, k + 1);
			a.pop_back();
		}
	};
	rf2(vi(), 0);

//	dump("cnt2:", cnt2);

	return res;
}


void zikken() {
	vvl fs;

	repi(n, 16, 16) {
		auto f = naive(n);
		fs.push_back(f);

		dump(f);
	}

	dump_math(fs);

	exit(0);
}
/*
1
6 3
30 15 9
142 71 43 23
654 327 195 105 57
2958 1479 867 465 255 135
13198 6599 3811 2033 1111 593 313
58254 29127 16611 8817 4791 2553 1359 711
254862 127431 71907 38001 20535 10905 5799 3057 1593
1106830 553415 309475 162929 87607 46361 24583 12953 6799 3527
4776846 2388423 1325283 695409 372279 196377 103815 54585 28647 14961 7737
20505486 10252743 5650659 2956401 1576503 829209 437127 229305 120135 62745 32655 16839
87614350 43807175 24000739 12524657 6655543 3491609 1835911 960953 502471 262073 136423 70769 36409
372827022 186413511 101595363 52894833 28020279 14665497 7693191 4018617 2097351 1092153 567879 294681 152463 78279
1580786574 790393287 428751075 222764145 117673527 61458201 32170887 16773561 8739015 4543545 2359239 1223097 633063 326769 167481
6681060238 3340530119 1804482787 935795825 493063735 257017625 134275975 69890489 36354247 18873401 9786823 5067833 2620999 1353497 697231 356807

2D P-recursive なのでライブラリで殴れる．
*/

vvl a0= { {1}, {6, 3}, {30, 15, 9}, {142, 71, 43, 23}, {654, 327, 195, 105,
   57}, {2958, 1479, 867, 465, 255, 135}, {13198, 6599, 3811, 2033,
   1111, 593, 313}, {58254, 29127, 16611, 8817, 4791, 2553, 1359,
   711}, {254862, 127431, 71907, 38001, 20535, 10905, 5799, 3057,
   1593}, {1106830, 553415, 309475, 162929, 87607, 46361, 24583,
   12953, 6799, 3527}, {4776846, 2388423, 1325283, 695409, 372279,
   196377, 103815, 54585, 28647, 14961, 7737}, {20505486, 10252743,
   5650659, 2956401, 1576503, 829209, 437127, 229305, 120135, 62745,
   32655, 16839}, {87614350, 43807175, 24000739, 12524657, 6655543,
   3491609, 1835911, 960953, 502471, 262073, 136423, 70769,
   36409}, {372827022, 186413511, 101595363, 52894833, 28020279,
   14665497, 7693191, 4018617, 2097351, 1092153, 567879, 294681,
   152463, 78279}, {1580786574, 790393287, 428751075, 222764145,
   117673527, 61458201, 32170887, 16773561, 8739015, 4543545, 2359239,
	1223097, 633063, 326769, 167481}, {6681060238, 3340530119,
   1804482787, 935795825, 493063735, 257017625, 134275975, 69890489,
   36354247, 18873401, 9786823, 5067833, 2620999, 1353497, 697231,
   356807} };


int main() {
//	input_from_file("input.txt");
//	output_to_file("output.txt");

//	zikken();

	int n, p;
	cin >> n >> p;

	mint::set_mod(p);

	mint inv3 = mint(3).inv();

	vvm a(n + 1, vm(n + 1));
	repi(i, 1, min(sz(a0), n)) repi(j, 1, i) a[i][j] = a0[i - 1][j - 1];

	// 半自動生成
	repi(i, 4, n) {
		a[i][1] = 9 * a[i - 1][1] - 24 * a[i - 2][1] + 16 * a[i - 3][1];
	}
	repi(i, 5, n) {
		a[i][2] = 9 * a[i - 1][2] - 24 * a[i - 2][2] + 16 * a[i - 3][2];
	}
	repi(i, 4, n) {
		a[i][i] = 3 * a[i - 1][i - 1] - 4 * a[i - 3][i - 3];
	}
	repi(i, 4, n) repi(j, 3, i - 1) {
		a[i][j] = -3 * a[i - 1][j - 2] - 2 * a[i - 1][j - 1] + 4 * a[i - 1][j] + a[i][j - 2] + a[i][j - 1];
		a[i][j] *= inv3;
	}

	dumpel(a);

	vm res = a[n];

	mint inv2 = mint(2).inv();
	mint pow_inv2 = mint(inv2).pow(n - 1);
	repir(i, n, 1) {
		res[i] *= pow_inv2;
		pow_inv2 *= inv2;
	}
	dump(res);

	repi(i, 1, n) cout << res[i] << " \n"[i == n];
}
yukicoder

結果

ソースコード
