yukicoder 1181 (★2.5) 解説
解説と微妙に違うので 真部分集合の条件いる？
解説: 明らかに$ S の対称性が強い
まず集合 $ T が出てくるのがうるさいので、そこを消去する
数列 $ S の要素を $ i 個選び、マルを付けることにする。この選び方は $ _N C _i 通り
答に寄与するのはマルの着いた部分の積の和をとったもので、$ (1+2+...+K)^i が $ K^{N-i} 通りずつ存在することがわかる。
あとは$ i を $ 0 から $ N-1 まで動かして和を求めればよい。(真部分集合なので、範囲に注意)
要するに、 $ \sum_{i=0}^{N-1}$ _N C _i (\frac{K(K+1)}{2})^i K^{N-i} を求める。
→これ二項定理で戻せばO(1) いけるのでは？しらんけど
なんでこれ元々3.5だったの？