SRM 644 Div1 Medium MakingTournament

実験すると、K=1 のときは、フィボナッチ数列になる。
K>1 のときは、2^K +1 項間漸化式になりそうなので、最初の 2^K +1 項あたりまでを愚直に計算すると、行列を復元することができる。

というのを実装したら通った。直感的には正しいことが分かるが、ちゃんと証明して解きたい。

#define M 300
ll f[7][M], g[7][M];

ll pow_mod(ll a, ll r, ll m){
	ll x = 1;
	while(r){
		if(r&1) (x*=a)%=m;
		(a*=a)%=m;
		r>>=1;
	}
	return x;
}

vector<ll> mul(vector<vector<ll>> &A, vector<ll> &x){
	int n = x.size();
	vector<ll> y(n, 0);
	rep(i, n) rep(j, n) (y[i]+=A[i][j]*x[j])%=mod;
	return y;
}

void mul(vector<vector<ll>> &A){
	vector<vector<ll>> B(A);
	int n = A.size();
	A = vector<vector<ll>>(n, vector<ll>(n, 0));
	rep(k, n) rep(i, n) rep(j, n) (A[i][j]+=B[i][k]*B[k][j])%=mod;
}

class MakingTournament {
	public:
	int howManyWays(long long N, int K) {
		mset(f, 0); mset(g, 0);
		rep(i, M) g[0][i] = 1;
		g[0][1] = 0;
		f[0][0] = 1;
		for(ll i = 2; i < M; i++) f[0][i] = (f[0][i-1]+f[0][i-2])%mod;

		for(ll k = 1; k < 6; k++){
			rep(i, M) g[k][i] = (f[k-1][i]-g[k-1][i]+mod)%mod;
			f[k][0] = 1;
			rep(i, M) rep(j, i) (f[k][i]+=f[k][j]*g[k][i-j])%=mod;
		}
		ll m = 1<<K;
		vector<vector<ll>> A(m, vector<ll>(m, 0));
		rep(i, m-1) A[i+1][i] = 1;
		rep(i, m){
			ll sum = 0;
			rep(j, m) (sum+=f[K-1][i+j+1]*A[0][m-j-1])%=mod;
			A[0][i] = (f[K-1][i+m+1]-sum+mod)%mod;
		}
		vector<ll> x(m, 0);
		x[0] = 1;
		N--;
		while(N){
			if(N%2) x = mul(A, x);
			mul(A);
			N>>=1;
		}
		return (x[m-1]+mod)%mod;
	}
};