TopCoder SRM 644 Div1 Medium MakingTournament

これは本番解ききれなかったので、Unratedで助かったかも？

問題

1～N番まで番号を振られたN人の人がおり、K回戦まで行うトーナメントを考える。
各回戦では、人を番号順に２人以上何人かずつグループを組み、その勝者だけが次の回戦に進む。

K回戦終わった段階で、１人以上残るようなトーナメントの組み合わせ方を求めよ。

解法

状態遷移を考えて、行列乗算で解く。

1番の人から順にトーナメントに加えていくことを考える。

状態としては、各回戦に残っている参加者の有無を考えればよく、1～K回戦で戦う相手が１人以上残ってるかどうか2^K通りが考えられる。
最後に付け加えられた人がx回戦まで行くには、1～(x-1)回戦まで戦う相手が残っている場合であり、かつその人がx回戦まで行くと、1～(x-1)回戦は戦う相手がもう残っていない、と考えて状態遷移を行列表記に置き換えていく。

const int MAT=128;
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]=0;
	FOR(i,n) r[i][i]=1;
	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 MakingTournament {
	public:
	int howManyWays(long long N, int K) {
		int i,j,x,y;
		ZERO(G);
		
		FOR(i,1<<K) {
			FOR(j,K+1) if((i&((1<<j)-1))==((1<<j)-1)) {
				x=(i | (1<<j)) ^ ((1<<j)-1);
				if(j==K) x=0;
				G[x][i]=1;
			}
		}
		powmat(N,1<<K,G,G2);
		return G2[0][0]%mo;
	}
}

まとめ

行列累乗のコードがほとんどで、それ以外は行列を作るちょっとしたコードだけ。
本番行列累乗自体は頭に浮かんだけど、この行列は思い浮かばなかった。