T1：
答案为$frac{sum limits_{i=1}^n abs(a_i-a_ans)}{2^k}$。
因为每次两个CPU一定选择不同的方案。
时间复杂度$O(n)$。
T2：
路径一定由左括号，中间一段和右括号组成。
左右括号可以用hash匹配。
中间一段的方案可以DP求出。
设$dp[i][j][k][0/1]$表示走到$i$行$j$列，匹配到第$k$个，有无上下转移的方案数。
用左括号做初态，用右括号统计答案。
单独左右括号的情况会算重，要容斥掉。
时间复杂度$O(n^2)$。