yukicoder : No.612 Move on grid

これは割とすんなり。
https://yukicoder.me/problems/no/612

問題

３次元座標系において、初期状態で点Pが(0,0,0)にいる。
１秒毎に、隣接する格子点のいずれかに1/6の確率で遷移する。

a,b,c,d,eが与えられたとき、T秒後のPの座標を(x,y,z)としたとき、d ≦ ax+by+cz ≦ eを満たす確率を求めよ。

解法

問題文自体がかなりヒントになっている。
３次元の座標を個別に持ってDPするとTLEするが、最初から座標におけるax+by+czの1つの値だけ保持しておけばよい。
１秒枚に+a,-a,+b,-b,+c,-cのいずれかの 遷移を取る。

int T;
int A,B,C,D,E;
ll from[20202];
ll to[20202];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T>>A>>B>>C>>D>>E;
	int ma=max({abs(A),abs(B),abs(C)});
	from[10100]=1;
	FOR(i,T) {
		ZERO(to);
		for(j=10100-ma*i;j<=10100+ma*i;j++) if(from[j]) {
			from[j]%=mo;
			to[j-A]+=from[j];
			to[j+A]+=from[j];
			to[j-B]+=from[j];
			to[j+B]+=from[j];
			to[j-C]+=from[j];
			to[j+C]+=from[j];
		}
		swap(from,to);
	}
	
	ll ret=0;
	for(i=10100+D;i<=10100+E;i++) ret+=from[i];
	cout<<ret%mo<<endl;
}

まとめ

こちらも★2.5でもいいかも？
小難しいライブラリとか使わないしね。