D,Eが自信なかったけど何とか解けた。
http://codeforces.com/contest/610/problem/C
問題
2^k要素のベクトルが2^k個ある。
各要素は1か-1のいずれかであり、また異なるベクトル同士は直行している。
上記条件を満たすベクトル群の一例を答えよ。
解法
再帰的に構成できる。
2^k要素のベクトル2^k個を並べた行列をAとする。
そこからとする行列を作ると2^(k+1)要素のベクトル2^(k+1)個を作れる。
int N; string S[2020]; string rev(string s) { FORR(r,s) { if(r=='+') r='*'; else r='+'; } return s; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; S[0]="+"; FOR(i,N) { FOR(j,1<<i) { S[j+(1<<i)] = S[j]+rev(S[j]); S[j] += S[j]; } } FOR(i,1<<N) cout<<S[i]<<endl; }
まとめ
これはすんなり。