SRM 274 DIV1 Hard RingImposition

問題 Editorial

問題

数列seqが与えられる。この数列に"imposition"という操作をN回行った後の数列を求めよ。
"imposition": 各要素にその次(最後の要素の次は最初の要素)の要素をmod100で足す

• 2 <= |seq| <= 50
• 0 <= seq[i] <= 99
• 1 <= N <= 2*10^9

解答

行列累乗するだけ。
(A[i][i] = 1; A[(i+1)%n][i] = 1)。
行列がCirculantなのでO(|seq|^2 log N)でもできるが、普通にO(|seq|^3 log N)でやっても十分速い

コード

ライブラリはhttp://d.hatena.ne.jp/anta1/20130114/1358108415参照

#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define pb(x) push_back(x)
using namespace std;
typedef vector<int> vi; typedef long long ll;
typedef unsigned int Num;
#define MOD 100
#define assert(_)

struct Matrix {
	vector<vector<Num> > v, w;
	Matrix() {}
	Matrix(int n, int m): v(n, vector<Num>(m)) { assert(n > 0 && m > 0); }
	inline int height() const { return (int)v.size(); }
	inline int width() const { return (int)v[0].size(); }
	inline Num& at(int i, int j) { assert(0 <= i && i < height() && 0 <= j && j < width()); return v[i][j]; }
	inline const Num& at(int i, int j) const { assert(0 <= i && i < height() && 0 <= j && j < width()); return v[i][j]; }
	static Matrix identity(int n) {
		Matrix A(n, n);
		rep(i, n) A.at(i, i) = 1;
		return A;
	}
	inline static Matrix identity(const Matrix& A) {
		assert(A.height() == A.width()); return identity(A.height()); }
	Matrix& operator*=(const Matrix& B) {
		int n = height(), m = B.width(), p = B.height();
		assert(p == width());
		w.resize(n, vector<Num>(m, 0));
		rep(i, n) rep(j, m) {
			Num x = 0;
			rep(k, p) {
				x += at(i, k) * B.at(k, j);
			}
			x %= MOD;
			w[i][j] = x;
		}
		v.swap(w);
		return *this;
	}
};

template<typename Mat>
Mat operator^(const Mat& t, ll k) {
	Mat A = t, B = Mat::identity(t);
	while(k) {
		if(k & 1) {
			B *= A;
		}
		A *= A;
		k >>= 1;
	}
	return B;
}

struct RingImposition {
	vector <int> predict(vector <int> seq, int N) {
		int n = seq.size();
		Matrix A(n, n);
		rep(i, n) A.at(i, i) = A.at((i+1)%n, i) = 1;
		Matrix V(1, n);
		rep(i, n) V.at(0, i) = seq[i];
		V *= A ^ N;
		vi r;
		rep(i, n) r.pb(V.at(0, i));
		return r;
	}
};