左上のエントリに 1 を含む NXM 行列の数を見つける必要があります。すべてのエントリは整数値であり、隣接するエントリの違いは最大 1 です。N は最大 5 であり、M は最大 10^9 になることがわかっています。明らかに、バックトラッキング アルゴリズムは十分に高速ではありません。この問題は、行列の累乗を使用して解決できると思いますが、この点についてこれ以上のアイデアはありません。前もって感謝します！
質問する
68 次
1 に答える
0
すべての行は次の形式です。
x (y=x+1/x/x-1) (z=y+1/y/y-1) ...
x の値はあまり重要ではないため、(N = 5 の場合) 各行には 3^4 = 81 の可能性があります。
ここから、単純なプログラムを作成して、現在の行にある 81 個の可能性のそれぞれについて、どの可能性が次の行にどのくらいの頻度で出現するかを判断します。
そこから、単純な式がある場合は式を理解できるはずです。それ以外の場合は、O(10^9) アルゴリズムがあり、これは少なくとも最初に使用したものよりも優れています。
「最大」と「最大まで」は、アルゴリズムを少し混乱させます。
于 2012-12-31T06:14:17.450 に答える