問題名は関係なかった。
https://codeforces.com/contest/1286/problem/D
問題
1次元の数直線上にN個のパーティクルがあり、それぞれの初期位置が与えられる。
各パーティクルについて、移動の速さが与えられる。
また左右どちらに動くかの確率が与えられる。
2つのパーティクルが最初に衝突する時刻の期待値を求めよ。
解法
考える衝突は、初期状態で隣接するパーティクル同士のみで良い。
パーティクルの移動の向き毎に、衝突時刻を求め昇順に処理しよう。
SegTreeを使い、パーティクルの区間において、両端のパーティクルの移動の向きが与えられたとき、その中で未衝突となる確率を計算しよう。
処理の際、その状態に至る2パーティクルの状態が最初の衝突となる確率をこのSegTreeを用いて求めることができる。
衝突の時刻と確率の重みづけ平均を取ればそれが解。
int N; int X[101010],V[101010],P[101010]; const ll mo=998244353; struct mat{ ll p[2][2]; }; mat val[1<<19]; mat mul(mat& L, mat& R) { mat V; int x,y; FOR(x,2) FOR(y,2) V.p[x][y]=(L.p[x][0]*R.p[0][y]+L.p[x][1]*R.p[1][y])%mo; return V; } ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } bool cmp(vector<int>& L,vector<int>& R) { return 1LL*L[0]*R[1]<1LL*R[0]*L[1]; } vector<vector<int>> cand; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>X[i]>>V[i]>>P[i]; val[i+(1<<18)].p[0][0]=val[i+(1<<18)].p[0][1]=(100-P[i])*modpow(100)%mo; val[i+(1<<18)].p[1][0]=val[i+(1<<18)].p[1][1]=P[i]*modpow(100)%mo; } for(i=N;i<1<<18;i++) val[i+(1<<18)].p[1][0]=val[i+(1<<18)].p[1][1]=1; for(i=(1<<18)-1;i>=1;i--) val[i]=mul(val[2*i],val[2*i+1]); FOR(i,N-1) { if(V[i]<V[i+1]) cand.push_back({(X[i+1]-X[i]),V[i+1]-V[i],i,0,0}); if(V[i]>V[i+1]) cand.push_back({(X[i+1]-X[i]),V[i]-V[i+1],i,1,1}); cand.push_back({(X[i+1]-X[i]),(V[i]+V[i+1]),i,1,0}); } sort(ALL(cand), cmp); ll ret=0; ll pre=0; FORR(c,cand) { ll P=(val[1].p[0][1]+val[1].p[1][1])%mo; i=(c[2]+(1<<18)); val[i].p[c[3]][c[4]]=0; while(i>1) { i/=2; val[i]=mul(val[2*i],val[2*i+1]); } ll Q=(val[1].p[0][1]+val[1].p[1][1])%mo; P=(P-Q+mo)%mo; (ret+=P*c[0]%mo*modpow(c[1]))%=mo; } cout<<ret<<endl; }
まとめ
なんでこんな問題名にしたんだ。