超立方体 - 题解
Naszt
·
·
题解
超立方体
> Problem Link <
设计说明
| 样例点是按照以下梯度设计的： |
算法 |
期望得分 |
| 递推 |
Subtask 0 |
| 部分公式 |
Subtask 1 |
| 普通公式 |
Subtask 1+2 |
| NTT / 整式递推 |
100 分 |
算法
递推 | Subtask 0
我们可以使用 \Theta(nm) 的递推：
从点 (0,0,0,\dots,0) 出发。
称 a^{[x_1,x_2,x_3,\dots,x_n]}_m 为走过 m 条棱后到达点 (x_1,x_2,x_3,\dots,x_n) 的方案总数。
容易得到递推关系式（记 \neg 为非运算）：
a^{[x_1,x_2,\dots,x_n]}_m=a^{[\neg x_1,x_2,\dots,x_n]}_{m-1}+a^{[x_1,\neg x_2,\dots,x_n]}_{m-1}+\dots+a^{[x_1,x_2,\dots,\neg x_n]}_{m-1}
可以发现当 x_1+x_2+\dots+x_n=y_1+y_2+\dots+y_n 时：
a^{[x_1,x_2,\dots,x_n]}_m=a^{[y_1,y_2,\dots,y_n]}_m
于是记 \lambda=x_1+x_2+\dots+x_n 可得递推式：
a^{[\lambda]}_m=(n-\lambda)a^{[\lambda+1]}_{m-1}+\lambda a^{[\lambda-1]}_{m-1}
普通公式 | Subtask 1+2
构造循环群 Z_2^n，其生成元分别为 x_1,x_2,\dots,x_n。
有生成函数：
f(x_1,x_2,\dots,x_n)=(x_1+x_2+\dots+x_n)^m=\sum_{\lambda_1,\lambda_2,\dots,\lambda_n\in N} a_{\lambda_1,\lambda_2,\dots,\lambda_n}x_1^{\lambda_1}x_2^{\lambda_2}\dots x_n^{\lambda_n}
方案数可以这么计算：
\sum_{x_1,x_2,\dots,x_n\in N}a_{x_1,x_2,\dots,x_n}[2\mid x_1+1][2\mid x_2+1]\dots[2\mid x_n]
用单位根反演得到：
\frac{1}{2^n}\sum_{x_1,x_2,\dots,x_n\in N}a_{x_1,x_2,\dots,x_n}(1-(-1)^{x_1})(1-(-1)^{x_2})\dots(1+(-1)^{x_1})
展开连乘，带入函数：
\frac{1}{2^n}\sum_{x_1,x_2,\dots,x_n\in\{-1,1\}}(-1)^{\frac{x_1+x_2+\dots+x_l-1}{2}}f(x_1,x_2,\dots,x_n)
排列组合：
\frac{1}{2^n}\sum_{k_1=0}^n\sum_{k_2=0}^{n-l}(-1)^{k_1}\binom{l}{k_1}\binom{n-l}{k_2}(n-2k_1-2k_2)^m
NTT / 整式递推 | 100 分
在普通公式做法的基础上，设：
F(x)=(-1)^x\binom{l}{x},G(x)=\binom{n-l}{x},H(x)=(n-2x)^m
可以化简成：
\frac{1}{2^n}\sum_{t=0}^nH(t)\sum_{k_1+k_2=t}F(k_1)G(k_2)
利用 NTT 可以 \Theta(\sum n\log n) 计算后半部分的卷积。
UPD:
感谢 NaCly_Fish 提供了一种整式递推的方法，
可以 \Theta(\sum n) 的计算，orz。
tips: 时间复杂度的计算忽略了一些可以当成常数的东西
代码实现
注意一个细节：
我们知道同余意义下 (n-2x)^m=(n-2x)^{m \bmod p-1}，
所以该数列是循环的。
但是当 m=0 和 m=p-1 时的结果可能不一样，
因为 0^0=1,0^{p-1}=0 <这里可以这么定义 0^0 >
所以需要特判。
这里给个我的核心代码吧：
for(ans=t=0;t<=n;++t)(ans+=fpow(P+n-(t<<1),m)*F[t])%=P;
std::cout<<ans*fpow(2,P-1-n)%P<<"\n";
其中 F[t] 是卷积的函数。
致谢
以下排名不分先后：
感谢 NaCly_Fish 对这题的关注与 hack（上方提到的细节），
感谢 szh_AK_all 积极联系验题人，
感谢 2023gdgz01 及时的沟通联系，
以及感谢所有团队成员和大家的支持。