AtCoder ABC #198 : F - Cube

最近のABCでは最難？
https://atcoder.jp/contests/abc198/tasks/abc198_f

問題

正整数Sが与えられる。
立方体の6面に和がSとなるよう正整数を書き込む。
回転させて面の値が一致するものは単一とみなすとするとき、その組み合わせは何通りか。

解法

ポリアと立方体で検索すると、資料が見つかる。
http://www.aoni.waseda.jp/sadayosi/course/past/comb06/chapter3.pdf
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/2016-16.pdf

下記の5パターンの総和を取り、全体を24で割ればよい。
(違う名前の変数が同じ値を取ってもよい)

• (a+b+c+d+e+f=Sの組み合わせ)×1
• (a+b+2c+2d=Sの組み合わせ)×3
• (a+b+4c=Sの組み合わせ)×6
• (2a+2b+2c=Sの組み合わせ)×6
• (3a+3b=Sの組み合わせ)×8

それぞれの変数の組み合わせだが、「最後に何番目の変数にインクリメントしたか」という状態を考えるとDPで数え上げることができる。
Sが大きいので行列累乗で高速化しよう。

ll S;
const ll mo=998244353;

ll modpow(ll a, ll n=mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

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

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;
}

ll hoge(int a,int b,int c,int d,int e,int f) {
	Mat A;
	vector<int> V={a,b,c,d,e,f};
	int i,j;
	FOR(i,6) {
		FOR(j,3) {
			A.v[(j+1)*6+i][j*6+i]=1;
		}
		if(V[i]) {
			FOR(j,i+1) A.v[i][(V[i]-1)*6+j]=1;
		}
	}
	A=powmat(S,A);
	ll ret=0;
	FOR(i,6) ret+=A.v[i][0];
	
	return ret%mo;
	
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>S;
	
	S-=6;
	ll ret=0;
	
	ret+=hoge(1,1,1,1,1,1);
	ret+=3*hoge(1,1,2,2,0,0);
	ret+=6*hoge(1,1,4,0,0,0);
	ret+=6*hoge(2,2,2,0,0,0);
	ret+=8*hoge(3,3,0,0,0,0);
	
	ret=ret%mo*modpow(24)%mo;
	cout<<ret<<endl;
	
}

まとめ

組み合わせ計算でどうにかしようと考えすぎて、行列累乗に至らなかったのが残念。