CF1227F2.Wrong Answer on test 233 (Hard Version)
我们设 \(f_i\) 表示考虑完所有的位置以后，循环右移比原序列答案更多的序列数。
这题非常关键的一点是：\(f_i=f_{-i}\) ，意思是你把每个放“和当前位置不同但和下一个位置相同”的数换成“和当前位置相同但是和下一个位置不同的方案数”。有了这个性质，我们考虑一下所求。
因为：
\[k^n=\sum_{i=-n}^nf_i \]所以有
\[\sum_{i=1}^nf_i=\frac{k^n-f_0}{2} \]那么现在就转化为了如何求解 \(f_0\) ，我们枚举有多少个“对改错”，那么“错改对”数量是一样的。
\[f_0=\sum_{i=0}^{\frac{m}{2}}{m \choose i}{m-i \choose i}(k-2)^{n-2i}k^{n-m} \]CF997C.Sky Full of Stars
和昨天做的那道题有点像，不过毒瘤了若干倍。
依旧是设 \(f_{i,j}\) 表示钦定 \(i\) 行 \(j\) 列颜色相同，剩余随意的方案数。\(g_{i,j}\) 表示恰好 \(i\) 行 \(j\) 列颜色相同的方案数。
\[f_{i,j}=\sum_{k=i}^n\sum_{t=j}^n{k \choose i}{t\choose j}g_{k,t} \]然后这里是一个二维的二项式反演。
我们假设反演完的式子是
\[g_{i,j}=\sum_{k=i}^n\sum_{t=j}^na_ka_tf_{k,t} \]其中 \(a_t\) 和 \(a_k\) 分别是关于 \(t,k\) 的系数，我们现在要够造出这个系数。
考虑将 \(f_{i,j}\) 关于 \(g\) 的递推式带入
\[g_{i,j}=\sum_{k=i}^n\sum_{t=j}^n a_ka_t\sum_{x=k}^n\sum_{y=t}^n{x\choose k}{y \choose t}g_{x,y} \]\[g_{i,j} =\sum_{x=i}^n\sum_{y=j}^ng_{x,y}\sum_{k=i}^xa_k{x \choose k}\sum_{t=j}^ya_t{y \choose t} \]要让两边变成恒等式，也就是
\[g_{i,j}=g_{i,j} \]我们考虑怎样才能实现，我们只要让
\[\sum_{k=i}^xa_k{x \choose k}=[x=i] \]由于
\[\sum_{k=i}^x (-1)^{k-i}{i \choose k}{ x \choose k} \]因此直接构造系数
\[a_k=(-1)^{k-i}{k \choose i} \]代回最开始的式子
\[g_{i,j}=\sum_{k=i}^n\sum_{t=j}^n(-1)^{k-i}{k \choose i}(-1)^{t-j}{t \choose j}f_{k,t} \]最终答案就是 \(3^{n^2}\) 减去 \(g_{0,0}\)
考虑 \(f\) 的计算式再将其代入 \(g\)
当 \(i,j\) 均不等于 \(0\) 时，
\[f_{i,j}=3{n \choose i}{n \choose j}3^{(n-i)(n-j)} \]当 \(i,j\) 中恰好有一个等于 \(0\) 时
\[f_{i,0}={n \choose i}3^i3^{n(n-i)} \]当 \(i,j\) 均等于 \(0\) 时
\[f_{0,0}=3^{n^2} \]后两种都可以直接代入暴力计算，考虑第一种，将 \(f\) 代入
\[\sum_{k=1}^n\sum_{t=1}^n(-1)^{k+t}3{n \choose k}{n \choose t}3^{(n-k)(n-t)} \]\[=3^{n^2+1}\sum_{k=1}^n(-1)^k{n \choose k}3^{-kn}\sum_{t=1}^n(-1)^t{n \choose t}3^{t(k-n)} \]\[=3^{n^2+1}\sum_{k=1}^n(-1)^k{n \choose k}3^{-kn}\sum_{t=1}^n{n \choose t}(-3^{k-n})^t \]\[=3^{n^2+1}\sum_{k=1}^n(-1)^k{n \choose k}3^{-kn} \left((1-3^{k-n})^n-1 \right) \]然后无视逆元这一部分就可以 \(O(n)\) 计算了。
然后这一题就做完了！
标签：11,sum,位置,kn,代入,choose,考虑,2022.1 From： https://www.cnblogs.com/oscaryangzj/p/17044351.html