UVa 12627 : Erratic Expansion

問題リンク : http://uva.onlinejudge.org/external/126/12627.html

問題概要 :
赤い風船を１つだけ持っている
次の日になると赤い風船が３つ、青い風船が１つになった
次の日になると赤い風船は前日と同様に分裂し、青い風船は４つの青い風船になった
詳しくは問題にある図を見ること
そんな感じの規則で1日毎に風船が変化していく
K日後の列Aから列Bまでにある赤い風船の数を数えよ

解法 :
再帰で領域を均等に４分割していくと良い

1 | 2
______
3 | 4

こんな感じで
４は全て青になる

rec(左上のx,左上のy,右下のx,右下のy) := この範囲にある赤い風船の数　とする
今みている領域がAからBの間にない場合、再帰を終了する ( 0を返す )
今みている領域がAからBの間に完全に入っている場合、４分割した領域のうち全て青になる領域でない領域は全て結果が等しくなるのでそのうちの１つだけ再帰しその結果を３倍して返す
今みている領域が2*2なら、1,2,3のうち対応する数を返す
それ以外の場合、1と２のみを計算し(1の結果)*2+(2の結果)を返す
1と3は全く同じ結果になりますからね

よくある再帰のアレ
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
int A,B,K,N;
 
inline bool isValid(int x) { return A <= x && x <= B; }
 
ll rec(int tx,int ty,int bx,int by){
  if( B < tx || bx < A ) return 0;
  int len_x = abs(tx-bx)+1;
  int len_y = abs(ty-by)+1;
  assert( len_x == len_y );
  if( len_x <= 2 ) {
    if( isValid(tx) && isValid(bx)  )  {
      return 3LL;
    } else {
      if( isValid(tx) && !isValid(bx) ) return 2LL;
      else if( isValid(bx) && !isValid(tx) ) return 1LL;
      return 0;
    }
  }
 
  bool all = false;
  if( isValid(tx) && isValid(bx) ) {
    all = true;
  }
  ll ret = 0;
  int h = len_x / 2;
  int nx[2],ny[2];
  //1
  nx[0] = tx, ny[0] = ty;
  nx[1] = tx+h-1, ny[1] = ty+h-1;
  ret += rec(nx[0],ny[0],nx[1],ny[1]) * 2LL;
  if( all ) return ret / 2LL * 3LL;
  //2
  nx[0] = tx+h, ny[0] = ty;
  nx[1] = bx, ny[1] = ty+h-1;
  ret += rec(nx[0],ny[0],nx[1],ny[1]);
  return ret;
}
 
int main(){
  int T,CNT=1;
  cin >> T;
  while( T-- ){
    cin >> K >> A >> B;
    N = (1<<K);
    if( K == 0 ) {
      printf("Case %d: 1\n",CNT++);
    } else {
      printf("Case %d: %lld\n",CNT++,rec(1,1,(1<<K),(1<<K)));
    }
  }
  return 0;
}