解説放送のG問題の解説を一通り見ていることを前提としています。 解法の流れはなんとなくわかったけど、順列を並び替える的な話がどこに行ったんだ？とか、(全体の転倒数)が一回しか答えに加算されていないのはなぜ？みたいな感じの疑問を持った人用の解説だと思ってください。見やすさは皆無なので許してください。
まず愚直解を考えてΣを展開する、「rep(i,n-k+1)をして、選んだ区間をK!通り試して転倒数をもとめてその期待値を求める」という感じのTLE前提をちょっと高速化すると、差分だけを求めるみたいな感じの解法になる
式に表すと下のようになって、Σiは、シャッフルする一番左を試す、ΣK!はその区間内を実際にシャッフルする、ということをそれぞれ意味する。
(Σi(
(ΣK!(
シャッフル前の全体の転倒数-シャッフル前のシャッフルする区間の転倒数+現在のK!での転倒数
)
)/K!
)
)/(n-k+1);
という形になっている。なお、Σiのループ回数は(n-k+1)回であることが後で重要なので注意(i=0,1,2,...n-kなのでn-k+1回)。
とりあえずΣの性質からΣK!をそれぞれに配る
そうしたときに一個ずつ見ていく
(ΣK!(シャッフル前の全体の転倒数))/K! について考えると、中身は定数なので、Σの性質から (ΣK!(シャッフル前の全体の転倒数))/K!=(シャッフル前の全体の転倒数)となる。1a+2a+3a...ka= a*(1+2+3,...K)=a*K!なので問題なく/K!できる、K!のせいでややこしく感じるなら K!をちゃんとした整数として求めれば理解できるはず
(ΣK!(シャッフル前のシャッフルする区間の転倒数))/K! について考えると、これはiの値が決まっているとき、絶対に定数なのでその定数が上と同様にK!回繰り返されるだけなのでK!の話が消せる
(ΣK!(現在のK!での転倒数))/K!については、これはK!ごとに値が違うからだめ、だから何もできない？と思いきや違う。今の「(ΣK!(現在のK!での転倒数))/K!」は「順列の転倒数の期待値」と言葉で表せる
この「順列の転倒数の期待値」というのは、その順列サイズがkだったとき、kC2/2という形で表せる。どういうことかというと、まず今求めているのは「期待値」であるというのが重要で、今とある順列があったとき、転倒数として数えられるのは2つ選んだ時に左の方が大きい場合となる。ここで順列の中から二つを選んだ時に、選んだ2つにおいて左の方が大きい確率は1/2であり、各ペアでの期待値は、11/2+01/2=1/2が期待値となり、それがnC2通りのペアがあるから、nC2*(1/2)=nC2/2が答えとなる。なお、確率が1/2というのは、「対称性」というキーワードで説明できるらしい。i,jと仮に決めたとして、ia[j]ならば転倒数として数えられる。ここで、a[i]>a[j]とa[i]a[j]と入れるか、a[i]と<それぞれに1通りずつ加算されるからa[i]>a[j]になる通りとa[i]<a[j]になる通りは等しく、全体の通りを半分半分しているから確率は1/2となる。(ChatGPTに教えてもらったのでこれでも理解できなければさらに質問してください)
よって現在のをまとめると
(Σi(
シャッフル前の全体の転倒数-シャッフル前のシャッフルする区間の転倒数+(kC2/2)
)
)/(n-k+1);
という感じで全てのK!が消せた。
次にΣiの方を考えていくためにΣiを配っていく
(Σi(シャッフル前の全体の転倒数))/(n-k+1) について考えると、中身は定数であり、Σiはi=0,1,2...n-kで、合計(n-k+1)回のループなので、さっきと同様に ((n-k+1)定数)/(n-k+1)だからx定数/xという感じでまた定数だけが一回分残る
(Σi(シャッフル前のシャッフルする区間の転倒数))/(n-k+1)について考えると、これはiが毎回違うと毎回数字が変わるから、定数じゃないのでΣを消せない。しかし長さkのをスライドしていけば求められて、その総和を/(n-k+1)すれば欲しい期待値が求まる、つまり純粋に求めるのをfenwciktreeで高速化すればOK
(Σi(kC2/2))/(n-k+1)について考えると、中身は定数なので二個上の行と同じように消せるので、kC2が一個だけ残る
よって最終結果は
シャッフル前の全体の転倒数 は一個分
シャッフル前のシャッフルする区間の転倒数 は愚直に求めていくんだけど高速化はfenwick_treeを使えばよくて、最後に求めた内容を /(n-k+1) すればOK
(kC2/2) は一個分
よってこの問題をACできる