省略
省略
C++に変換後のコードはこちら
int N, A[200], B[200];
int x[200], y[200], v[400], m;
Modint dp[200][400], dp2[200][400], w[400], abwi[200];
Modint coef[201], dd[201], nn[201];
{
int s, e;
Modint res, tmp, mul;
Comb<Modint> comb;
rd(N,(A,B)(N));
rep(n,1,N+1){
rep(i,n) dd[i] = 0;
dd[n] = 1;
rep(k,n){
s = n - k;
nn[0] = dd[s];
rep(i,1,s) nn[i] = nn[i-1] + dd[s-i];
rep(i,s) dd[i] = nn[i];
}
coef[n] = dd[0] * comb.ifac(n);
}
m = coordcomp(N, A, N, B, x, y) - 1;
rep(i,N) v[x[i]] = A[i], v[y[i]] = B[i];
rep(i,m) w[i] = v[i+1] - v[i];
rep(i,N) abwi[i] = Modint(1) / Modint(B[i] - A[i]);
rep(k,m) if(x[0] <= k < y[0]) dp[0][k] = dp2[0][k] = w[k] * abwi[0];
rep(i,1,N){
rep(k,m) if(x[i] <= k < y[i]){
tmp = w[k] * abwi[i];
if(i%2==0) s = k+1, e = m;
else s = 0, e = k;
rep(j,s,e) dp[i][k] += tmp * dp[i-1][j];
dp2[i][k] = dp[i][k];
mul = 1;
rrep(z,i){
if(!(x[z] <= k < y[z])) break;
dp[i][k] += tmp * dp2[z][k] * coef[i-z+1] * mul;
mul *= w[k] * abwi[z];
}
}
}
res = 0;
rep(k,m) res += dp[N-1][k];
wt(res);
}
Current time: 2024年03月28日19時37分39秒
Last modified: 2019年11月02日11時41分07秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る
Logged in as: unknown user (not login)