计数场。

T1 AGC036F. Square Constraints

zzz 哥哥搬的 nb 题，还不会。

T2 「LibreOJ NOI Round #2」不等关系

zrq 学长讲过的题诶。

只满足 \(\texttt <\) 关系的话，答案是个多重集排列 \(\dfrac{n!}{\prod a_i!}\)。

这样算会让一些 \(\texttt >\) 不满足，考虑容斥，枚举 \(\texttt >\) 的一个子集 \(|T|\) 强制不满足，容斥系数为 \((-1)^{|T|}\)。

关注每选一个 \(\texttt >\) 对容斥系数的贡献，那么可以做一个 DP，\(f_i\) 表示前 \(i\) 个段的 \(\frac{1}{\prod a_i!}\) 乘容斥系数之和。发现转移是半在线卷积，分治 NTT 即可 \(\mathcal O(n\log^2n)\)。

T3 ARC102C. Stop. Otherwise...

对于权值 \(i\)，如果 \(i<x\)，\(i\) 和 \(x-i\) 只能允许其中一个被选；特别地，\(i=x-i\) 时，这个值至多选一个；其余的值随意选。

设第一类权值对有 \(a\) 个，随意选的权值有 \(b\) 个。

列出式子，

\[\sum_{i=0}^a\binom{a}{i}2^i\sum_{j=i}^n\binom{j-1}{i-1}\left(\binom{n-j+b-1}{b-1}+\binom{n-1-j+b-1}{b-1}\right), \]

可以 \(\mathcal O(n^3)\)。

改一改，

\[\sum_{j=0}^n\left(\binom{n-j+b-1}{b-1}+\binom{n-1-j+b-1}{b-1}\right)(j-1)!\sum_{i=0}^{\min(a,j)}\binom{a}{i}2^i\frac{1}{(i-1)}\frac{1}{!(j-i)!} \]

把 T2 写的 NTT 粘过来就 \(\mathcal O(n^2\log n)\) 了。

幸好给的 \(2000\)，简单卡卡常就过了。

---

下面记录一个更优秀的做法：

• 考虑二选一权值对的 OGF为 \(1+2x+2x^2+\dots\)；
• 至多选一次的权值的 OGF 为 \(1+x\)；
• 随意选的权值的 OGF 为 \(1+x+x^2+\dots\)。

最后分配 \(n\) 个骰子的权值，答案为

\[[x^n]\left(\frac{1+x}{1-x}\right)^a\cdot (1+x)^{[2|x]}\cdot \left(\frac{1}{1-x}\right)^b \]

\[[x^n]\frac{(1+x)^A}{(1-x)^B} \]

我们知道 \([x^i](1+x)^A=\dbinom{A}{i}\)，\([x^i]\dfrac{1}{(1-x)^B}=\dbinom{i+B-1}{B-1}\)，每次可以 \(\mathcal O(n)\) 卷积得到单点答案。总复杂度 \(\mathcal O(nK)\)。