Codeforces Round #175 (Div. 2)

A. Slightly Decreasing Permutations

• 后(k)个倒序放前面，前(n-k)个顺序放后面。

---

B. Find Marble

• 模拟。

---

C. Building Permutation

• 排序。

---

D. Permutation Sum

• 折半，(a_i) 固定为(1,cdots,n)，(A_{16}^{8})枚举前半部分(b_i)，记录(、Bmask、Cmask)，表示数的使用状态。
• 然后(A_{16}^{8})枚举后半部分，同样记录(、Bmask、Cmask)，那么只要两个状态翻转，累加前半部分对应状态的方案数即可。

---

E. Positions in Permutations

• (dp(i,j,k))表示前i个存在j个gp的方案数，k表示(、、i-1、i、i+1)位置占用情况。
• 这样的转移会存在某些数没有放置的情况，假设当前已经有(i)个gp，那么乘上((n-i)!)则表示至少有(i)个gp的方案数，用(f[i])表示。
• 那么$$ans[i] = f[i] - sum_{j = i + 1} ^ {n} {inom{j}{i} cdot ans[j]} $$