随记

随记?标题那个词时百度翻译的，，，，

感觉比较有拓展的，或者说自己应该多看看的打上了*标。

1. \(\mu(ix)\) 怎么筛？*

可以杜教筛，很震撼。

\(f_x(i)=\mu(ix)\) 这个函数首先是积性的，不包含的质因子直积形成的，而他的的贝尔级数为：\((1-x)\) 和 \(1\)。

我们构造 \(g_x(i)=[\gcd(x,i)=1]\)。他的贝尔级数为：\(1+x+x^2+\cdots +x^n+\cdots\)，和 \(1\)。

发现很神奇呀，乘起来之后就是 \(\epsilon\)。

---

特别的 \(\phi(ix)\) 的杜教筛法也是类似的。

---

2. 感性理解对偶。

\[ \begin{aligned} \max c^{T}x,Ax\le b,x\ge 0\\ \min y^Tb,A^Ty\ge c,y\ge 0\\ \end{aligned} \]

限制与变量对调，限制系数与目标函数系数对调。

\[ \begin{aligned} y^TA\ge c^T\Rightarrow y^TAx\ge c^Tx\Rightarrow y^Tb\ge y^TAx\ge c^Tx \end{aligned} \]

这样我们得到了 \(\min y^Tb\ge \max c^{T}x\)。

接下来证明等号很复杂，所以感性理解 \(\mathrm{maximize}\) 也始终小于 \(\mathrm{minimize}\) 最终取等？

---

3. 复杂度真的不对吗？*

我们都知道，值域是 \(sz_u\) 的树背包 dp 的复杂度是 \(O(n^2)\) 的。

那么如果值域变成了 \(\min(sz_u,k)\) 这类的，他的复杂度啥呢？

答案是通过精细实现，是 \(O(nk)\) 的。

大概是你考虑将合并分成三部分。

我们称 \((u,v),sz_u>k,sz_v\le k\) 为切换边，那么切换边下面的转移复杂度可以用 \(\sum_{v}sz_v^2\) 来分析，由于是不交的，所以有 \(\sum_{v}sz_v^2\le \sum_{v}sz_vk=O(nk)\)。

切换边上面的点总共只有 \(n/k\) 个，那么直接转移的复杂度是 \((n/k)k^2=O(nk)\) 的。

切换边的转移代价可以用 \(\sum_{v} sz_vk\) 来分析的，又是 \(v\) 不交，所以这部分也是 \(O(nk)\) 的。

这个其实给了我们一些启示，如果能将树分成若干个“不交并”的这样的集合，那么很多事情会变成 \(O(n)\) 。

例如『MdOI R1』Path 这题的 \(n\log n\) 做法，几次利用到了不交并关键性质。

『MdOI R1』Path

考虑全局最大异或和的链，实际上有很多链的答案是他们。性质太棒了。

---

4.原汁原味的淀粉。*

如题，如果需要维护点集 \(A\)，每次插入一个数，查询 \(f(u)\sum_{x\in A}dis(u,x)\)。

这个问题我最开始以为拆贡献，变成链加，链求和是最为方便的做法。可惜不用全局平衡二叉树的话，树剖是 \(\log^2\) 的。

那么如果使用点分树的话呢？，考虑点分树这样一个结构，点分树上两点一定在原树路径上。

我们之前干的事情是把路径集合，划分成若干个落在lca处的不交并。这样我们可以把路径集合落在点分树上lca处的不交并。

好处是明显的，树高 \(\log\) 一些我们平时不敢干的事情可以暴力做了。感觉做法很有拓展性。

当然我们知道 toptree 的结构更加有拓展性。记得u群里总说直接在toptree上分治。全局平衡二叉树是静态toptree。

5.英国的将军算法。

不知道这玩意咋想出来的。。

如何求 \(a\cdot m^{-1}\bmod M\)。

waiting for upd

6. 区间点积真的啥操作都能维护呀！

区间点积真的啥操作都能维护呀！

记录 \(sa,sb,sab\) 足以了。。。。。。。。。。

