AtCoder Beginner Contest 160 F問題 - Distributing Integers

Source

AtCoder Beginner Contest 160
問題文

問題概要

省略

解法

省略

cLay（version 20201229-1）のコード

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

int N, A[2d5], B[2d5];
graph g;
Modint res[2d5];
Comb<Modint> c;

int num[2d5];

int dfs1(int n, int b){
  num[n] = 1;
  rep[g.edge[n]](i,g.es[n]){
    if(i == b) continue;
    num[n] += dfs1(i, n);
  }
  return num[n];
}

void dfs2(int n, int b, Modint val){
  int mem_n, mem_i;
  Modint mem_v;
  res[n] = val;
  rep[g.edge[n]](i,g.es[n]){
    if(i == b) continue;
    mem_n = num[n];
    mem_i = num[i];
    mem_v = val;

    num[n] -= num[i];
    num[i] = N;

    val *= mem_n;
    val *= mem_i;
    val /= num[n];
    val /= num[i];
    dfs2(i, n, val);
    num[n] = mem_n;
    num[i] = mem_i;
    val = mem_v;
  }
}

{
  Modint val;

  rd(N,(A--,B--)(N-1));
  g.setEdge(N,N-1,A,B);
  rep(i,N) sortA(g.es[i], g.edge[i]);

  dfs1(0, -1);
  val = c.fac(N);
  rep(i,N) val /= num[i];
  dfs2(0, -1, val);
  wtLn(res(N));
}

Current time: 2024年04月26日01時25分43秒
Last modified: 2021年01月02日18時55分19秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC160 ABC_F
トップページに戻る

Logged in as: unknown user (not login)