Skip to content

Commit c01d51a

Browse files
VexobenVexoben
committed
提交内容说明
1 parent c120913 commit c01d51a

10 files changed

+126
-120
lines changed

‎_posts/2018-05-07-学习笔记-二项式系数.md

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,7 @@ $$ 1\dbinom{n}{1}+2\dbinom{n}{2}+...+n\dbinom{n}{n}=n2^{n-1}$$
6464
$$
6565

6666
$$ $$
67-
67+
6868
5、对任意整数$$n>=1$$，有恒等式
6969

7070
$$ n(n+1)2^{n-2}=\sum_{k=1}^{n}k^2\dbinom{n}{k} $$
@@ -158,22 +158,22 @@ $$ (1+z)^{\alpha}=\sum_{k=0}^{\infty}\dbinom{\alpha}{k}z^k $$
158158

159159
设$$n$$是正整数，令$$\alpha=-n$$，则有
160160

161-
$$ \dbinom{\alpha}{k}=\dbinom{-n}{k}=\frac{-n(-n-1)...(-n-k+1)}{k}\\
162-
=(-1)^k\frac{n(n+1)...(n+k-1)}{k}=(-1)^k\dbinom{n+k-1}{k}$$
161+
$$ \dbinom{\alpha}{k}=\dbinom{-n}{k}=\frac{-n(-n-1)...(-n-k+1)}{k!}\\
162+
=(-1)^k\frac{n(n+1)...(n+k-1)}{k!}=(-1)^k\dbinom{n+k-1}{k}$$
163163

164164
因此当$$ abs(z) $$ < 1有
165165

166166
$$ \frac{1}{(1+z)^n}=\sum_{k=0}^{\infty}(-1)^k\dbinom{n+k-1}{k} $$
167167

168168
用$$-z$$代替$$z$$，于是有
169169

170-
$$ \frac{1}{(1-z)^n}=\sum_{0}^{\infty}\dbinom{n+k-1}{k} $$
170+
$$ \frac{1}{(1-z)^n}=\sum_{k=0}^{\infty}\dbinom{n+k-1}{k} $$
171171

172172
作为特殊情况，当$$n=1$$时有
173173

174174
$$ \frac{1}{1+z}=\sum_{k=0}^{\infty}(-1)^kz^k \\
175175
\frac{1}{1-z}=\sum_{k=0}^{\infty}z^k $$
176-
176+
177177
## **重要的二项式系数恒等式**
178178

179179
1、（阶乘展开式）对整数$$n>=k>=0$$有

‎_posts/2018-05-09-codeforces666e-forensic-examination.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ img: https://vexoben.github.io/assets/images/Blog/2018-05-09-codeforces666e-fore
1111

1212
## **题意**
1313

14-
给定一个长为l(l<=500000)的字符串s，再给m(m<=50000)个总长不超过50000的字符串ti，q(q<=500000)组询问，每组询问(l,r,pl,pr)表示询问字符串s的子串s[l,r]，在字符串ti(l<=i<=r)中最多的出现次数。要求输出出现次数和出现次数最多的串的标号。
14+
给定一个长为l(l<=500000)的字符串s，再给m(m<=50000)个总长不超过50000的字符串ti，q(q<=500000)组询问，每组询问(l,r,pl,pr)表示询问字符串s的子串s[l,r]，在字符串ti(pl<=i<=pr)中最多的出现次数。要求输出出现次数和出现次数最多的串的标号。
1515

1616
## **题解**
1717

