题目描述
给定一个长度为 \(n\) 的正整数数组 \(A\)，其中每个数都在 \(1\) 到 \(m\) 之间，从左到右排成一排。现在要将每个数字染成红色或者绿色，我们定义一个染色方案为优秀的染色方案，当且仅当它满足：
- 每个数 \(A_{i}\) 要么被染成红色，要么被染成绿色。
- 红色的数从左到右依次严格递增，绿色的数从左到右依次严格递减。
例如：\(1\;9\;3\;4\;7\;6\) 中，将 \(1\;3\;4\;7\) 染成红色，\(9\;6\) 染成绿色是优秀的染色方案（\(\color{red}1\color{green}9\color{red}347\color{green}6\)）；\(1\;3\;4\;6\) 染成红色，\(9\;7\) 染成绿色也是优秀的染色方案（\(\color{red}1\color{green}9\color{red}34\color{green}7\color{red}6\)）。但是将 \(1\;4\;7\;6\) 染成红色，\(9\;3\) 染成绿色则不是优秀的染色方案，因为 \(1\;4\;7\;6\) 不是递增的。\(1\;9\;5\;5\) 中，将 \(1\) 和任意一个 \(5\) 染色红色，\(9\) 和另一个 \(5\) 染成绿色，也是优秀的染色方案（其中一种是 \(\color{red}1\color{green}95\color{red}5\)）。
如果一个数组至少存在两个不同的优秀的染色方案，那么称这个数组是完美的。(两个染色方案不同当且仅当至少存在一个位置上的数字被染成不同的颜色）。
例如，\(1\;9\;3\;4\;7\;6\) 和 \(1\;9\;5\;5\) 都是完美的，因为上面已经分别给出了 \(2\) 种优秀的染色方案。而 \(2\;3\;3\;3\) 则不是完美的，因为找不到任何一种优秀的染色方案。同时 \(1\;5\;3\;6\;4\) 也不是完美的，因为仅存在一种优秀的染色方案（\(\color{red}1\color{green}5\color{red}36\color{green}4\)）。
补充说明：如果红色的数只有 \(0\) 个或者 \(1\) 个，我们也认为它严格递增；同理如果绿色的数只有 \(0\) 个或者 \(1\) 个，我们也认为它严格递减。例如 \(\color{red}123\)，\(\color{red}1\color{green}2\color{red}3\) 都是优秀的的染色方案，因此 123 是完美的数组。
我们定义一种给染色方案打分的方式。
对于每个的有序元素对 \(A_{i}, A_{j}(i<j)\) :
- 如果 \(A_{j}\) 染成红色，且 \(A_{j}<A_{i}\)，则该元素对得 \(m-A_{j}+1\) 分;
- 如果 \(A_{j}\) 染成绿色，且 \(A_{j}>A_{i}\)，则该元素对得 \(A_{j}\) 分;
- 不满足 1 或 2 ，则该元素对得 \(0\) 分。
则一个染色方案的得分为所有有序元素对的得分和。
一个完美的数组的得分为它所有优秀的染色方案的得分的最大值。
现在确定数组 \(A\) 的前 \(t\) 个数 \(A_{1}, A_{2}, \ldots，A_{t}\), 你需要回答以下两个问题:
- 第一问：有多少种确定 \(A\) 中后 \(n-t\) 个数的方案使得 \(A\) 是一个完美数组？
- 第二问：所有可能的完美数组的得分和是多少？
由于答案太大，你只需要输出答案在模 \(998244353\) 下的结果即可。
提示
【评分方式】
每个测试点 \(5\) 分。
每一行应按顺序输出两问的答案，不符合输出格式的输出得 \(0\) 分。
程序仅回答对第一问得 \(1\) 分，仅回答对第二问得 \(4\) 分，两问都答对得 \(5\) 分。
如果你不回答第一问或第二问，也需要在对应位置上输出任意一个整数以满足输出格式。
【子任务】
对于所有的数据，保证： \(1 \leq C \leq 5\)；\(2 \leq n \leq 50\)；\(1 \leq t \leq n\)；\(1 \leq m \leq 200\)；\(1 \leq A_{i} \leq m\) 。
题解
下面是我想的做法。
先思考\(t=n\)怎么做，即给定一个完整的数组\(A\)，判定其是否为完美数组，以及计算其得分。
先考虑判定怎么做。
首先，一个完美数组中出现次数最多的元素，出现次数必然\(<=2\)，若同一元素出现三次，因为红，绿均要求严格，考虑最好的情况，也只是一个染成红色，一个染成绿色，剩下一个甚至无法染色，下面对完美数组的讨论均有这一前提。
若其为完美数组，则必然存在一个非空的位置集合\(S\)，其中的位置上的数既可以被染成红色，也可以被染成绿色，因为如果集合\(S\)为空集，那么相当于每个位置的颜色是唯一的，当然也有可能找不出优秀的染色方案，不过无论是哪种情况，该数组都不可能为完美数组。
考虑一个位置\(pos\)怎么样才可能在集合\(S\)中，我们发现这件事情等价于\([1,pos-1]\)中\(<=A_{pos}\)的数与\([pos+1,n]\)中\(>=A_{pos}\)的数构成递增子序列且\([1,pos-1]\)中\(>=A_{pos}\)的数与\([pos+1,n]\)中\(<=A_{pos}\)的构成递减子序列，若\(pos\)满足以上两个条件，那么\(A_{pos}\)染成红色或绿色均可。
方案：若\(pos\)染成红色，则将\([1,pos-1]\)中\(<A_{pos}\)的数均染成红色，\([pos+1,n]\)中\(>A_{pos}\)的数均染成红色，剩余的数染成绿色即可。
若\(pos\)染成绿色，则将\([1,pos-1]\)中\(>A_{pos}\)的数均染成绿色，\([pos+1,n]\)中\(<A_{pos}\)的数均染成绿色，剩余的数染成红色即可。
那么判断集合\(S\)是否为空集只需枚举\(pos\)，同时维护前缀后缀即可做到线性。
那么\(t=n\)的第一问做完了，2分到手。
接下来思考整个题怎么做。
考虑\(S\)中的数有什么性质：首先，不可能有断点，在位置上必然是连续的。
即记\(S\)中最小值为\(l\)，最大值为\(r\)，那么\(S\)中的元素即为\(l\)至\(r\)。
证明：第一种情况，\(S\)中只有一个元素。
去除\(S\)中只有一个元素的情况，考虑\(S\)中只有两个元素的情况，不妨使用反证法。
设\(S\)中只有\(pos_1,pos_2\)两个元素，\(pos_1<pos_2\)且\(pos_2!=pos_1+1\)，首先讨论\(A_{pos_1}=A_{pos_2}\)的情况，发现无法找到染色方案，推出矛盾，那么即可推出\(S\)中元素的第二种情况\(r=l+1\)且\(a_r=a_l\)
根据我们之前的推论可知\([1,pos_1-1]\)中\(<=A_{pos_1}\)的数与\([pos_1+1,n]\)中\(>=A_{pos_1}\)的数构成递增子序列，\([1,pos_2-1]\)中\(<=A_{pos_2}\)的数与\([pos_2+1,n]\)中\(>=A_{pos_2}\)的数构成递增子序列，\([1,pos_1-1]\)中\(>=A_{pos_1}\)的数与\([pos_1+1,n]\)中\(<=A_{pos_1}\)的数构成递减子序列，\([1,pos_2-1]\)中\(>=A_{pos_2}\)的数与\([pos_2+1,n]\)中\(<=A_{pos_2}\)的数构成递减子序列。
不妨设\(A_{pos_1}<A_{pos_2}\)，那么\([pos_1+1,pos_2-1]\)中\(<=A_{pos_2}\)的数构成递增子序列，\([pos_1+1,pos_2-1]\)中\(>=A_{pos_2}\)的数构成递减子序列，那么任取\(x\in[pos_1+1,pos_2-1],x\in Z\)。
首先必然有\(A_x>A_{pos_1}\)（由\([1,pos_2-1]\)中\(<=A_{pos_2}\)的数构成递增子序列，且\(A_{pos_1}<A_{pos_2}\)推出。）。
其次必然有\(A_x<A_{pos_2}\)，证明考虑若\(A_x>A_{pos_2}\)，由于已有\(A_x>A_{pos_1},A_{pos_2}>A_{pos_1}\)，故与\([pos_1+1,pos_2-1]\)中\(>=A_{pos_1}\)的数构成递增子序列矛盾！
所以\(A_{pos_1}<A_x<A_{pos_2}\)。
则由上可推出\([1,x-1]\)中\(<=A_x\)的数与\([x+1,n]\)中\(>=A_x\)的数构成递增子序列，且\([1,x-1]\)中\(>=A_x\)的数与\([x+1,n]\)中\(<=A_x\)的数构成递减子序列，则\(x\)也在集合\(S\)中，与\(S\)中只有两元素的假设矛盾！
\(A_{pos_1}>A_{pos_2}\)的情况是类似的，可推出\(A_{pos_1}>A_x>A_{pos_2}\)。
而且由于任取\(x\in[pos_1+1,pos_2-1],x\in Z\)都可证明\(x\)在\(S\)中，故对于任意的\(i\in[l,r],i\in Z\)，\(i\)均在集合\(S\)中，且满足\(A_l<...<A_r\)或\(A_l>...>A_r\)，这是第三种情况。
接下来考虑在这些数在值域上有什么性质。
可以发现\(l\)到\(r\)这些数在值域上切出了一段，即对于任意的\(i\in[1,l-1],i\in Z\)，均有\(A_i \notin[min(A_l,A_r),max(A_l,A_r)]\)。
证明考虑反证法，若存在\(i\in[1,l-1],i\in Z\)，有\(A_i\in[min(A_l,A_r),max(A_l,A_r)]\)，若\(i\)被染成红色，则\(A_l\)至\(A_r\)中小于\(A_i\)的数不能被染成红色，绿色同理，那么这些数的位置就不能在集合\(S\)中，推出矛盾！即证。
仅在\(n=1\)时会出现第一种情况。
第二种情况与第三种情况类似做。
取第三种情况讨论。
先做第一问，我们可以在\(r\)处统计方案数，注意到对于\(A_1\)至\(A_{r-1}\)这些数，恰好存在一种染色方案使得红色序列结尾小于\(A_r\)，绿色序列结尾大于\(A_r\)，即将\(l\)至\(r-1\)的所有数染成红色，\([1,l-1]\)中的数\(<A_l\)的染成红色，\(>A_r\)的染成绿色。
那么可以\(dp\)，具体的，我们令\(f[i][j][k]\)表示现在做完了第\(i\)个数，红色序列结尾的数为\(j\)，绿色序列结尾的数为\(k\)的方案数，枚举\(r,A_r,A_{r+1}\)，转移形如\(f[i][lim_j][lim_k]=\sum\limits_{j<lim_j}f[i-1][j][lim_k]+\sum\limits_{k>lim_k}f[i-1][lim_j][k]\)，前缀和优化一下发现是\(O(nm^2)\)的，最后答案\(ans\)形如\(\sum\limits_{j}\sum\limits_{k} f[n][j][k]\)，在最开始预处理一下\(f\)即可。
第一问做完了，时间复杂度单次\(O(nm^2)\)，20分到手。
考虑第二问怎么做，先思考\(t=n\)怎么办。
此时\(S\)已知，取\(A_l<...<A_r\)讨论，另一种情况类似。
此时\(S\)中的数至多有一个被染成绿色。
考虑有一个数被染成绿色的情况。
不妨假设将\(A_{pos}(l<=pos<=r)\)染成绿色，固定\(pos\)，对得分的贡献为\(\sum\limits_{i=1}^{l-1}[A_i<A_{pos}]*A_{pos}+\sum\limits_{i=l}^{pos-1}A_{pos}\)，即\(\sum\limits_{i=1}^{l-1}[A_i<A_{pos}]*A_{pos}+(pos-l)*A_{pos}\)，当\(pos\)变大时，\(A_{pos}\)变大，\([1,l-1]\)中小于\(A_{pos}\)的个数可能变多，\((pos-l)\)变大，对得分的贡献显然变大，所以若要选一个染成绿色，我们必须贪心的将\(A_r\)染成绿色来最大化得分。
当然，也有可能\(S\)中的数均被染成红色，也需要讨论。
其实与上面的染色方案唯一的区别就是将\(A_r\)改为了红色。
那么综上所述
\[若A_r染成红色\\ 则将[1,r-1]中<A_r的元素染成红色，[1,r-1]中>=A_r的元素染成绿色\\ 将[r+1,n]中>A_r的元素染成红色，[r+1,n]中<=A_r的元素染成绿色\\ 设该方案得分为res_1\\ 若A_r染成绿色\\ 则将[1,r-1]中<=A_r的元素染成红色，[1,r-1]中>A_r的元素染成绿色\\ 将[r+1,n]中>=A_r的元素染成红色，[r+1,n]中<A_r的元素染成绿色\\ 设该方案得分为res_2\\ 那么最终的最大得分res=max(res_1,res_2) \]那么\(t=n\)的第二问也做完了，28分到手。
接下来思考整个题怎么做。
仍然枚举\(r,A_r,A_{r+1}\)
我会拆贡献！
\[[1,r-1]:\\ 设g[i][j][k]表示前i个数，红色结尾j，绿色结尾k，得分和\\ g0[i][j][k]表示前i个数，红色结尾j，绿色结尾k，红色数之和\\ g1[i][j][k]表示前i个数，红色结尾j，绿色结尾k，绿色数之和\\ r:\\ 设[1,r-1]中剩余num个位置可以填数\\ 有num_R个<A_r的可以填的数，有num_G个>A_r的可以填的数，对答案的贡献为\\ \sum\limits_{i=0}^{num}\binom{num}{i}\binom{num_R}{i}\binom{num_G}{num-i}max(A_r红情况，A_r绿情况)\\ A_r红:(m-A_r+1)*(num-i)+...\\ A_r绿:A_r*i+...\\ 就是上面写的两个方案里取个max，如果看懂了我写的，自己应该能推出来，因此就不写了\\ [r+1,n]:\\ 不妨以A_i染成绿色为例，染成红色是类似的\\ 我们需要统计A_1至A_{i-1}中有多少个数小于A_i\\ 对r分类讨论：\\ 若r<t,此时A_r已经确定，A_{r+1}已经确定\\ 外层循环只有i,r,是O(nm)的\\ 对于已经确定的数，出现次数就是第一问的方案数\\ 未确定的数，出现次数是相同的，出现次数之和可以计算，计算出和后取平均值即可\\ 得到所有数出现次数后乘乘贡献就得到了答案。\\ 若r=t,此时A_r已经确定，A_{r+1}未确定\\ 若r>t,则A_r未确定，A_{r+1}未确定，这两种情况可以放在一起做。\\ 以A_{r+1}为分界点断开，左边的数分为一类，A_{r+1}一类，右边的数分为一类，出现次数不同的数只有这三类\\ 将r往右挪动时重新计算即可，挪动次数是O(n)的。 \]综上所述，本题单次复杂度是\(O(n^2m^2)\)的，但是多组询问，所以还要乘个\(C\)，所以最后复杂度是\(O(Cn^2m^2)\)的，可以通过，只要我说的是对的，100分到手。
标签：省选,题解,染成,pos,绿色,color,红色,染色,联考 From： https://www.cnblogs.com/llzer/p/17300377.html