Rockdu's Blog

Peace small elephant

Xiao Ming likes playing the international chess ,especially like the elephant(it can move by slant while no barrier), 

but he think the big elephant of the chess is cruel,and a kind of small elephant is not as cruel as the big elephant. 

Its attack range is checks on the ramp of the small elephant's check's right angle.Now Ming is going to put many small elephants on his chessboard. 

It's interesting that when two small elephants have a common side they'll become one solidarity elephant, 

and more than 2 small elephants also can do this if satisfy the condition,and the attack range of solidarity elephants is same as the small elephant. 

Now there is a requirement that it's empty on anyone of elephants' attack range(no piece).Xiao Ming has a special chessboard with $m*n$ checks. 

Please figure out the number of all the plans that satisfy the condition.As the number is too big,we need to have a modulo $1000000007$. 

The following is pictures show the attack range of elephants with different shape,"X"means attack range. 

 

InputThere are at most $5$ testcases . 

For each testcase contains two integers $n,m$ ,meaning as in the title. 
$1 \leq n \leq 1000000000,1 \leq m\leq 7$ 
OutputFor each testcase print a single integer - the number of all the plans that satisfy the condition. 
Sample Input

1 1
2 3

Sample Output

2
50​​

神奇被套路，一开始naive的想法：诶，1e9， 肯定找规律啊，先来二两轮廓线。然后智障般啥规律都没找到。经过大神指点：诶，智障轮廓线，不是一列一列状压递推吗。再一看每一次的转移完全雷同……mdzz，128*128矩阵快速幂。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define for(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int p = 1000000007;
long long trans[130][130], stdrd[130][130], fin;
int n, m, now, cnt, flag, last;
long long ans[130][130];
int pow2[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
inline bool is_t(int st, int k) {return (st & pow2[k - 1]);}
inline void edit(int & st, int k, bool s) {st |= pow2[k - 1];}

void MulE(long long a[130][130], long long b[130][130]) {
	for(i, 0, pow2[m] - 1)
		for(j, 0, pow2[m] - 1) {
			ans[i][j] = 0;
			for(k, 0, pow2[m] - 1)
				(ans[i][j] += (a[i][k] * b[k][j])) %= p;
		}
}

void init() {
	for(i, 0, pow2[m] - 1)
		stdrd[i][i] = 1;
}

void Mtxpow(int k) {
	init();
	while(k) {
		if(k & 1) MulE(stdrd, trans), swap(stdrd, ans);
		MulE(trans, trans);
		swap(trans, ans);
		k >>= 1;
	}
}

int main() {
	while(~scanf("%d%d", &n, &m)) {
		fin = 0;
		memset(trans, 0, sizeof(trans));
		memset(stdrd, 0, sizeof(stdrd));
		for(i, 0, pow2[m] - 1)
			for(j, 0, pow2[m] - 1) {
				now = i, cnt = 0, flag = 0;
				while(++cnt, now) {
					if(now & 1)
						if(!((cnt == 1 && (!is_t(j, cnt + 1) || is_t(j, cnt) || is_t(now, cnt + 1))) ||
						   (cnt == m && (!is_t(j, cnt - 1) || is_t(j, cnt) || last)) ||
						   (cnt != m && cnt != 1 && (((!is_t(j, cnt - 1) || last) && (!is_t(j, cnt + 1) || is_t(now, 2))) || is_t(j, cnt)))))
							{flag = 1;break;}
					last = now & 1;
					now >>= 1;
				}
				if(flag == 1) continue;
				++trans[i][j];
			}
		Mtxpow(n);
		for(j, 0, pow2[m] - 1) {
			(fin += (stdrd[0][j])) %= p;
		}
		printf("%lld\n", fin);
	}
	return 0;
}