151123(6)

C


Dyck path とSelf-avoiding walk の融合(6)

m > 0, (mn + 2) (n + 1) / 2 < 64 のとき、
F(mn, n) を出力してみる。

#include <stdio.h>

int triangular_number(int x, int y, int m, int n){
 int i;
 i = x - m * y + (m * (2 * n - y + 1) + 2) * y / 2;
 return i;
}

// startがx, y、goalの座標がmn, n
long long search(int x, int y, int m, int n, long long used){
 long long cnt = 0LL;
 int z;
 z = triangular_number(x, y, m, n);
 if (x < 0 || m * n + 1 <= x || y < 0 || m * y > x || (used & (1LL << z)) > 0) return 0;
 if (x == m * n && y == n) return 1;
 used += 1LL << z;
 cnt += search(x + 1, y, m, n, used);
 cnt += search(x - 1, y, m, n, used);
 cnt += search(x, y + 1, m, n, used);
 cnt += search(x, y - 1, m, n, used);
 used -= 1LL << z;
 return cnt;
}

int main(void){
 int m;
 int n;
 long long used;
 m = 1;
 for (n = 0; n < 10; n++){
  used = 0LL;
  printf("%lld\n", search(0, 0, m, n, used));
 }
 m = 2;
 for (n = 0; n < 7; n++){
  used = 0LL;
  printf("%lld\n", search(0, 0, m, n, used));
 }
 m = 3;
 for (n = 0; n < 6; n++){
  used = 0LL;
  printf("%lld\n", search(0, 0, m, n, used));
 } 
 m = 4;
 for (n = 0; n < 5; n++){
  used = 0LL;
  printf("%lld\n", search(0, 0, m, n, used));
 }
 m = 5;
 for (n = 0; n < 5; n++){
  used = 0LL;
  printf("%lld\n", search(0, 0, m, n, used));
 }
 return 0;
}

出力結果
1
1
2
7
40
369
5680
150707
6993712
567670347
1
1
4
44
1282
105022
25769912
1
1
8
284
44360
33970104
1
1
16
1872
1592536
1
1
32
12384
57870848