結果

問題 No.1963 Subset Mex
コンテスト
ユーザー vjudge1
提出日時 2025-12-23 16:00:04
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 3,654 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,026 ms
コンパイル使用メモリ 86,712 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-23 16:00:07
合計ジャッジ時間 2,927 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 25 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<cstring>
#include<utility>
#include<fstream>
#include<iostream>
#include<type_traits>
using namespace std;

using ull = unsigned long long;
constexpr const unsigned mod = 998244353, modM1 = mod - 1;
constexpr const size_t sizeof_unsigned = sizeof(unsigned);
inline void UpdateInc(unsigned& pos, const unsigned val)
{
	if ((pos += val) >= mod)
	{
		pos -= mod;
	}
	return;
}
inline void UpdateDec(unsigned& pos, const unsigned val)
{
	if (static_cast<int>(pos -= val) < 0)
	{
		pos += mod;
	}
	return;
}
unsigned counter[111], f[2][101][101], g[2][101];
constexpr unsigned& counter_0 = counter[0], (&f_1)[101][101] = f[1];
int main()
{
	unsigned T;
        
	for (T=1; T--;)
	{
		unsigned n;
		cin >> n;
		const unsigned nP1 = n + 1, n2M1 = n * 2 - 1;
		unsigned maxi_a = 0, mini_a = 128;
		for (unsigned i = 1; i <= n; ++i)
		{
			unsigned a;
			cin >> a;
			if (maxi_a < a)
			{
				maxi_a = a;
			}
			if (mini_a > a)
			{
				mini_a = a;
			}
			++counter[a];
		}
		const unsigned maxi_num = maxi_a + 7;
		f[maxi_num % 2][0][0] = 1;
		for (unsigned i = maxi_num; i > 1; --i)
		{
			const unsigned counter_iM1 = counter[i - 1];
			auto& f_i = f[i % 2], & f_iM1 = f[(i % 2) ^ 1];
			for (unsigned j = 0; j <= n; ++j)
			{
				const int jMn = j - n;
				const unsigned t1 = counter_iM1 - j;
				auto& f_i_j = f_i[j], & f_iM1_j = f_iM1[j];
				for (unsigned k = 0; k <= n; ++k)
				{
					if (f_i_j[k])
					{
						const unsigned f_i_j_k = f_i_j[k];
						for (unsigned u = 0; u <= n; ++u)
						{
							const int t2 = t1 - u;
							if (t2 >= 0)
							{
								UpdateInc(f_iM1_j[k + t2], f_i_j_k);
							}
							else if (t2 >= jMn)
							{
								UpdateInc(f_iM1[j - t2][k], f_i_j_k);
							}
						}
						f_i_j[k] = 0;
					}
				}
			}
		}
		const unsigned counter0P1 = counter_0 + 1;
		unsigned ans = 0;
		for (unsigned i = 0; i <= n; ++i)
		{
			const unsigned t = counter0P1 - i;
			auto& f_1_i = f_1[i];
			for (unsigned j = 0; j <= n; ++j)
			{
				if (f_1_i[j])
				{
					if (static_cast<int>(t + j) > 0)
					{
						ans = (ans + static_cast<ull>(min(t + j, nP1)) * f_1_i[j]) % mod;
					}
					f_1_i[j] = 0;
				}
			}
		}
		if (mini_a < 2)
		{
			ans = (ans ? ans - 1 : modM1);
		}
		const unsigned maP1 = maxi_a + 1;
		unsigned& g_maP1_0 = g[maP1 % 2][0];
		for (unsigned i = 1; i <= maxi_a; ++i)
		{
			if (counter[i])
			{
				unsigned needing = 0, c = counter_0;
				for (unsigned j = i - 1; j; --j)
				{
					if (counter[j] > needing)
					{
						c += counter[j] - 1 - needing;
					}
					else
					{
						needing = min(needing + needing + 1 - counter[j], n2M1);
					}
				}
				if (needing > c)
				{
					const size_t siz_g = static_cast<size_t>(needing = min(needing - c, nP1)) * sizeof_unsigned;
					g_maP1_0 = 1;
					const unsigned iP1 = i + 1, needingM1 = needing - 1;
					auto& g_i = g[i % 2];
					for (unsigned j = maP1; j > i; --j)
					{
						if (counter[j - 1] || j != iP1)
						{
							const unsigned limit_u = counter[j - 1] - (j == iP1);
							auto& g_j = g[j % 2], & g_jM1 = g[(j % 2) ^ 1];
							for (unsigned k = 0; k < needing; ++k)
							{
								if (g_j[k])
								{
									const unsigned g_j_k = g_j[k], end_u = min(limit_u, needingM1 - k);
									for (unsigned u = 0; u <= end_u; UpdateInc(g_jM1[k + (u++)], g_j_k));
									g_j[k] = 0;
								}
							}
						}
						else
						{
							memset(g[j], 0, siz_g);
						}
					}
					for (unsigned j = 0; j < needing; UpdateDec(ans, g_i[j]), g_i[j++] = 0);
					g_i[needing] = 0;
				}
			}
		}
		memset(counter + mini_a, 0, static_cast<size_t>(maxi_a - mini_a + 1) * sizeof_unsigned);
		cout << ans << '\n';
	}
	return 0;
}
0