学习 Hiengon 大神，开头应该有一句原神语录或者日文歌词，但是我不玩原神，也不是罕见，所以略过。

个人感觉，其实这题的重点不在后面的多项式优化，而在这个容斥系数的推导。这其实展示了一类不太平凡的容斥系数的通用推法。

这个题解本身就是复读论文，后面加点自己的理解。

首先最终的式子是 $f_i = \sum\limits_{0<j<i} f_{i-j}\mathrm C_{i}^{j} 2^{j(i-j)} (-1)^{j-1}$，重点在于那个 $(-1)^{j-1}$ 从哪来。

首先我们有最基本的容斥：

$$g(S) = \sum_{T\subseteq S} f(T)\\f(S) = \sum_{T\subseteq S} (-1)^{|S|-|T|}g(T)$$

可以看作 $\sum\limits_{i=0}^n (-1)^i \mathrm C_{n}^{i}=[n=0]$ 的外在表现，具体的组合双射得参考上面这个的（不知道有没有就是了），反正我不会。这个式子集合关系反过来也是对的，下面要用。

然后我们思考这个题咋做。设 $f(i,S)$ 表示 $i$ 个点，目前零度点集合 恰好 为 $S$ 的方案数，$g(i,S)$ 表示 $i$ 个点，钦定 $S$ 内部均为零度点的方案数。显然有：

$$g(n,S)=\sum_{S\subseteq T} f(n,T)\\f(n,S)=\sum_{S\subseteq T} (-1)^{|T|-|S|} g(n,T)$$

现在我们要算 $g(n,\emptyset)$，直接开始大力推式子：

$$\begin{aligned}g(n,\emptyset) & = \sum_{m=1}^n \sum_{|T|=m} \sum_{T\subseteq S}(-1)^{|T|-|S|} g(n-|S|,\emptyset) 2^{|S|(n-|S|)}\\& = \sum_{S\neq \emptyset} g(n-|S|, \emptyset) 2^{|S|(n-|S|)} \sum_{m=1}^{|S|} (-1)^{|S|-m} \mathrm C_{|S|}^{m}\\& = \sum_{j=1}^{n} g(n-j,\emptyset) \mathrm C_{n}^{j} 2^{j(n-j)} (-1)^{j-1}\end{aligned}$$

每行都解释一下：第一行就是大力展开递推式，第二行交换求和顺序，第三行枚举 $|S|$ 大小直接算，后面那个 $(-1)^{j-1}$ 其实是凑了个 $m=0$ 化二项式定理，然后再减回去。

于是我们就得到了这样一个容斥系数。事实上引起我注意的是最上面的那个最基本的容斥式子，经过之前和 DarkMoon 大神的讨论，发现其实莫反，二项式反演都可以从这个直接理解。

好了，你已经学会有标号 DAG 计数的方法了，快去试试切掉 联合省选2024 d2t2 吧！

一个妙妙思路

将棋子按位置从小到大排序后一对一对看，如1 2 3 4，[1，2]为一对，[3，4]为一对

每对中左边的那个棋子如果往左移了几步，右边的棋子也移动相同的步数，对结果没有影响；但如果右边的棋子往左移，就会对结果有影响，右边的棋子最多移动到左边棋子的右边1格的位置

所以其实只需要维护每对石子之间的距离，类似Nim游戏，当每一对石子相差1时无法移动

如果给定的n为奇数，则多加入一个位置为0的点，与最小的那个为一对

这不是一篇题解，只是偶然发现大多数提交的复杂度都是错的。

其实只是少了一个剪枝：对所有搜索得到的二元组 $(state,sum)$ 去重。

以下记 $N=2n$。

如果不去重，考虑一组数据满足 $a_i=1$。此时前一半中 $sum=i$ 的状态有 $[x^i](1+x+x^{-1})^n=[x^{i+n}](1+x+x^2)^n$ 个，记作 $f_i$。

由于我们是对于每一个后一半的状态，遍历所有前一半与之相等的状态，那么总遍历量为 $\sum_i{f_i^2}$。查一下 OEIS 发现，这个东西是 $O(\frac{3^{2n+0.5}}{2\sqrt{2\pi n}})$ 也就是 $O(\frac{3^{N+0.5}}{2\sqrt{\pi N}})$ 的，其实不比 $O(3^N)$ 的暴力优多少，证明在link。

然而如果去重了，一个粗略的上界是，对于后一半的 $3^n$ 个状态，前一半中最多有 $2^n$ 个状态与之对应，那么就是 $O(6^{\frac{N}{2}})$ 的。此时也能看出，某谷上一堆说复杂度是 $O(3^{\frac{N}{2}})$ 的题解全是瞎扯。

值得注意的是，官方其实还给出了一种 $(1+\sqrt{1.5})^N$ 的做法，奈何我英语不好看不懂。链接是link。

