AGC 017 E Placing Squares

E - Placing Squares

N を増やしたときの差分について観察するとうまく解けるようになる。
M = 0 の場合でも難しいので、まずは M = 0 の場合を考える。
右端の正方形が k*k で、それ以外の正方形の面積の積(=重み)が a であるような状況を考える。
右端に辺を追加すると、
右端の正方形が (k+1)*(k+1)、重みが a になるか、
右端の正方形が 1*1、重みが k*k*a になる。
よく見ると、
(重み)*(右端の正方形の面積) の総和
(重み)*(右端の正方形の辺の長さ) の総和
(重み)*(右端の正方形の個数) の総和
を線形変換しているので、行列累乗で解ける。(試していないが、editorial に書かれている解法で出てくる行列と同じになるはず。)

M が 0 でないときも、遷移が少し変わるだけなので、そこだけ違う行列をかければよい。

typedef vector<ll> vec;
typedef vector<vec> mat;
#define M 100010
ll n, m;
ll d[M];
 
void mul(mat &A, mat &B){
	int n = A.size();
	mat C(n, vec(n, 0));
	rep(k, n) rep(i, n) rep(j, n) C[i][j]+=A[i][k]*B[k][j]%mod;
	A.swap(C);
	rep(i, n) rep(j, n) A[i][j] %= mod;
}
 
int main(){
	scanf("%lld%lld", &n, &m);
	rep(i, m) scanf("%lld",d+i+1);
	d[m+1] = n;
	mat A(3, vec(3, 1));
	A[0][0] = A[0][1] = 2;
	A[2][1] = 0;
	mat B(A);
	rep(i, 3) B[i][0]--;
	mat X(3, vec(3, 0));
	rep(i, 3) X[i][i] = 1;
	rep(i, m+1){
		if(i) mul(X, B);
		ll t = d[i+1]-d[i]-1;
		mat C(A);
		while(t){
			if(t&1) mul(X, C);
			mul(C, C);
			t >>= 1;
		}
	}
	ll res = 0;
	rep(i, 3) res += X[0][i];
	printf("%lld\n", (res+mod)%mod);
	return 0;
}