悠然w
悠然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)
洛谷(10)
状压DP(3)
生成函数(2)
矩阵乘法&矩阵快速幂(2)
矩阵乘法&矩阵快速幂(2)
矩阵树定理(2)
线段树(4)
组合数学(1)
结论题(2)
考试总结(20)
莫队(1)
贪心(3)
随机(2)
题解(1)
高斯消元(2)
高精度(6)
归档
标签
去牛客网
登录
/
注册
悠然w的博客
全部文章
（共232篇）
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
534
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
760
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
336
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
472
luogu P5488 差分与前缀和 FFT
又是一道FFT 好题。 首先来看一看求前缀和。 求一次前缀和就先当于卷上一个系数全为1的多项式，即\(\displaystyle \sum_{i=0}^{\infin}x^i\)(想一想，为什么)，这个东西就等于 \(\displaystyle \frac{1}{1-x}\),简单证明一下。 ...
2019-12-11
0
0
luogu P4173 残缺的字符串 FFT
温馨提示:倘若下角标看不清的话您可以尝试放大。 倘若没有通配符的话可以用KMP搞一搞。 听巨佬说通配符可以用FFT搞一搞。 我们先考虑一下没有通配符的怎么搞。我们设a=1,b=2,...,然后我们构造一个这样的函数\(\displaystyle P_x=\sum_{i=0}^{m-1}(A_i...
2019-12-11
0
357
luogu P4173 残缺的字符串 FFT
温馨提示:倘若下角标看不清的话您可以尝试放大。 倘若没有通配符的话可以用KMP搞一搞。 听巨佬说通配符可以用FFT搞一搞。 我们先考虑一下没有通配符的怎么搞。我们设a=1,b=2,...,然后我们构造一个这样的函数\(\displaystyle P_x=\sum_{i=0}^{m-1}(A_i...
2019-12-11
0
0
首页
上一页
10
11
12
13
14
15
16
17
18
19
下一页
末页
牛客博客，记录你的成长
京公网安备 11010502036488号