“超级无敌神仙炫酷无敌原神大王”豪华套餐堂堂复活。 首先树剖,考虑维护轻儿子的贡献,之后在重链上直接查。记 $f_u$ 为 $u$ 的子树中到 $u$ 的最大答案,$g_u$ 为 $u$ 的所有轻儿子中 $f_v$ 的最大值,$dis_u$ 为 $u$ 到根的距离。 询问时,在重链中往下走就维护 $g_u+dis_u$,往上走就维护 $g_u-dis_{fa_u}$,重链之间就用 $g_u$ 转移。 修改时,用类似询问的方法维护重链顶的 $f_u$,再更新 $g_{fa_u}$。考虑对每个点开一个 set 维护 $g_u$ 即可。 时间复杂度 $O(n\log^2 n)$,巨大难写。
题目1887 [国家集训队 2011] Crash的旅行计划
10
3 条 评论
2023-11-06 17:05:20
|
|
Pro3918 梦现时刻 题解偶然看到的神秘题,感觉有点意思。 首先考虑式子的组合意义,可以理解为共有 $n$ 个球,可以从前 $b$ 个中选任意个涂白,再在剩下的球中选 $a$ 个涂黑的方案数。 考虑转而枚举前 $b$ 个球中涂黑的数量,得到 $f_{a,b}=\sum_{i=0}^b{2^{b-i}C_b^iC_{n-b}^{a-i}}$ 注意到这个式子很能卷积,考虑将 $b$ 固定,设 $F_b(x)=\sum{f_{a,b}x^a}$,得到 $F_b=(2+x)^b(1+x)^{n-b}$ 此时枚举 $b$ 并动态维护多项式已经可以做了,类似背包和退背包。时间复杂度 $O(m^2)$。
实际上可以直接推出 $f_{a,b}$ 的递推式。考虑 $F_b(x)'=b(2+x)^{b-1}(1+x)^{n-b}+(n-b)(2+x)^b(1+x)^{n-b-1}$ $\quad\quad\;\;\,=bF_{b-1}(x)\frac{1}{1+x}+(n-b)F_b(x)\frac{1}{1+x}$ 于是 $(1+x)F_b(x)'=bF_{b-1}(x)+(n-b)F_b(x)$ 提取系数即得 $(a+1)f_{a+1,b}+af_{a,b}=bf_{a,b-1}+(n-b)f_{a,b}$ 整理一下 $f_{a+1,b}=\frac{1}{a+1}(bf_{a,b-1}+(n-a-b)f_{a,b})$ 预处理逆元直接递推,时间复杂度 $O(m^2)$。 “超级无敌神仙炫酷无敌原神大王”豪华套餐特邀嘉宾。
题目3918 梦现时刻
8
评论
2023-10-10 20:24:35
|
|
跟下面那道题比起来属于是纯纯的小清新题了,这就是原友出题人和原批出题人的差距。不过当时的 FFT 应该没有现在这么普及,就像原神在最初几年也没有引起轩然大波一样。
这种组合数取模肯定考虑卢卡斯定理,况且 $n \lt p^{10}$ 也算是提醒你了。 将 $n$ 和 $k$ 写成 $p$ 进制数 $\overline{n_N...n_0}$ 和 $\overline{k_N...k_0}$,根据卢卡斯定理有 $C_n^k=\prod_i{C_{n_i}^{k_i}}$。显然每个 $k_i$ 的贡献是可以分开算的。
令 $f_{i,j}$ 表示前 $i$ 位组合数累乘后 $\%p=j$ 的方案数,$g_{i,j}$ 表示使得 $C_{n_i}^k \%p = j$ 的 $k$ 的数量,转移是简单的: $$f_{i,j}=\sum_{(x\times y) \%p=j}{f_{i-1,x} g_{i,y}}$$ 这转移式和卷积的相似度可以与原神媲美了,然而这个下标是相乘而不是相加。 但这玩意属于是典中典了,直接把下标对 $p$ 的原根取对数就可以转化成相加了,具体见 “[SDOI2015]序列统计”。
重新定义一下,令当前选择的原根是 $G$。 令 $f_{i,j}$ 表示前 $i$ 位组合数累乘后 $\%p=G^j$ 的方案数,$g_{i,j}$ 表示使得 $C_{n_i}^k \%p = G^j$ 的 $k$ 的数量,将转移写成和卷积: $$F_i=\sum_{j\ge 0}{f_{i,j}x^j}\quad\quad G_i=\sum_{j\ge 0}{g_{i,j}x^j}$$ $$\Rightarrow F_{i}=\sum_{j\ge 0}(\sum_{(x+y)\%(p-1)=j}{f_{i-1,x} g_{i,y}})x^j=F_{i-1}G_i$$
大概就是这样,注意下标相加实际是指数相加,所以根据费马小定理对 $p-1$ 取模。以及这样卷积出来会有下标大于 $p-1$ 的项,及时合并到前面即可。 介于答案模数较小,使用 FFT 计算卷积,时间复杂度大概是 $O(10p\log(p))$。 勉强加入“超级无敌神仙炫酷无敌原神大王”豪华套餐。
题目1797 [国家集训队2012]binomial
10
评论
2023-08-05 18:39:20
|
|
数个月前说要写,鸽到现在,菜。 属于是惊世骇俗的神秘题了。 拿到式子直接开始乱推:
$$ \sum_{i=1}^{n}{\gcd(i,n)^x \mathrm{lcm}(i,n)^y}\\ $$ $$ =\sum_{i=1}^{n}{i^yn^y\gcd(i,n)^{x-y}}\\ $$ $$ =n^y\sum_{d|n}{d^{x-y}\sum_{i=1}^{n}{i^y[\gcd(i,n)=d]}}\\ $$ $$ =n^y\sum_{d|n}{d^{x-y}\sum_{i=1}^{\frac{n}{d}}{(id)^y[\gcd(i,\frac{n}{d})=1]}}\\ $$ $$ =n^y\sum_{d|n}{d^x\sum_{i=1}^{\frac{n}{d}}{i^y\sum_{k|i,k|\frac{n}{d}}{\mu(k)}}}\\ $$ $$ =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)\sum_{i=1}^{\frac{n}{dk}}{(ik)^y}}}\\ $$ $$ =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^y\sum_{i=1}^{\frac{n}{dk}}{i^y}}}\\ $$ $$ =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^yS(\frac{n}{dk},y)}}\\ $$
玩原神的人都知道 $S(\frac{n}{dk},y)$ 是个 $y+1$ 次多项式,这就是原神带给我骄傲的资本。记 $S=\sum_{i=0}^{y+1}{f_ix^i}$ 代入:
$$ =n^y\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^y\sum_{i=0}^{y+1}{f_i(\frac{n}{dk})^i}}}\\$$ $$ =n^y\sum_{i=0}^{y+1}{f_i\sum_{d|n}{d^x\sum_{k|\frac{n}{d}}{\mu(k)k^y{(\frac{n}{dk})^i}}}}\\$$ $$ =n^y\sum_{i=0}^{y+1}{f_i(\mu \cdot Id^y \ast Id^x \ast Id^i)_{(n)}}\\$$
三个函数卷积,纯纯的卷狗。 好在三个积性函数卷出来也是积性函数,于是 pollard_rho 出 $n$ 的所有质因子分开算。
$$(\mu \cdot Id^y \ast Id^x \ast Id^i)_{(p^c)}\\$$ $$ =\sum_{j=0}^{c}{\mu(p^j)p^{yj}\sum_{k=0}^{c-j}{p^{kx}p^{(c-j-k)i}}}\\$$ $$ =\sum_{k=0}^{c}{p^{ci+(x-i)k}}-p^y\sum_{k=0}^{c-1}{p^{(c-1)i+(x-i)k}}\\$$
两坨都是等比数列求和,好好好,玩原神玩的。 最后就是这个 $f_i$。 如果你玩原神,那么你就会伯努利数,那么就知道:
$$\sum_{i=1}^{n}{i^k}=\frac{1}{k+1}\sum_{j=0}^{k}{(-1)^jC_{k+1}^jB_jn^{k+1-j}}$$
其中 $B_j$ 是伯努利数,可以用 EGF 求:
$$B(x)=\sum_{i \ge 0}{B_i\frac{x^i}{i!}}=\frac{x}{e^x-1}$$
然后就结束了。原神,启动! 听说还很卡常,已加入“超级无敌神仙炫酷无敌原神大王”豪华套餐。
题目1770 [国家集训队2012]JZPKIL
9
评论
2023-08-01 21:43:41
|
|
首先设 $f_i$ 为 $i$ 个点的 DAG 数量,枚举其中的 $i-j$ 个点没有入度,然后剩下 $j$ 个点向它们随意连边,但这样会算重,需要在容斥一下,方程是: $$ f_i = \sum_{j=1}^{i}{(-1)^{j-1} C_i^j 2^{j(i-j)} f_{i-j}}$$ 时间复杂度 $O(n^2)$,可过 $n=5000$。
这个式子看起来就很能卷积,不过这个 $2^{j(i-j)}$ 很烦,可以化一下: $$j(i-j)=\frac{i^2}{2}-\frac{j^2}{2}-\frac{(i-j)^2}{2}$$ 这样就能把 $j$ 和 $i-j$ 分开了。于是: $$ f_i = \sum_{j=1}^{i}{(-1)^{j-1} \frac{i!}{j!(i-j)!} 2^{\frac{i^2}{2}-\frac{j^2}{2}-\frac{(i-j)^2}{2}} f_{i-j}}$$ $$ = 2^{\frac{i^2}{2}}i! \sum_{j=1}^{i}{\frac{(-1)^{j-1}}{2^{\frac{j^2}{2}}j!} \frac{f_{i-j}}{2^{\frac{(i-j)^2}{2}}(i-j)!} }$$ 设: $$A(x)=\sum_{i \ge 1}{\frac{(-1)^{i-1}}{2^{\frac{i^2}{2}}i!}x^i}$$ $$F(x)=\sum_{i \ge 0}{\frac{f_i}{2^{\frac{i^2}{2}}i!}x^i}$$ 于是: $$F = A*F +1$$ 即: $$F = \frac{1}{1-A}$$ 使用 FFT 卷积,时间复杂度 $O(n\log(n))$,可过 $n=100000$。
题目2353 [HZOI 2015] 有标号的DAG计数 I
11
评论
2023-04-17 19:47:39
|
|
做法一:首先设 $f_i$ 表示至少 $i$ 对和睦的方案,$g_i$ 表示恰好 $i$ 对和睦的方案。 显然有: $$f_i=\sum_{j=i}^{n}{C^i_jg_j}$$ 根据二项式反演,有: $$g_i=\sum_{j=i}^{n}{(-1)^{j-i}C^i_jf_j}$$ 而我们还有: $$f_i=C^i_nA^i_n2^i(2n-2i)!$$ 于是: $$g_i=\sum_{j=i}^{n}{(-1)^{j-i}C^i_jC^j_nA^j_n2^j(2n-2j)!}$$ $$=\frac{n!^2}{i!}\sum_{j=i}^{n}{\frac{(-1)^{j-i}2^j}{(j-i)!(n-j)!}}$$ 显然可以卷积,于是时间复杂度 $O(Tn\log n)$.
本题还有个加强版,每次询问只需要求一组 $(n,k)$ 的答案,但 $T \le 2e5,n \le 5e6$。
做法二:发现实际要求的是错排的方案数,记 $F_n$ 表示 $n$ 对情侣的错排方案数,于是: $$ans(n,k)=C^k_nA^k_n2^kF_{n-k}=(C^k_n)^2k!2^kF_{n-k}$$ 而显然: $$\sum_{k=0}^{n}{ans(n,k)}=\sum_{k=0}^{n}{(C^k_n)^2k!2^kF_{n-k}}=(2n)!$$ 化成卷积形式: $$\sum_{k=0}^{n}{\frac{2^k}{k!}\frac{F_{n-k}}{(n-k)!^2}}=\frac{(2n)!}{n!^2}$$ 于是我们设: $$A(x)=\sum_{i \ge 0}{\frac{2^i}{i!}x^i}$$ 有: $$A(x)=\sum_{i \ge 0}{\frac{(2x)^i}{i!}}=e^{2x}$$ 再设: $$F(x)=\sum_{i \ge 0}{\frac{F_i}{i!^2}x^i}$$ 再设: $$B(x)=\sum_{i \ge 0}{\frac{(2i)!}{i!^2}x^i}$$ 根据广义二项式定理,有: $$B(x)=(1-4x)^{-\frac{1}{2}}$$ 再代入上边的卷积式得: $$A \cdot F=B$$ 也就是: $$F(x)=\frac{e^{-2x}}{(1-4x)^{\frac{1}{2}}}$$ 求个导: $$F'(x)=\frac{8xe^{-2x}}{(1-4x)^{\frac{3}{2}}}=\frac{8x}{1-4x}F(x)$$ 于是得到: $$F'(x)=4xF'(x)+8xF(x)$$ 观察系数: $$F_{n+1}=4n(n+1)F_n+8n^2(n+1)F_{n-1}$$ 终于得到了递推式,可以 $O(n+T)$ 解决加强版。本题同样也可 $O(n+Tn)$。
题目3353 情侣?给我烧了
10
评论
2023-04-14 22:51:01
|