发现最难受的是每行必须选最大值，不好统一刻画。

但是我们可以直接转化这个问题：泛化为从每行选一个数，求最大可能值。不难发现这样答案不会变化。

于是可以状压 dp，$f(i,S)$ 表示处理完前 $i$ 列，目前 $S$ 中为 $1$ 的行已经选上数的最大可能值。

转移直接枚举循环位移，然后枚举子集转移即可。$\mathcal O(Tmn3^n)$。

再做一些最优性的分析，加以预处理，可以做到 $\mathcal O(T(m\log m + n^32^n + n3^n))$。

//阅读须知：请读完第六行后跳到主函数阅读，有利于理解程序。

//思路：建立一个最大为n/2+1的小根堆，将数据输入小根堆，若堆满就删除堆顶元素，直到数据全部输入。

//若n为偶数，则中位数为堆顶元素，否则中位数为堆顶元素与左孩子和右孩子间更小的那个元素的算数平均值，即（堆顶元素+左孩子与右孩子间更小的那个）/2

#include<iostream>

#include<cstdio>

using namespace std;

int a[260000]; //定义小根堆a

int n,s=0,b,t;//n:需处理数据数量，s:堆内元素数量，b:输入媒介（数据中转），t:未处理数据数量

void swim(int s)//上浮操作，变量s为需要进行上浮的数据，本函数用于插入

{

while(s>1&&a[s]<a[s/2])

{

swap(a[s],a[s/2]);

s/=2;

}

}

void push(int b)//插入数据

{

a[++s]=b;

swim(s); //此处s为要上浮的元素在堆中的下标，详见上浮函数swim

}

void jd()//建立小根堆a，此时a中包含了输入数据中前n/2+1个数据

{

   for(int i=1;i<=n/2+1;++i)

   {

       cin>>b;

       push(b); //将b插入至堆中，详见插入函数push

   }

}

void sink(int k)//下沉操作，k恒为1

{

while(2*k<=n/2+1)

   {

   int j=2*k;

   if(j+1<=n/2+1&&a[j]>a[j+1])

   {

       j=j+1;

   }

   if(a[k]<=a[j])

   {

       break;

   }

   swap(a[k],a[j]);

   k=j;

   }

}

void pop()//删除数据

{

   a[1]=a[s--]; //将堆顶替换为堆底元素

   sink(1);

}

int main()

{

   freopen("median.in","r",stdin);

   freopen("median.out","w",stdout);

   cin>>n;

   jd(); //建堆，详见建堆函数jd

   t=n-(n/2+1); //计算未处理数据数量，以免在循环里计算导致超时

   while(t) //当数据没有处理完时

   {

       t--; //剩余数据-1

       cin>>b;

       push(b); //将输入数据b插入堆中，详见插入函数push

       pop(); //将堆顶（下标最小的不可能为中位数的元素）删除，详见删除函数pop

   }

   if(n%2) //当n为奇数

   {

       printf("%0.1f\n",1.0*a[1]);

   }

   else

   {

       printf("%0.1f\n",1.0*(a[1]+min(a[2],a[3]))/2.0);

   }

   return 0;

} //Adam与GS53热心创作

杜教筛

求 $\sum_{i=1}^{n} \phi(i^2)$

基本上是裸的杜教筛

一个关于 $\phi$ 的性质：$$\phi(ij) = \frac{\phi(i)\phi(j)gcd(i,j)}{\phi(gcd(i,j))}$$

证明：该式本质上是容斥，$\phi$ 的原式子是，当 $n = {p_1}^{c_1}\times {p_2}^{c_2} \times ··· \times {p_m}^{c_k}$

$\phi(n) = n \times \prod_{i=1}^{m} (1 - \frac{1}{p_i})$

这里式子就表示为先把 $i$ 和 $j$ 的质因数乘上在除去 $i,j$ 的共同质因数，即 $\phi(gcd(i,j))$，最后再消掉 $gcd(i,j)$ 即可得到该式。

然后开始推式子：

$$ \sum_{i=1}^{n} \phi(i^2) = \sum_{i=1}^{n} i \times \phi(i) $$

不难发现该式等于 $\phi \cdot id$

$$ (\phi \cdot id) \ast id = \sum_{d\mid n} d * \phi(d) * \frac{n}{d} = n \times \sum_{d\mid n} \phi(d) = id^2$$

我们设 $f(n) = n \times \phi(n),S(n) = \sum_{i=1}^{n} f(i)$ ,这里的 $id$ 与 $id^2$ 的前缀和都比较好求。

运用杜教筛公式可得：

$$ S(n) = \sum_{i=1}^{n}i^2 - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)$$

$$ = \frac{n(n+1)(2n+1)}{6} - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)$$

线性筛出前 $n^{\frac{2}{3}}$ 项，整除分块即可