不用 \(5\times 5\) 矩阵。。。。。

7. MTT

\(a_i,b_i\in \mathbb{Z}\)。

\(f(x)=A(x)+iB(x),g(x)=A(x)-iB(x)\)

\[ \begin{aligned} [x^k]f(x)=\sum_{j=0}(a_j+ib_j)(w_{n}^k)^j\\ [x^{n-k}]g(x)=\sum_{j=0}(a_j-ib_j)(w_{n}^{n-k})^j\\ \end{aligned} \]

\(\overline{a_j+ib_j}=a_j-ib_j\)

\(\overline{w_{n}^k}=w_{n}^{n-k}\)

\(\overline{[x^k]f(x)}={[x^{n-k}]g(x)}\)

8. agc的c的證明。

如果一个完全图，我给每条边都定向，产生的无向图有环。

那么一定存在一个简单三元环。对于任意一个长度>=4的环，考虑其中任意两点，不管怎么连边，必然会分成一个更小的环。

9. 只有向后push_back的st表。

这个我们更改定义变成 \([x-2^i+1,x]\) 的极值。

然后发现就可以转移啦，这个也就是相当于插入叶子，然后倍增求lca那种东西。

10. 不清楚的异或卷积（感谢cres的无私贡献）*

inline void fwt(int *a,int lim){
    for(int mid=1;mid<lim;mid<<=1){
        for(int j=0;j<lim;j+=(mid<<1)){
            for(int k=0;k<mid;k++){
                int x=a[j+k],y=a[j+k+mid];
                a[j+k]=x+y,a[j+k+mid]=x-y;
            }
        }
    }
}
int a[1010],b[1010],d[1010];
double c[1010];
int main(){
    int x=11,y=7,z=5,lim=32;
    a[0]=3,a[x]=1;fwt(a,lim);
    b[0]=5,b[y]=1;fwt(b,lim);
    d[0]=7,d[z]=1;fwt(d,lim);
    for(int i=0;i<lim;i++) cout<<a[i]*b[i]*d[i]<<" ";cout<<endl;
    for(int i=0;i<lim;i++) c[i]=1;
    c[x]*=sqrt(1.0*(3+1)/(3-1));
    c[y]*=sqrt(1.0*(5+1)/(5-1));
    c[z]*=sqrt(1.0*(7+1)/(7-1));
    for(int mid=1;mid<lim;mid<<=1){
        for(int j=0;j<lim;j+=(mid<<1)){
            for(int k=0;k<mid;k++){
                double x=c[j+k],y=c[j+k+mid];
                c[j+k]=x*y;c[j+k+mid]=x/y;
            }
        }
    }
    for(int i=0;i<lim;i++) {
        cout<<(c[i]*sqrt((5+1)*(5-1))*sqrt((3+1)*(3-1))*sqrt((7+1)*(7-1)))<<" ";
    }
    cout<<endl;
}

似乎正确性得到了说明，如果我们只在 \(\bmod\) 质数意义下计算大抵可以这么做。

\(\bmod p\) 时，开一次根号只会扩一次域。我们只会引入一次 \(i\)。

考虑 \(p\) 是质数，所以存在原根，这样数域中每一个数（除了0）都可以表示成 \(g^c\) 如果 \(c\bmod 2=0\) 那么是二次剩余，否则只需要引入 \(i=g^{1/2}\) 这样所有的数都可以在数域中被表示出来。

然后现在我们希望求的是： \[ \prod_{i=1}^{n} (a_i+b_ix^{T_i}) \] 这里的乘法是异或卷积，即 \(x^a\times x^b=x^{a\text{ xor }b}\)。

我的做法大概是一个 \(2^nn\mathrm{polylog}(p)\) 的。

waiting for addition

接下来我们可以将位置 \(T_i\) 处乘上 \(\sqrt{\frac{A_i}{B_i}}\) ，最后在进行一次新定义的 fwt 即可得到真实的 \(fwt(\prod_{i=1}^{n} (a_i+b_ix^{T_i}))\)。

然后做一次普通的ifwt。