太简单的不记录，从2023.10.26开始记录。
1.AGC005D
题解
首先容斥，强制 \(i\) 个位置不满足，系数是 \((-1)^i\) ，后面应该乘个 \((n-i)!\) ，表示剩下的任意排，那么应该再乘个 \(f(i)\) 表示这 \(i\) 个位置满足的方案数。
考虑怎么算 \(f(i)\) ，首先建二分图，左边表示位置，右边表示位置上的值。
对于 \(i\) 从 \(1\) 至 \(n\) ，若 \(i+k<=n\) ，将 \(((i,0),(i+k,1)),((i,1),(i+k,0))\) 连一条无向边（ \(0\) 表示左部点，\(1\) 表示右部点。），容易发现原图形成若干条链，那么如果我们选了一条边，则意味着这个位置上的值不满足。
容易发现每条链是独立的，而且我们选出的边必须点不交。
注意到，从一条长度为 \(n\) 的链中选出 \(m\) 条点不交的边，方案数为 \(\binom{n-m}{m}\)，这是因为总共有 \(n-1\) 条边可供选择，而选出的边里除了第一条边，每条边都会ban掉一条前面的边。
因为每条链是独立的，所以接下来就可以合并了，做多项式加法卷积即可，暴力实现的话复杂度是 \(O(n^2)\) 。
Bonus:924844033的原根是5，所以可以做到 \(O(n\ log \ n)\)。
AC记录：Submission #46945971 - AtCoder Grand Contest 005
标签：乘个,表示,选出,记录,位置,每条 From： https://www.cnblogs.com/llzer/p/17790234.html