たとえば K=4 で 1,4,7,10 が書かれたカードから引く場合を考えると、 全試行パターンは1回目と2回目で4通りずつなので、K^2=16 通り。
期待値は、全ての場合の得点を合計してこの K^2 で割ればよいので、合計の方を求められればよい。
得点ごとに、そのパターン数を考えると
得点が1になる場合: 1を2回連続で引く 1x1 = 1 通り
得点が4になる場合: 1,4から2回連続で引く場合から
得点が1になる場合を除く 2x2 - 1x1 = 3 通り
得点が7になる場合: 3枚から2回連続で引く場合から
得点が1,4になる場合を除く 3x3 - 2x2 = 5 通り
得点が10になる場合: 4枚から2回連続で引く場合から
得点が1,4,7になる場合を除く 4x4 - 3x3 = 7 通り
1x1 + 4x3 + 7x5 + 10x7 = 118
小さい順に 1,3,5,...（奇数）通りずつパターン数が増えていく。得点とパターン数を掛け合わせればよい。
（同じ数字があった場合も、適当に順番を決めて扱えばよい）
で、この K=4 の値から K=5 の値を求められる。
A_5=6 を追加した場合、
得点 パターン数
1 1
4 3
New! 6 5
7 5→7
10 7→9
3番目に追加されるのでパターン数は5となり、6 \times 5 が新たに増える。
また、それより大きい値の 7,10 は、1つにつき 2 ずつパターン数が増える。
なので、
が、逐次求められればよいことになる。（A_i \times (2p+1) + 2q だけ増える）
これは、A_i をindexとして個数を管理するFenwick Treeと、合計を管理するFenwick Treeの2本を使って 1回あたり \log{A_{max}} で求められる。
単調増加列の問題は、差分に着目すると上手くいくことがよくある。
末尾と M との差分（下図 b_5）まで含めて考えると、差分の総和が上限値 M となる。
A 0 a1 a2 a3 a4 M Aの差分 b1 + b2 + b3 + b4 + b5 = M
隣り合う項の3で割ったあまりが異なるので、両端を除く b_2～b_4 は、3の倍数であってはいけないということになる。
逆にこれさえ満たせば条件を満たす数列となるため、そのような非負整数列 B=(b_1,...,b_{N+1}) の個数を数えればよい。
ここで、B を3で割った商 X=(x_1,...,x_{N+1}) とあまり Y=(y_1,...,y_{N+1}) に分けて考える。
条件は「y_2～y_N は 0 禁止（1,2 のいずれか）」「3x_i+y_i の総和が M」となる。
条件を満たす X,Y は、例えば以下のようにして構築できる。
以下の2つを固定すると、
そのパターン数が O(1) で求められる。
この2つを掛け合わせたものが、s,k を固定した時のパターン数となる。全探索して合計すれば答え。
本番では3で割った商とあまりに分割するところまでは思いついたが、b_1 を特別視しすぎて b_2～b_N だけで X,Y を考え、b_1 は別で計算してしまったため、考慮すべきパターン数が増え、計算量が NM から減らせなかった。