提出 #65458298

---

ソースコード 拡げる

// #include <bits/allocator.h> // Temp fix for gcc13 global pragma
// #pragma GCC target("avx2,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
#ifdef LOCAL
	#include "Debug.h"
#else
	#define debug_endl() 42
	#define debug(...) 42
	#define debug2(...) 42
	#define debug_bin(...) 42
#endif

// Enumerate all partitions of 0 to n in lexicographical order.
vector<vector<vector<int>>> enumerate_partitions(int n){
	assert(0 <= n);
	vector<vector<vector<int>>> p(n + 1);
	p[0] = {{}};
	for(auto x = 1; x <= n; ++ x) for(auto last = x; last >= 1; -- last) for(auto q: p[x - last]){
		if(!q.empty() && q.back() < last) break;
		q.push_back(last);
		p[x].push_back(q);
	}
	for(auto x = 1; x <= n; ++ x){
		reverse(p[x].begin(), p[x].end());
		for(auto &q: p[x]) reverse(q.begin(), q.end());
	}
	return p;
}
// Enumerate all partitions of 0 to n in lexicographical order, along with its occurence as set of sizes of cycles in S_n.
template<class T, bool PRECOMPUTE_INVERSE = false>
vector<vector<pair<vector<int>, T>>> enumerate_partitions_with_count(int n){
	auto p = enumerate_partitions(n);
	vector<T> fact(n + 1, 1), invfact, inv;
	for(auto x = 1; x <= n; ++ x) fact[x] = fact[x - 1] * x;
	if constexpr(PRECOMPUTE_INVERSE){
		invfact.resize(n + 1), inv.resize(n + 1, 1);
		invfact[n] = 1 / fact[n];
		for(auto x = n - 1; x >= 1; -- x){
			invfact[x] = invfact[x + 1] * (x + 1);
			inv[x + 1] = invfact[x + 1] * fact[x];
		}
	}
	vector<vector<pair<vector<int>, T>>> res(n + 1);
	for(auto x = 0; x <= n; ++ x){
		for(auto q: p[x]){
			T cnt = fact[x];
			for(auto y: q){
				if constexpr(PRECOMPUTE_INVERSE) cnt *= inv[y];
				else cnt /= y;
			}
			for(auto l = 0; l < (int)q.size(); ){
				int r = l;
				while(r < (int)q.size() && q[l] == q[r]) ++ r;
				if constexpr(PRECOMPUTE_INVERSE) cnt *= invfact[r - l];
				else cnt /= fact[r - l];
				l = r;
			}
			res[x].push_back({q, cnt});
		}
	}
	return res;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	cout << fixed << setprecision(15);
	int n, t, m, k;
	cin >> n >> t >> m >> k;
	vector<vector<int>> parts;
	for(auto all = enumerate_partitions(m)[m]; auto part: all){
		if((int)part.size() <= n){
			vector<int> cnt(m + 1);
			for(auto x: part){
				++ cnt[x];
			}
			cnt[0] = n - (int)part.size();
			parts.push_back(cnt);
		}
	}
	vector<double> dp(k + 1), dp_next(k + 1);
	dp[k] = 1;
	for(auto i = 0; i < t; ++ i){
		ranges::fill(dp_next, 0);
		dp_next[k] = 1;
		for(auto x = 0; x < k; ++ x){
			for(auto cnt: parts){
				double cur = 0;
				for(auto y = 0; y <= m; ++ y){
					cur += cnt[y] * dp[min(k, x + y)];
				}
				dp_next[x] = max(dp_next[x], cur / n);
			}
		}
		swap(dp, dp_next);
	}
	cout << dp[0] << "\n";
	return 0;
}

/*

*/

提出情報

ジャッジ結果