なんだこれ。
https://community.topcoder.com/stat?c=problem_statement&pm=14463
問題
深さDの完全二分木がある。
各頂点にN色のいずれかの色を塗ることを考える。
まず根にいずれかの色を塗ろう。
今頂点に色cが塗られている場合、左の子頂点はleft[c]、右の子頂点はright[c]で塗られる。
この木のスコアは、葉頂点のうち色がiの頂点がC(i)個あるとするとsum(C(i)^2) mod (10^9+7)である。
根頂点の色を任意に決められる場合、スコアの最大値を求めよ。
解法
木の左右は無視して、深さが1つ深くなると色cの頂点1個から色left[c]およびright[c]の頂点が1個ずつ増えると考える。
この関係を行列で表現すれば、行列のD乗に持ち込める。
あとは行列の累乗テクで高速に行列のD乗を求め、各根頂点の色に対応したスコアを総当たりしよう。
O(N^3*log(D))なので十分間に合う。
const int MAT=105; ll G[MAT][MAT],G2[MAT][MAT]; ll mo=1000000007; void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) { int i,x,y,z; ll a2[MAT][MAT]; FOR(x,n) FOR(y,n) a2[x][y]=a[x][y]; FOR(x,n) FOR(y,n) r[x][y]=(x==y); while(p) { ll h[MAT][MAT]; if(p%2) { FOR(x,n) FOR(y,n) h[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo; FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo; } FOR(x,n) FOR(y,n) h[x][y]=0; FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo; FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo; p>>=1; } } class ChristmasBinaryTree { public: int count(long long depth, vector <int> left, vector <int> right) { int N=left.size(); ZERO(G); int i,j; FOR(i,N) G[left[i]][i]++, G[right[i]][i]++; powmat(depth-1,N,G,G2); ll ma=0; FOR(i,N) { ll tot=0; FOR(j,N) tot+=G2[j][i]*G2[j][i]%mo; ma=max(ma,tot%mo); } return ma; } }
まとめ
これ900ptだったかな。