定番テクを知っていると非常に簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=15140
問題
R*Cの大きさの0/1の2値からなる行列を考える。
このうち、各行・各列における1の登場数が偶数であるものを辞書順昇順に並べたとき、K番目に来るのはどれか。
解法
行・列それぞれパリティが0になっていなければならないという条件が厄介。
ただこれは対応が容易で、左上(R-1)列(C-1)行は何でもよく、そこを決めると最右列・最下段が確定する。
よって左上(R-1)列(C-1)行を合わせて(R-1)*(C-1)桁の2進数とみなしたときそれがKとなるように1を入れていけばよい。
あとは最右列・最下段を埋めよう。
class EvenMatrices { public: vector <string> findKth(int r, int c, long long k) { vector<string> V,E; int y,x; FOR(y,r) V.push_back(string(c,'0')); int left=(r-1)*(c-1); FOR(y,r-1) FOR(x,c-1) { left--; if(left>60) continue; if(k>=1LL<<left) { V[y][x]^=1; V[r-1][x]^=1; V[y][c-1]^=1; V[r-1][c-1]^=1; k-=1LL<<left; } } return k?E:V; } }
まとめ
パリティ指定のある行列は、(R-1)行(C-1)列は何でもよい、というテクは定番なので使えるようになっておこう。