{"problem":{"name":"[JRKSJ R5] 1-1 B","description":{"content":"给出一个序列 $a$，$\\forall i\\in [1,n],a_i\\in \\{1,-1\\}$。 询问有多少个将 $a$ 重排后的序列使得该序列的最大子段和最小化。 称两个序列不同，当且仅当这两个序列有任意一个位置上的数不同。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8848"},"statements":[{"statement_type":"Markdown","content":"给出一个序列 $a$，$\\forall i\\in [1,n],a_i\\in \\{1,-1\\}$。\n\n询问有多少个将 $a$ 重排后的序列使得该序列的最大子段和最小化。\n\n称两个序列不同，当且仅当这两个序列有任意一个位置上的数不同。\n\n## Input\n\n第一行一个整数 $n$。\n\n第二行 $n$ 个整数表示 $a$。\n\n## Output\n\n一个整数表示答案。答案对 $998244353$ 取模。\n\n[samples]\n\n## Background\n\n本题是 1-1 的较难版本，较易版本为 [1-1 A](https://www.luogu.com.cn/problem/P8847)。\n\n## Note\n\n最大子段和的定义：序列中一段区间的和的最大值。即 $\\max_{1\\le l\\le r\\le n} \\sum_{i=l}^r a_i$。\n\n### 数据规模\n本题采用捆绑测试。\n\n| $\\text{Subtask}$ | $n\\le$ | $\\text{Score}$ |\n| :----------: | :----------: | :----------: |\n| $1$ | $10$ | $20$ |\n| $2$ | $100$ | $20$ |\n| $3$ | $500$ | $20$ |\n| $4$ | $10^4$ | $40$ |\n\n对于 $100\\%$ 的数据，$1\\le n\\le 10^4$，$a_i\\in \\{1,-1\\}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8848","tags":["动态规划 DP","2022","洛谷原创","洛谷月赛"],"sample_group":[["4\n1 -1 1 -1","3"],["5\n1 1 1 -1 1","3"],["10\n1 1 1 1 1 1 1 -1 -1 -1","40"]],"created_at":"2026-03-03 11:09:25"}}