SRM550 Div1 Medium

500

配置の仕方が、nCk = n-1Ck-1 + n-1Ck を何となく連想させる。
描画してみる。向きと幅がアレだけど、nCk mod 2 のフラクタルに見える。しかし、値の範囲が大きすぎる。

どうやら、nCkが奇数であることと(~n&k)==0は同値らしい。

class CheckerExpansion {
public:
  vector <string> resultAfter(lli t, lli x0, lli y0, int w, int h)
  {
    vector<string> ret;

    for (lli i = y0; i < y0 + h; ++i) {
      string s;
      for (lli j = x0; j < x0 + w; ++j) {
        bool hata = true;
        lli k = i;
        lli n = (i + j) / 2LL;
        hata = hata && !(~n & k);
        hata = hata && ((i + j) % 2 == 0);
        hata = hata && (n < t);
        if (hata) s += (n % 2) ? 'B' : 'A';
        else s += '.';
      }
      ret.push_back(s);
    }
    reverse(ret.begin(), ret.end());
    return ret;
  }
};