この問題を解決しようとしていますが、解決策が見つかりません:
N 行 M 列に配置された正方形からなるボードが与えられます。このボードのタイリングは、それを覆うタイルのパターンです。次の場合、タイリングは興味深いものです。
only tiles of size 1x1 and/or 2x2 are used;
each tile of size 1x1 covers exactly one whole square;
each tile of size 2x2 covers exactly four whole squares;
each square of the board is covered by exactly one tile.
たとえば、次の画像は、サイズが 4 行 3 列のボードのいくつかの興味深いタイリングを示しています 。
ボードの 2 つの興味深いタイリングは、一方のタイリングではサイズ 1x1 のタイルで覆われ、他方ではサイズ 2x2 のタイルで覆われている正方形がボード上に少なくとも 1 つ存在する場合、異なります。たとえば、上の画像に示されているすべてのタイリングは異なります。
関数を書く
int count_tilings(int N, int M);
これは、2 つの整数 N と M を指定すると、サイズが N 行 M 列のボードの異なる興味深いタイルの数のモジュロ 10,000,007 の剰余を返します。
と仮定する：
N is an integer within the range [1..1,000,000];
M is an integer within the range [1..7].
たとえば、N = 4 および M = 3 の場合、この関数は 11 を返す必要があります。これは、サイズが 4 行 3 列のボードに 11 の異なる興味深いタイリングがあるためです。
http://dabi.altervista.org/images/task.img.4x3_tilings_all.gif
(4,3) の結果は 11、(6,5) の結果は 1213 です。次のことを試しましたが、うまくいきません。
static public int count_tilings ( int N,int M ) {
int result=1;
if ((N==1)||(M==1)) return 1;
result=result+(N-1)*(M-1);
int max_tiling= (int) ((int)(Math.ceil(N/2))*(Math.ceil(M/2)));
System.out.println(max_tiling);
for (int i=2; i<=(max_tiling);i++){
if (N>=2*i){
int n=i+(N-i);
int k=i;
//System.out.println("M-1->"+(M-1) +"i->"+i);
System.out.println("(M-1)^i)->"+(Math.pow((M-1),i)));
System.out.println( "n="+n+ " k="+k);
System.out.println(combinations(n, k));
if (N-i*2>0){
result+= Math.pow((M-1),i)*combinations(n, k);
}else{
result+= Math.pow((M-1),i);
}
}
if (M>=2*i){
int n=i+(M-i);
int k=i;
System.out.println("(N-1)^i)->"+(Math.pow((N-1),i)));
System.out.println( "n="+n+ " k="+k);
System.out.println(combinations(n, k));
if (M-i*2>0){
result+= Math.pow((N-1),i)*combinations(n, k);
}else{
result+= Math.pow((N-1),i);
}
}
}
return result;
}
static long combinations(int n, int k) {
/*binomial coefficient*/
long coeff = 1;
for (int i = n - k + 1; i <= n; i++) {
coeff *= i;
}
for (int i = 1; i <= k; i++) {
coeff /= i;
}
return coeff;
}