AtCoder Grand Contest 050 (Good Bye rng_58 Day 1) D問題 - Shopping

Source

AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)
問題文

問題概要

省略

解法

省略

cLay（version 20201228-1）のコード

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

#define MD 998244353

int N, K;
int vis[41][41][41];
Modint ans[41][41][41][41];

void solve(int n, int b, int s){
  int r, tt;
  Modint p;

  if(vis[n][b][s]) return;
  vis[n][b][s] = 1;
  if(n==0) return;

  if(s == 0){
    solve(n, b+1, n);
    rep(i,n) ans[n][b][s][i] = ans[n][b+1][n][i];
    return;
  }

  r = K - (N - n);
  tt = K - b;
  if(r==0) return;

  p = Modint(r) / tt;
  if(p != 0){
    solve(n-1, b, s-1);
    ans[n][b][s][0] += p;
    rep(i,n-1) ans[n][b][s][i+1] += p * ans[n-1][b][s-1][i];
  }

  p = 1 - Modint(r) / tt;
  if(p != 0){
    solve(n, b, s-1);
    rep(i,n) ans[n][b][s][(i+1)%n] += p * ans[n][b][s-1][i];
  }
}

{
  rd(N, K);
  solve(N, 0, N);
  rep(i,N) wt(ans[N][0][N][i]);
}

Current time: 2024年04月24日13時04分48秒
Last modified: 2020年12月28日21時11分33秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC050 AGC_D
トップページに戻る

Logged in as: unknown user (not login)