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; }