[JRKSJ R5] 1-1 B

Luogu

IDLGP8848

Time1000ms

Memory128MB

DifficultyP4

动态规划 DP2022洛谷原创洛谷月赛

给出一个序列 $a$，$\forall i\in [1,n],a_i\in \{1,-1\}$。询问有多少个将 $a$ 重排后的序列使得该序列的最大子段和最小化。称两个序列不同，当且仅当这两个序列有任意一个位置上的数不同。 ## Input 第一行一个整数 $n$。第二行 $n$ 个整数表示 $a$。 ## Output 一个整数表示答案。答案对 $998244353$ 取模。 [samples] ## Background 本题是 1-1 的较难版本，较易版本为 [1-1 A](https://www.luogu.com.cn/problem/P8847)。 ## Note 最大子段和的定义：序列中一段区间的和的最大值。即 $\max_{1\le l\le r\le n} \sum_{i=l}^r a_i$。 ### 数据规模本题采用捆绑测试。 | $\text{Subtask}$ | $n\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | | $1$ | $10$ | $20$ | | $2$ | $100$ | $20$ | | $3$ | $500$ | $20$ | | $4$ | $10^4$ | $40$ | 对于 $100\%$ 的数据，$1\le n\le 10^4$，$a_i\in \{1,-1\}$。

Samples

Input #1

4
1 -1 1 -1

Output #1

Input #2

5
1 1 1 -1 1

Output #2

Input #3

10
1 1 1 1 1 1 1 -1 -1 -1

Output #3

API Response (JSON)

{
  "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$ 取模。...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments