ZigZagK的博客
[多项式ln+多项式exp+分治NTT]LOJ2320【「清华集训 2017」生成树计数】题解
题目概述LOJ2320解题报告学到了好多多项式套路。如果 $i$ 连通块度数是 $d_i$ ,则每条边都有 $a_i$ 个选择,把 $a_i$ 放进答案式子里,答案式子就是:$$ \sum_T(...
[生成函数+分治NTT+多项式ln]洛谷4705【玩游戏】题解
题目概述Luogu4705解题报告二项式展开后:$$ {t!\over nm}\sum_{k=0}^{t}{1\over k!}(\sum_{i=1}^{n}a_i^k){1\over(t-k)...
[Bluestein套路+多项式ln]2022“杭电杯”中国大学生算法设计超级联赛(7)1010【Connectivity of Erdős-Rényi Graph】题解
题目概述HDU7218解题报告这道题看起来和城市规划很像,但是由于要考虑概率,所以卷积式子和求方案数的式子不一致。定义 $f_i$ 表示 $i$ 个点成为一个连通块的概率,考虑两个连通块的概率:...
[容斥+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛(8)1013【Shattrath City】题解
题目概述HDU7232解题报告比赛的时候想的是正着做,写完DP式子发现是个看起来很可做的东西,结果实际上不能做,寄掉了。实际上应该倒着做,$f_{i}$ 表示 $[1,n]$ 排列第一次出现在 ...
[多项式exp]2022“杭电杯”中国大学生算法设计超级联赛(6)1003【Find the Number of Paths】题解
题目概述HDU7199解题报告多项式套路题,需要把题目中两种路径对应到比较容易处理的多项式形式。首先是 $i\to i+1$ ,有 $n+k-i$ 条路径,这个形式不太友好,因此我们考虑把整个序...
[容斥+DP+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛(1)1010【Walk】题解
题目概述HDU7147解题报告从来没做过这种容斥,长见识了😭。定义 $f_i$ 表示走了 $i$ 行都合法的权值和,以及 $g_i$ 表示走了 $i$ 行全非法的权值和(特殊的,如果 $i=1$...
[生成函数+多项式除法求系数]2021牛客暑期多校训练营8 H【Scholomance Academy】题解
题目概述Scholomance Academy解题报告伪装成数论题的多项式全家桶题。首先我们可以把 $\varphi(n)$ 拆成 $\prod\varphi(p_i^{a_i})$ ,因此不难...
[线性代数+多项式取模]洛谷4723【常系数齐次线性递推】题解
题目概述给出递推 $f$ 的 $[0,K-1]$ 项,给出系数 $\{a_K\}$ ,$f_n=\sum_{i=1}^{K}a_if_{n-i}(n\ge K)$ ,求第 $n$ 项。$n\le...
[多项式+牛顿二项式定理]HHHOJ108【爱丽丝/Alice】题解
解题报告题目中显然给出了一个卷积形式,所以我们移下项,凑凑常数,得到:$$ {A(x)-A_0\over x}-A_1=A(x)A(x)-A_0^2\\ A(x)-A_0-A_1x=xA^2(x...
[多项式多点求值]洛谷5050【多项式多点求值】题解
题目概述给出一个多项式 $F(x)$ ,有 $m$ 个询问,每次求 $F(a_i)$ 。解题报告将 $F(x)$ 在 $x=a$ 处进行泰勒展开:$$ F(x)=F(a)+F'(a)(x-a)+...