CodeChef-GAPFILL : Gap Filler Game

問題概要

+を十にしたようなライツアウトで、解の存在するH*W(H,W<10^18)の盤面は何通りあるか求める問題。テストケース5*10^5個。

解法

小さいところで実験したら法則性がわかる。後はフェルマーの小定理などを使って計算すればよい。

acceptされたコード

#include <cstdio>
using namespace std;

typedef long long int64;

const int64 MOD = 1e9 + 7;

inline int64 pow_binary(int64 x, int64 n, int64 mod){
	int64 ret = 1;
	for(;n;n>>=1){
		if( n&1 ){
			ret = ret * x % mod;
		}
		x = x * x % mod;
	}

	return ret;
}

int solve(int64 H, int64 W){
	int64 ans = 1;
	if(W%2 == 0){
		if(H%2==0){
			return (int)((int64)solve(H, W+1) * pow_binary(2, MOD-2, MOD) % MOD);
		}
		else{
			return solve(H, W+1);
		}
	}

	int64 WW = W / 2, diff = WW * 4, HH = H / 2;
	diff %= MOD - 1;
	HH %= MOD - 1;
	int64 e = 1 + HH*diff;
	e %= MOD - 1;

	return (int)pow_binary(2, e, MOD);
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		int64 N, M;
		scanf("%lld%lld", &N, &M);
		printf("%d\n", solve(N, M));
	}
	return 0;
}