{"problem":{"name":"[yLCPC2024] D. 排卡","description":{"content":"扶苏有一个双端队列 $a$。这个队列与计算机科学中队列的概念类似，不同的是，这个队列既可以从队列头读取和弹出元素，也可以在队列尾部读取和弹出元素，因此被称为『双端队列』。 这个队列中有 $n$ 个数。扶苏将通过 $n$ 次操作构造一个长度为 $n$ 的序列 $b$，第 $i$（$1 \\leq i \\leq n$）次操作会可以进行如下两个过程之一： 1. 令 $b_i$ 为 $a$ 的队列头，并","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10236"},"statements":[{"statement_type":"Markdown","content":"扶苏有一个双端队列 $a$。这个队列与计算机科学中队列的概念类似，不同的是，这个队列既可以从队列头读取和弹出元素，也可以在队列尾部读取和弹出元素，因此被称为『双端队列』。\n\n这个队列中有 $n$ 个数。扶苏将通过 $n$ 次操作构造一个长度为 $n$ 的序列 $b$，第 $i$（$1 \\leq i \\leq n$）次操作会可以进行如下两个过程之一：\n\n1. 令 $b_i$ 为 $a$ 的队列头，并在 $a$ 的头部弹出一个元素。\n2. 令 $b_i$ 为 $a$ 的队列尾，并在 $a$ 的尾部弹出一个元素。\n\n我们定义一个数对 $(i, j)$ 的得分为：\n\n$$\\mathrm{score}(i,j) = i^j \\bmod 998244353$$\n\n即 $i$ 的 $j$ 次幂对 $998244353$ 取余数的结果。特别的，在本题中我们规定 $0^0 = 0$。\n\n现在，扶苏想用最优的策略构造 $b$ 序列，最大化如下式子的值：\n\n$$\\sum_{i = 1}^{n - 1} \\mathrm{score}(b_i, b_{i + 1})$$\n\n即 $b$ 所有相邻两项按原顺序计算的得分之和。\n\n注意，我们仅在计算一个数对的时候将得分对 $998,244,353$ 取模，在计算求和时不再将这个和取余。\n\n## Input\n\n**本题单个测试点内有多组测试数据**。第一行是一个正整数，表示数据组数 $T$。对每组数据：\n\n第一行是一个整数 $n$（$2 \\leq n \\leq 10^3$），表示序列的长度。  \n第二行有 $n$ 个整数 $a_1, a_2, \\dots a_n$（$0 \\leq a_i < 998,244,353$），按从头到尾的顺序表示队列 $a$ 里每个数字的值。\n\n数据保证单个测试点内 $n$ 的和不超过 $10^3$。\n\n## Output\n\n对每组测试数据，输出一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n经过千辛万苦，扶苏终于到达了机厅。但是她很快发现机厅排起了大 b 队 ~~（不是省选的 B 队）~~。\n\n舞萌玩家们在人多的时候经常采取排卡的方式决定谁下一个上机。因为人实在是太多了，他们在排卡的时候，便注意到了卡上的编号。\n\n他们向扶苏提了一个问题，你能解决吗？","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10236","tags":["洛谷原创","区间 DP","洛谷月赛"],"sample_group":[["2\n5\n5 3 1 4 2\n6\n6 5 1 4 2 3","1168\n15655"]],"created_at":"2026-03-03 11:09:25"}}