SRM578

Easy ("GooseInZooDivOne", 250)

ローカルで大丈夫っぽかったので投げてみたら、最大盤面（50x50）を'v'で埋め尽くしたケースでTLEが出た。ローカルでそのケースをやっても -O2 なら333msecで終了するのになんで？

もしかして：サーバ激遅
サーバで実行してみるにはArenaのTEST機能を使えばいい。
http://topcoder.g.hatena.ne.jp/agw/20130121/1358797527
vector<string> fieldは

vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

を + ボタンで50回追加して（でいいのかな）
int dist = 0 でTEST実行

遅い…

ローカルでは余裕な提出コード

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
// BEGIN CUT HERE
#include "cout.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>

using namespace std;
typedef long long ll;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())

#define MOD 1000000007LL

ll add(ll x, ll y) { return (x + y) % MOD; }
ll sub(ll x, ll y) { return (x - y) % MOD; }
ll mul(ll x, ll y) { return (x * y) % MOD; }
ll pow(ll x, ll y) {
  ll v = 1;
  for(;y;x=mul(x,x),y>>=1)
    if(y&1) v = mul(v, x);
  return v;
}
ll div_(ll x, ll y) { return mul(x, pow(y, MOD-2)); }

ll C(ll n, ll k) { // nCk
  pair<ll,ll> p(n, k);
  // if (found(cmm, p)) return cmm[p];
  ll v = 1;
  for (ll i=1; i<=k; ++i) 
    v = div_(mul(v, n-i+1), i);
  return v;
}

ll twopow(ll x) { // 2^x
  ll a = 1LL;
  rep(i,x) a = mul(a, 2);
  return a;
}

class UnionFind {
  vector<int> data;
 public:
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};

class GooseInZooDivOne {
 public:
  int count(vector<string> field, int dist) {
    int W=sz(field[0]), H=sz(field), S=W*H; // 50x50=2500

    stringstream ss;
    rep(i,H) ss << field[i];
    string f = ss.str();

    UnionFind uf(S);
    for (int i=0; i<S-1; ++i) {
      int xi = i % W, yi = i / W;
      if (f[i] == '.') continue;
      for (int j=i+1; j<S; ++j) {
        if (f[j] == '.') continue;
        int xj = j % W, yj = j / W;
        int md = abs(xi-xj) + abs(yi-yj);
        if (md <= dist) uf.unionSet(i, j);
      }
    }

    map<int,int> cnt;
    rep(i,S){
      if (f[i] == '.') continue;
      int r = uf.root(i);
      ++cnt[r];
    }

    int even=0, odd=0;
    tr(it,cnt){
      int /* r = it->first,*/ c = it->second;
      if (c & 1) ++odd;
      else       ++even;
    }

    if (even == 0 && odd == 0) return 0;

    ll ans = 0LL;
    ll tp = twopow(even); // 2^even
    for (int i=0; i<=odd; i+=2) {
      ll ci = C(odd, i);
      ans = add(ans, mul(tp, ci));
    }
    ans = (ans + MOD - 1) % MOD;

    return (int)ans;
  }
};

じゃああれだ... 2^n とか nCk の計算を高速化するしかない

vector<vector<ll> > c_gen(int c_max) {
  vector<vector<ll> > c(c_max+1);
  c[0].assign(1, 1LL); // 0C0
  for (int i=1; i<=c_max; ++i) {
    c[i].assign(i+1, 1LL);
    for (int j=1; j<i; ++j) {
      ll c_ij = (c[i-1][j-1] + c[i-1][j]) % MOD;
      c[i][j] = c_ij;
    }
  }
  return c;
}

...

ll twopow(ll x) { // 2^x
  ll b = 2LL, r = 1LL;
  while (x) {
    if (x & 1) {
      r = mul(r, b);
    }
    x >>= 1LL;
    b = mul(b, b);
  }
  return r;
}

...

class GooseInZooDivOne {
 public:
  int count(vector<string> field, int dist) {
    ...

    vector<vector<ll> > c = c_gen(odd);

    for (int i=0; i<=odd; i+=2) {
      ll ci = c[odd][i];  // ll ci = C(odd, i);

      ...

今度は 56.166msecなので大丈夫。

注意点

odd=0な場合もあるので 0C0=1がちゃんと出るようにしておくこと。（一回引っかかった）