Solution Set - 神奇 NOIP 模拟賽

\[\mathfrak{\text{Defining }\LaTeX\text{ macros...}}\newcommand{\vct}[1]{\boldsymbol{#1}}\newcommand{\stir}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}\newcommand{\opn}[1]{\operatorname{#1}}\newcommand{\lcm}[0]{\opn{lcm}}\newcommand{\sg}[0]{\opn{sg}}\newcommand{\dist}[0]{\opn{dist}}\newcommand{\lca}[0]{\opn{lca}}\newcommand{\floor}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor}\newcommand{\ceil}[2]{\left\lceil\frac{#1}{#2}\right\rceil}

\]

  2021.10.29.

  「A. 莓良心」 給定 \(\{w_n\}\)，對于所有将其劃分為 \(k\) 個非空集合的方式，求 \(w_i\times (w_i\text{ 所在集合大小})\) 之和的總和模 \(998244353\) 的值。\(n\le10^6\)。

  考慮算每個 \(w_i\) 的貢獻次數，首先 \(w_i\) 自己算一次，\(\stir{n}{k}\)；任意 \(j\not=i\) 的 \(w_j\) 和 \(w_i\) 放一次時貢獻一次，\((n-1)\stir{n}{k-1}\)，\(\mathcal O(n)\) 算第二類斯特林數單點值即可。

  「B. 盡梨了」 給定 \(\{(a,b)_n\}\)，初始時 \(t=0\)，每次選一個未選過的 \(i\)，令 \(t\leftarrow(a_i+1)(t+1)+b_i\)，需要保證此時 \(t\le m\)。求最多能選擇的次數。\(n\le2\times10^5\)，\(m\le10^9\)。

  交換貪心可知确定要選的集合時最優的選取順序，依此排序後，問題變為從其中依次取子序列。注意到 \(a=0\) 的必然最後選，且按 \(b\) 從小到大選；\(a\not=0\) 每次選擇至少有 \(t\leftarrow 2(t+1)\)，對于這種情況直接 DP，最後考慮 \(a=0\) 即可。複雜度 \(\mathcal O(n\log m)\)。

  「C. 團不過」 有求 \(n\) 堆有标号石子堆，每堆石子數量在 \([1,2^n)\) 且不存在兩堆相同數量石子堆時，Nim 先手必勝的方案數。\(n\le10^7\)。