エイシング プログラミング コンテスト 2020 : F - Two Snuke

いくつか解法がある問題。
https://atcoder.jp/contests/aising2020/tasks/aising2020_f

問題

正整数Nが与えられる。
10個の変数s1,s2,n1,n2,u1,u2,k1,k2,e1,e2について、

• いずれも整数で総和はN以下
• 0≦s1＜s2
• 0≦n1＜n2
• 0≦u1＜u2
• 0≦k1＜k2
• 0≦e1＜e2

を満たす組における(s2-s1)(n2-n1)(u2-u1)(k2-k1)(e2-e1)の総和を10^9+7で割った余りを求めよ。

解法

15次程度の式になるので、式変形やラグランジュ補間をする方法と、組み合わせで解く解法がある様子。
ここではEditorial同様後者で説明。

s2-s1=Δs、以下同様にすると
0≦2*(s1+n1+u1+k1+e1)+(Δs+Δn+Δu+Δk+Δe)≦Nとなる非負整数を割り当て、Δs*Δn*Δu*Δk*Δeを求める問題となる。

これをまず以下のように言い換えよう。

• N個のボールの間に、10個の仕切りを入れ、s1,n1,u1,k1,e1,Δs,Δn,Δu,Δk,Δe,以後余り、の11要素に分解することを考える。
• ただしs1～e1に相当する仕切りは、間のボールが偶数でないといけない。

これだと単に変数の決め方の総数になるので、Δs*Δn*Δu*Δk*Δeの総和に腹ならない。

Δs個のボールの間にもう1個仕切りを入れようとするとそれは(Δs-1)通りの入れ方があることになる。
これを利用してもう少し変形しよう。

• N-5個のボールの間に11個の仕切りを入れ、s1,n1,u1,k1,e1,Δs1,Δs2,Δn1,Δn2,Δu1,Δu2,Δk1,Δk2,Δe1,Δe2,以後余り、の16要素に分解することを考える。(N-5なのは、Δs～Δeに最低1個を先に割り当てるため)
• ただしs1～e1に相当する仕切りは、間のボールが偶数でないといけない。

先頭5要素についてはパリティの値を状態として持つようにすると、全体で21通りの状態に対する先頭n個のボールの分解の仕方の漸化式が組める。
あとは行列累乗の要領で数え上げよう。

const int MAT=21;
struct Mat { ll v[MAT][MAT]; Mat(){ZERO(v);};};
const ll mo=1000000007;

Mat mulmat(Mat& a,Mat& b,int n=MAT) {
	ll mo2=4*mo*mo;
	int x,y,z; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(x,n) FOR(z,n) FOR(y,n) {
		r.v[x][y] += a.v[x][z]*b.v[z][y];
		if(r.v[x][y]>mo2) r.v[x][y] -= mo2;
	}
	FOR(x,n) FOR(y,n) r.v[x][y]%=mo;
	return r;
}

Mat powmat(ll p,Mat a,int n=MAT) {
	int i,x,y; Mat r;
	FOR(x,n) FOR(y,n) r.v[x][y]=0;
	FOR(i,n) r.v[i][i]=1;
	while(p) {
		if(p%2) r=mulmat(r,a,n);
		a=mulmat(a,a,n);
		p>>=1;
	}
	return r;
}


int T;
int N;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	Mat A;
	FOR(i,10) {
		A.v[i^1][i]=1;
		if(i%2==0) {
			for(j=1;j<10;j+=2) if(j>i+1) A.v[j][i]++;
			for(j=10;j<21;j++) A.v[j][i]++;
		}
	}
	for(i=10;i<21;i++) {
		for(j=i;j<21;j++) A.v[j][i]++;
	}
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		if(N<5) {
			cout<<0<<endl;
		}
		else {
			Mat B=powmat(N-4,A);
			cout<<B.v[20][0]<<endl;
		}
	}
}

まとめ

どちらの解法もパッと浮かばなかったな…。