問題のリンクはこちらです。問題は、基本的に、要素の合計が A と B の間である、サイズ N × M の特定の行列のそのようなすべての部分行列を数えることです。N、M<=250。10^-9<=A<=B<=10^9。
人々はDPとBITを使用してそれを解決しました。方法はわかりません。
最初に、上記の問題のより単純なバージョンである 1 次元のケースを解決しようとしました: 長さ N の配列 A が与えられた場合、サブ配列内の要素の合計が A と B の間にあるすべてのサブ配列を数えますが、それでもできませんでしたO（n ^ 2）よりも優れていると考えてください。これが私がしたことです：
元の配列のプレフィックス合計を保持するための別の配列を作成することを考えました。たとえば、prefix[N] です。プレフィックス[i] = A 1 + A[2] + A[3] + ...A[i]。プレフィックス [1] = A [1] を設定します。次に、2 から N までの各 i について、合計 Z = A[j] + A[j+1] + ..A[i] が A と B の間にあるように、すべての j <= i を数えます。これは等価です。接頭辞[i] - 接頭辞[j-1]。しかし、それはまだ O(n^2) です。各 i について、j は i か所にヒットしています。
主な問題を解決するために与えられたアプローチで私を前進させるために、誰かが私を一歩一歩助けてくれますか?.