这种是老题了吧
#include<iostream>
#include<algorithm>
using namespace std;
int n, a, b, m;
struct ss {
int a[1 << 7][1 << 7];
} ba, x;
void dfs(int s) {
for (int i = 0; i < a - 1; i++) {
int p = 3 << i;
if ((s & p) == 0) {
ba.a[m][(~(s + p))&(n - 1)] = 1;
dfs(s + p);
}
}
}
ss mm(ss a, ss b, int k) {
ss temp;
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++) {
temp.a[i][j] = 0;
for (int l = 0; l < k; l++)
temp.a[i][j] += a.a[i][l] * b.a[l][j];
temp.a[i][j] %= 9937;
}
return temp;
}
int main() {
while (scanf("%d%d", &a, &b) != EOF) {
if (a > b)swap(a, b);
n = 1 << a;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
x.a[i][j] = ba.a[i][j] = 0;
if (i == j)x.a[i][j] = 1;
}
for (m = 0; m < n; m++) {
ba.a[m][(~m)&(n - 1)] = 1;
dfs(m);
}
for (; b; b >>= 1, ba = mm(ba, ba, n)) if (b & 1)x = mm(x, ba, n);
printf("%d\n", x.a[0][0]);
}
}
据说有数学公式。。我是用矩阵做的