悠然w

洛谷

BZOJ(6) cdq分治(2) CodeForces(2) DP(6) dsu on tree(2) FFTNTT(4) FWT(1) KDtree(4) loj(1) luogu(6) min-max容斥(1) ODT/珂朵莉树(6) OI无关(1) 二分(2) 二分图匹配(3) 克鲁斯卡尔重构树(1) 分块(1) 分治(3) 动态点分治(1) 区间DP(1) 单调栈(8) 双指针(1) 后缀自动机(1) 奇技淫巧(3) 学习笔记(4) 容斥定理(1) 差分(3) 广搜bfs(3) 扫描线(1) 数位DP(3) 数论(1) 整体二分(1) 文化课(1) 最小生成树(1) 最短路(3) 未归档(57) 杂记(11) 树状数组(4) 树链剖分(1) 概率&期望(3) 模拟(4) 状压DP(3) 生成函数(2) 矩阵乘法&矩阵快速幂(2) 矩阵乘法&矩阵快速幂(2) 矩阵树定理(2) 线段树(4) 组合数学(1) 结论题(2) 考试总结(20) 莫队(1) 贪心(3) 随机(2) 题解(1) 高斯消元(2) 高精度(6)

/ 注册

全部文章 / 洛谷（共10篇）

P7426 [THUPC2017] 体育成绩统计模拟

题目链接写这道题最重要的是条理清晰。除了阳光长跑外，其他的都能在读入的时候处理掉。处理阳光长跑最头疼的就是处理时间。把时间单位都变成秒就好啦。我们算出从2017年1月1日0点到这时刻有多少秒就行啦。代码注释很详细，具体看代码吧。 #include<algorithm&...

2021-07-16

0 0

P4552 [Poetize6] IncDec Sequence 差分

题目不难，但是思路巧妙。我们求出差分数组后，就变成了这三种操作 1.一个数加一 2.一个数减一 3.一个数加一的同时一个数减一我们要让 \(2\) ~ \(n\) 变成 \(0\) ，设所有整数的和为 \(s1\) ，负数的和的绝对值为 \(s2\) ，则最少操作数为 \(max(s1, ...

2020-03-30

0 0

P4592 [TJOI2018]异或可持久化0/1Trie树

对于一段区间查询最大异或值，我们可以用可持久化0/1Trie树来维护。对于一个点的子树，它们的 \(dfs\) 序是一段连续的区间。对于一条路经，我们拆成两个端点分别到达 \(LCA\) 的两条路径，它们的 \(dep\) 是连续的。我们分别建出来 1.以 \(dfs\) 序为外层的...

2020-03-30

0 0

[武汉加油] 洛谷 P3107 [USACO14OPEN]Odometer S

记忆化搜索既然需要出现的次数 \(\geq\) 长度的一半，我们不妨就枚举这个数，按照记搜的套路，我们记录一下这个数的出现次数以及是否没了前导零即可。记录次数的时候如果往后添的数是枚举的数，则 \(++cnt\) ,否则 \(--cnt\) ,易证符合条件当且仅当 \(pos=0\) 时 \...

2020-03-15

0 0

luogu P5162 WD与积木 FFT

\(NTT\) 神仙题，强烈建议先自己推一推式子再看题解,顺便orz memset0。题面没看太懂，大概意思就是求有n个不同的小球，放进 \(1\)、\(2\)、$……n $ 个不同的盒子，不可空的情况下，期望用了几个盒子。按照套路，我们应该分别求出总的方案数\(g_i\)和总共用的盒子数 ...

2019-12-13

0 0

luogu P4091 [HEOI2016/TJOI2016]求和 FFT

又是一道神仙题orz 我们先化一化式子。 \(\displaystyle Ans[n]=\sum_{i=0}^n\sum_{j=0}^iS(i,j)\times 2^j\times (j!)\) 看着\(\displaystyle \sum_{j=0}^i\)很不爽，因为当\(j>i\)...

2019-12-13

0 0

luogu P5641 【CSGRound2】开拓者的卓识 FFT

FFT好题。首先我们考虑如何用组合数学来求解。先放一下结论: \(\displaystyle Ans[i]=\sum_{j=1}^ia_jC_{j+k-2}^{j-1}C_{i-j+k-1}^{i-j}\) 给一个简略的证明: 还是组合数学的老套路，我们考虑每一个位置对答案的贡献，贡献就是...

2019-12-12

0 0

luogu P4841 [集训队作业2013]城市规划 FFT

FFT神仙题，强烈建议先自己推一推式子再看题解。首先正着想比较难想，正难则反，所以我们先考虑一下全集。设\(\displaystyle g[n]=2^{C_n^2}\)(C为组合数),表示n个有标号的点随便连边的方案数，设\(f[n]\)是n个有标号的点的无向连通图的方案数。考虑\(g\)和...

2019-12-12

0 0

luogu P3321 [SDOI2015]序列统计 FFT

首先数相同，位置不同的算作不同的方案,每多出一个位置就能多转移一次，所以我们可以写出这样的转移。 \(\displaystyle C[k]=\sum_{i\times j \%m==k}A[i]\times B[j]\) 我们平时写的FFT/NTT都是加号，这里是乘号，想要把乘号变成加号就要取\...

2019-12-12

0 0

luogu P5488 差分与前缀和 FFT

又是一道FFT 好题。首先来看一看求前缀和。求一次前缀和就先当于卷上一个系数全为1的多项式，即\(\displaystyle \sum_{i=0}^{\infin}x^i\)(想一想，为什么)，这个东西就等于 \(\displaystyle \frac{1}{1-x}\),简单证明一下。 ...

2019-12-11

0 0