yukicoder No.907 - Continuous Kadomatu

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLayversion 20191102-1)のコード

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)

ログイン: