Codeforces Round #232

http://codeforces.com/contest/396
http://user.qzone.qq.com/251815992/blog/1393572631

Problem A. On Number of Decompositions into Multipliers

Brief description:

給定一個數,問分拆成 n 個整數乘積的方案有多少種。

Analysis:

。。每個素因子是獨立的。。乘法原理。。
考察某個素因子,假設出現了 m 次。。那麼就是將 m 個球放進 n 個盒子中的方案數。。。
隔板法即可。

Problem B. On Sum of Fractions

Brief description:

。。

Analysis:

裂項。

Problem C. On Changing Tree

Brief description:

給出一棵有根樹,支持以下兩種操作:

  • 1 u a k:表示對以 u 為根的子樹,對每個結點添加 a-dk,其中 d 是該結點與 v 的距離。
  • 2 u:查詢節點 v 的值。

Analysis:

。如果 d = 0。。那麼顯然就是。。
http://www.shuizilong.com/house/archives/poj-3321-apple-tree/

這裡我們只需要維護兩個樹狀數組 c1, c2
每次修改時。。
。。對 c1 += a ,c2 += d。。。
詢問時返回 c1 - dep[v]*c2 。。。
(這樣會多減去一點。。再從 c1 里加上。。。)

http://codeforces.com/contest/396/submission/5971492