AtCoder Beginner Contest 180 F問題 - Unbranched

Source

AtCoder Beginner Contest 180
問題文

問題概要

省略

解法

省略

cLay（version 20201018-2）のコード

C++に変換後のコードはこちら

int N, M, L;
Modint dp[301][301], pre1[301][301], pre2[301][301];
Comb<Modint> c;

Modint solve(int L){
  if(L==0) return 0;

  rep(i,N+1) rep(j,M+1) dp[i][j] = 0;
  dp[0][0] = 1;

  rep(i,N+1) rep(k,1,L+1) pre1[i][k] = c.C(N-i-1, k-1) * c.fac(k) / 2;
  rep(i,N+1) rep(k,1,L+1) pre2[i][k] = c.C(N-i-1, k-1) * c.fac(k-1) / 2;

  rep(i,N+1) rep(j,M+1) if(dp[i][j] != 0){
    rep(k,1,L+1){
      if(i+k > N) break;
      if(k==1){
        if(i+k <= N && j+k-1 <= M) dp[i+k][j+k-1] += dp[i][j];
      } else if(k==2){
        if(i+k <= N && j+k-1 <= M) dp[i+k][j+k-1] += dp[i][j] * (N-i-1);
        if(i+k <= N && j+k <= M) dp[i+k][j+k] += dp[i][j] * (N-i-1);
      } else {
        if(i+k <= N && j+k-1 <= M) dp[i+k][j+k-1] += dp[i][j] * pre1[i][k];
        if(i+k <= N && j+k <= M) dp[i+k][j+k] += dp[i][j] * pre2[i][k];
      }
    }
  }

  return dp[N][M];
}

{
  Modint res;
  rd(N,M,L);
  res += solve(L);
  res -= solve(L-1);
  wt(res);
}

Current time: 2024年04月18日19時05分29秒
Last modified: 2020年10月18日15時13分41秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC180 ABC_F
トップページに戻る

Logged in as: unknown user (not login)