LOJ6358 前夕
LOJ 分析 考虑求出交集大小至少为 $k$ 的方案数 $f(k)$，显然有 从小到大枚举 $k$，动态维护 $(\omega ^ j - 1) ^ k$ 即可 $\mathcal{O}(n)$ 计算。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog...
LOJ 分析 考虑求出交集大小至少为 $k$ 的方案数 $f(k)$，显然有 从小到大枚举 $k$，动态维护 $(\omega ^ j - 1) ^ k$ 即可 $\mathcal{O}(n)$ 计算。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog...
Luogu LOJ 分析 显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。 考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数，不难得到 可以发现是一个差卷积的形式，于是直接 NTT 即可。 代码 // ===============...
Codeforces Luogu 算法一 分析 设树边的权值为 $x$，非树边的权值为 $1$，然后矩阵树定理。设得到的多项式为 $F(x)$，那么显然 $k=i$ 时的答案即为 $[x^i]F(x)$。 然而直接 MTT + 高斯消元显然是过不去的。但是 $F(x)$ 是一个 $n-1$ 次多项式，所以我们可以把 $x=[1,n]$ 代进去求出 $F(1..n)$，然后解方程组解出系数即可...
LOJ 分析 容易想到容斥，计算至少包含 $i$ 个魔术对的序列数 $g_i$。根据二项式反演不难得到 分治求出所有 $f_i$ 的卷积即可得到 $dp_m$。 然而 $dp_{m,i}$ 并不等于 $g_i$，因为我们还可以任意排列不构成魔术对的 $n-i$ 张牌，所以还需要乘上一个 $(n-i)!$。 最后二项式反演一下即可得到答案。记得把答案除掉 $\prod a_i!$。 代码 /...
Luogu LOJ 分析 为了方便，设 $n<m<l$，$V=nml$。 考虑容斥，求出至少有 $i$ 个极大数的方案数 $c_i$。 那么 $c_i$ 等于选出 $i$ 个极大数的方案数、$i$ 个极大数所在的平面的并填数的方案数、其它位置填数的方案数之积。 首先考虑求选出 $i$ 个数的方案数 $f_i$，不难得到 总时间复杂度 $\mathcal{O}(n)$。 代码 /...
Luogu LOJ 分析 首先题目要求的其实就是方案数。 设 $cnt_i$ 表示颜色为 $i$ 的珍珠的数量，那么如果一组方案合法的话会有 显然也是一个卷积的形式。 于是只需要构造多项式求出 $f_i$ ，再构造多项式求出 $g_i$ ，再求答案即可。 另外注意特判 $2m<n-D$ 和 $2m>n$ 的情况，答案分别为 $D^n$ 和 $0$ 。 总结：这是一道好题，可是...