@@ -195,4 +195,5 @@ int main() {
195195
}
196196
```
197197
198-
[1]: http://codeforces.com/contest/666/problem/E
198+
[1]: http://codeforces.com/contest/666/problem/E
199+

‎_posts/2018-07-13-bzoj1443-[jsoi2009]游戏game.md

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -17,8 +17,6 @@ n,m<=100
1717

1818
## **题解**
1919

20-
给出题人点赞！
21-
2220
首先，给定一个棋盘，如果将它黑白染色，我们可以得到二分图。
2321

2422
这时可以观察到一个性质：如果AA将棋子放在一个不在最大匹配内的格子上，他是必胜的。

‎_posts/2018-10-15-agc002-做题小记.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -25,12 +25,14 @@ n ≤ 100000, a[i] ≤ 1e9
2525

2626
很奇妙的解法。
2727

28-
先按 a[i] 排个序。在坐标系中画出图标，其中 x = i 的位置有高度为 a[i] 的柱子。
28+
先按 a[i] 从大到小排个序。在坐标系中画出图标，其中 x = i 的位置有高度为 a[i] 的柱子。
2929

3030
可以发现，拿走最大一堆，就是向右走一个单位；从所有堆中取一个，就是向上走一个单位。从 (0, 0) 开始走。
3131

3232
打个表可以发现斜率为 1 的直线上的点胜负状态相同， 而一个边界上的点，向右向上有一个能走的步数为奇数就是胜态。
3333

34+
UPD: 除了终止态之外，所有斜率为 1 的直线上的点胜负状态相同。所以一个点的状态可以直接推到和一个边界上的点胜负状态相同。要证明这个结论，从两个方面证明. 1、如果一个点是必胜态，它右上角的点不可能是必败态，否则对手下一步一定可以走到右上角的那个点使自己陷入必败态；2、如果一个点是必败态，它右上角的点一定是必胜态。设这个点坐标是 (0, 0)， 那么 (0, 1) 和 (1, 0) 都是必胜态，由 1 的结论得知 (2, 1) 和 (1, 2) 一定是必胜态，从而 (1, 1) 只能转移到必胜态，它本身就是必败态。
35+
3436
```cpp
3537
#include<bits/stdc++.h>
3638
using namespace std;

‎_posts/2018-10-25-agc004-做题小记.md

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -63,7 +63,7 @@ $$O(n ^ 4)$$ DP即可。
6363

6464
### **题意**
6565

66-
给定一张 $$n$$ 个点 $$m$$ 条边的连通图，所有点初始为白色。每次可以选择两个同色相邻点，将他们颜色同时翻转。问将所有点变为黑色的最小步数。无解输出-1。
66+
给定一张 $$n$$ 个点 $$m$$ 条边的连通图，所有点初始为白色。每次可以选择两个同色相邻点，将他们颜色同时翻转。问将所有点变为黑色的最小步数。无解输出$-1$。
6767

6868
$$ N ≤ 100000 $$, $$ M ≤ N$$
6969

@@ -115,7 +115,7 @@ $$ N ≤ 100000 $$, $$ M ≤ N$$
115115

116116
当操作这条边时，它的影响不是交换两个点的颜色，而是将两个同色点反色。
117117

118-
我们用令一种语言表述树的情况。
118+
我们用另一种语言表述树的情况。
119119

120120
原问题：一张图分为X部和Y部，初始都为白色，每次可以选择一条边，将两个点的颜色同时取反。条件是两点同色。目标是让所有点反色。
121121

@@ -145,4 +145,5 @@ $$ N ≤ 100000 $$, $$ M ≤ N$$
145145
[7]: https://vexoben.github.io/contest/2018/08/30/atcoder-regular-contest-101.html
146146
[6]: https://agc004.contest.atcoder.jp/submissions/3460830
147147
[5]: https://www.lydsy.com/JudgeOnline/problem.php?id=1045
148-
[4]: https://agc004.contest.atcoder.jp/submissions/3468103
148+
[4]: https://agc004.contest.atcoder.jp/submissions/3468103
149+

‎_posts/2018-11-17-noip2018游记.md

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -101,6 +101,10 @@ T2看了一下觉得是每个斜列的个数加一乘起来。但是被样例2
101101

102102
性质A是个倍增维护dp的矩阵型转移。还剩半个小时的时候开始码但是没调出来。
103103

104+
还有一件非常惊险的事情是,在比赛结束准备离场的时候,突然心慌编译了一下 T3, 发现CE了! 这时候比赛结束的提示音已经响了233, 但是趁着大家离场非常混乱冷静改过了编译.
105+
106+
很庆幸当时可以那么镇定.
107+
104108
## **后记** ##
105109

106110
xjoi评测出来是 100 + 100 + 95 + 88 + 65 + 44 = 492，其中95和88是被xjoi卡常了。希望ccf那里能过。Day2T3不知道为什么fst了性质B的8分。
@@ -111,4 +115,6 @@ Day2考得相当惊险。虽然时间把控没有特别精准，但是作出几
111115

112116
再就是大赛经验不足，考场debuff太严重，思维完全没有平常训练的时候活跃。
113117

114-
这个分数应该能去冬令营？真正OI生涯的大门开始为我敞开，心里还是有几分向往的。
118+
这个分数应该能去冬令营？真正OI生涯的大门开始为我敞开，心里还是有几分向往的。
119+
120+
UPD: 实际得分 100 + 100 + 100 + 100 + 65 + 44 = 509. 好像 509 分太多了就 roll 了几个 509 去 WC, 然后非酋选手就被 D 没了.

0 commit comments

Comments
 (0)