搜索结果
查询Tags标签： binom，共有 20条记录-
关于下降幂
定义 下降幂就是形如 \(n^{\underline m}\) 的式子，表示 \[n^{\underline m} =\prod_{i=n-m+1}^n i=\frac{n!}{(n-m)!} \]同理还有一个上升幂： \[n^{\overline m}=\prod_{i=n}^{n+m-1} i=\frac{(n+m-1)!}{(n-1)!} \]注意这个地方 \(n,m\) 都可能是负数，也就是 \(n^{\un…
2022/9/16 23:19:39 人评论 次浏览 -
P6800 【模板】Chirp Z-Transform
\(\text{Solution}\) 考虑把\(c^i\)带入多项式得 \[ans_i = \sum_{j = 0}^{n - 1}a_jc^{ij} \]利用组合数把\(c^{ij}\)拆开，\(ij = \binom{i + j}{2} - \binom{i}{2} - \binom{j}{2}\)，证明把组合数拆开即可。 \[ans_i = \sum_{j = 0}^{n - 1}a_jc^{\binom{i + j}{2} - …
2022/7/14 23:21:52 人评论 次浏览 -
组合数学基础
组合数 性质和公式 \(1.\) 对称性 \[\binom{n}{k}=\binom{n}{n-k} \]\(2.\) 加法公式 \[\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} \]其组合意义为钦定最后一个数选或不选的方案数相加。 \[\sum_{i=0}^{n}\binom{n}{i}=2^n \]其组合意义为所有的选数方案恰好对应了每…
2022/6/28 23:31:23 人评论 次浏览 -
重修 二项式反演
我只知道容斥不知道二项式反演。 反演，顾名思义就是有两个函数 \(f,g\)，知道 \(f\) 用 \(g\) 表示后反过来 \(g\) 用 \(f\) 表示。 二项式反演有一个无敌对称的柿子： \[f(n)=\sum_{i=1}^n(-1)^i\binom{n}{i}g(i)\iff g(n)=\sum_{i=1}^n(-1)^i\binom{n}{i}f(i) \]这个柿…
2022/6/21 23:19:45 人评论 次浏览 -
AGC021
AGC021 做了一下 AGC021 这套题，感觉很厉害，纪念一下，题意就不放了。 A 自己想出来了，就枚举每一位，然后后面的位可以都是 \(9....\) 之类的，前面可以卡的死一点。 B 你就考虑，既然他这个圆这么离谱，那一看起来就和这个东西没啥关系啊。 显然只有凸包上的点才有可…
2022/4/7 6:23:30 人评论 次浏览 -
[CQOI 2018] 交错序列
\(\text{I love Wordle!!!}\) I guessed this 5-letter word in 5/6 tries. ⬛⬛⬛⬛⬛
2022/3/29 6:28:21 人评论 次浏览 -
关于 NOI2019 斗主地 的证明
左边 \(L\) 右边 \(R\) 张牌： 左边从上往下第 \(x\) 张牌对第 \(i\) 个位置的贡献 其实都可以打表观察 233 \[\sum_{x}\binom{i-1}{x-1}\binom{n-i}{L-x}w_x \]\(w_x = x :\) \[\sum_{x}\binom{i-1}{x-1}\binom{n-i}{L-x} x \]\[\sum_{x}(\binom{i}{x}x - \binom{i-1}{x}…
2021/12/28 23:39:00 人评论 次浏览 -
关于 NOI2019 斗主地 的证明
左边 \(L\) 右边 \(R\) 张牌： 左边从上往下第 \(x\) 张牌对第 \(i\) 个位置的贡献 其实都可以打表观察 233 \[\sum_{x}\binom{i-1}{x-1}\binom{n-i}{L-x}w_x \]\(w_x = x :\) \[\sum_{x}\binom{i-1}{x-1}\binom{n-i}{L-x} x \]\[\sum_{x}(\binom{i}{x}x - \binom{i-1}{x}…
2021/12/28 23:39:00 人评论 次浏览 -
Tricks
\(a\) 的平均数为 \(m\) 等价于 \(\sum a_i-m=0\)。可以配合其他算法处理一些平均数的最优解问题。例：问平均数处于 \([p,q)\) 的区间数。 相当于需要处理平均数小于 \(p\) 的数量然后减一下即可。\(b_i=a_i-p\)，然后做前缀和 \(s_i=\sum_{j=1}^{i} b_i\)，相当于求有多…
2021/11/11 23:14:39 人评论 次浏览 -
Tricks
\(a\) 的平均数为 \(m\) 等价于 \(\sum a_i-m=0\)。可以配合其他算法处理一些平均数的最优解问题。例：问平均数处于 \([p,q)\) 的区间数。 相当于需要处理平均数小于 \(p\) 的数量然后减一下即可。\(b_i=a_i-p\)，然后做前缀和 \(s_i=\sum_{j=1}^{i} b_i\)，相当于求有多…
2021/11/11 23:14:39 人评论 次浏览 -
省内联考 10.17 随机过程（process）
简要题意： 在长度为 \(l\) 的数轴上均匀随机 \(n\) 个区间，求被至少 \(k\) 个区间覆盖的长度期望。 这个描述已经足够形式化了，下面直接开始推导。 设 P_x 为每个点合法的概率，二项式反演有：$$P_x=\sum_{i=k}^n\binom{n}{i}(2x(1-x))^i(1-2x(1-x))^{n-i}$$ 枚举 \(k…
2021/10/18 6:10:45 人评论 次浏览 -
省内联考 10.17 随机过程（process）
简要题意： 在长度为 \(l\) 的数轴上均匀随机 \(n\) 个区间，求被至少 \(k\) 个区间覆盖的长度期望。 这个描述已经足够形式化了，下面直接开始推导。 设 P_x 为每个点合法的概率，二项式反演有：$$P_x=\sum_{i=k}^n\binom{n}{i}(2x(1-x))^i(1-2x(1-x))^{n-i}$$ 枚举 \(k…
2021/10/18 6:10:45 人评论 次浏览 -
题解 树上竞技
传送门 有几档暴力不会写，巨丢人 \(m=2\) 的话两个人之间的距离会覆盖整棵树上所有可能的路径，所以就是求所有树上路径长度的总和 成链且 \(m\) 为奇数的话，集中点肯定是中位数那个点 考场上想偏了，只会用这个性质求一些给定的人应该集中在哪个点 但实际上可以枚举中位…
2021/10/3 6:40:11 人评论 次浏览 -
题解 树上竞技
传送门 有几档暴力不会写，巨丢人 \(m=2\) 的话两个人之间的距离会覆盖整棵树上所有可能的路径，所以就是求所有树上路径长度的总和 成链且 \(m\) 为奇数的话，集中点肯定是中位数那个点 考场上想偏了，只会用这个性质求一些给定的人应该集中在哪个点 但实际上可以枚举中位…
2021/10/3 6:40:11 人评论 次浏览 -
Card
\(Ans=\frac{\sum\limits_{i=0}^ni^k(m-1)^{n-i}\binom ni}{m^k}\) \(F(x)=\sum\limits_{t\ge0}\frac{x^t}{t!}\sum\limits_{i=0}^ni^t\binom ni(m-1)^{n-i}\) \(=\sum\limits_{i=0}^n\binom ni(m-1)^{n-i}e^{ix}\) \(=(e^x+m-1)^n\) \(现在求[x^k]F(x),我们试用EI介绍的方…
2021/9/17 23:09:56 人评论 次浏览
