これは割とすんなり。
https://yukicoder.me/problems/no/612
問題
3次元座標系において、初期状態で点Pが(0,0,0)にいる。
1秒毎に、隣接する格子点のいずれかに1/6の確率で遷移する。
a,b,c,d,eが与えられたとき、T秒後のPの座標を(x,y,z)としたとき、d ≦ ax+by+cz ≦ eを満たす確率を求めよ。
解法
問題文自体がかなりヒントになっている。
3次元の座標を個別に持ってDPするとTLEするが、最初から座標におけるax+by+czの1つの値だけ保持しておけばよい。
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でもいいかも?
小難しいライブラリとか使わないしね。