母函数初探


一般生成函数

bzoj3028: 食物

裸题。
可乐的贡献:$1+x$
汉堡的贡献:$1+x^2+x^4+x^6…=\frac{x^{+\infty}-1}{x^2-1}$
鸡腿的贡献:$1+x+x^2=\frac{x^3-1}{x-1}$
蜜桃多的贡献:$x+x^3+x^5…=\frac{x^{+\infty}-x}{x^2-1}$
鸡块的贡献:$1+x^4+x^8+x^{12}…=\frac{x^{+\infty}-1}{x^4-1}$
包子的贡献:$1+x+x^2+x^3=\frac{x^4-1}{x-1}$
土豆片炒肉的贡献:$1+x$
面包的贡献:$1+x^3+x^6+x^9…=\frac{x^{+\infty}-1}{x^3-1}$
将他们乘到一起!
$f(x)=(1+x)\cdot\frac{x^{+\infty}-1}{x^2-1}\cdot\frac{x^3-1}{x-1}\cdot\frac{x^{+\infty}-x}{x^2-1}\cdot\frac{x^{+\infty}-1}{x^4-1}\cdot\frac{x^4-1}{x-1}\cdot(1+x)\cdot\frac{x^{+\infty}-1}{x^3-1}$
loli给我说一般认为|x|<1,否则级数不收敛。这样的话
$f(x)=\frac{x}{(x-1)^4}$
我们可以用广义二项式定理,即求$(x-1)^{-4}$的n项的系数,即$\binom {-4}{n}(-x)^n=\frac{(n+3)(n+2)(n+1)}{6}$
也可以
$g(x)=\frac{1}{(x-1)^4}=(1+x+x^2+x^3…)^4$,第n项的系数相当于将n个相同的球放入4个不同的盒子,每个盒子可以为空,求方案数,这就是$C_{n+3}^{3}$

阅读全文

重量平衡树和后缀平衡树

学习clj的论文


重量平衡树

  • 首先是动态区间k大,普通树套树,整体二分什么的就不谈了,还可以用重量平衡树来做平衡树套线段树。

阅读全文

期望与概率总结

本人暂时感觉一些简单题的解题方法有:
1。迭代的升级版:用线性数列的方法推矩阵,最后高斯消元。

  1. 考虑每个的期望(设当前状态到终点状态的期望),一般会形成一个有环的Dp,然后高斯消元。

阅读全文

字符串总结

最小表示法

很简单的一个东西

应用

bzoj1398

裸题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdC++.h>
using namespace std;
const int N = 1e6 + 9;
char A[N], B[N];
int n, sA, sB;
int get (char *s) {
int i = 0, j = 1, k = 0, mi;
for (; i < n && j < n && k < n; ) {
mi = s[i + k >= n ? i + k - n : i + k] - s[j + k >= n ? j + k - n : j + k];
if (mi == 0) ++k;
else if (mi > 0) i = i + k + 1, k = 0;
else j = j + k + 1, k = 0;
if (i == j) ++j;
}
return i < j ? i : j;
}
int main () {
scanf("%s%s", A, B); n = strlen(A);
sA = get(A); sB = get(B);
for (int i = 0; i < n; ++i) if (A[(sA + i) % n] != B[(sB + i) % n]) return puts("No"), 0;
puts("Yes");
for (int i = 0; i < n; ++i) putchar(A[(sA + i) % n]);
return 0;
}

阅读全文

atcoder记录

AGC001

D (1000)

被干了
将一个回文串看做回文串两边的点互相连边,要求最后形成一个联通块

阅读全文

kangaroo[CEOI2016]

这道题好像题解是用了将dp数组差分然后什么什么的,我原来感觉做了没有什么用,因为这是真的不容易想到(差分这种想法还是可以记下的),然后某天菜菜问了我这道题,我看了栋栋的题解,发现了好的做法。


我们知道每个排列与笛卡尔树一一对应。
然后就可以考虑这个排列的笛卡尔树。
我们考虑按权值从小到大依次加点:
在任何时刻,当前维护的排列的笛卡尔树一定是一个森林,其中每棵树,代表着一段。

阅读全文

bzoj2064

这道题本质其实上是求最多分成多少个组,使得每组的sum相同

$$
ans=n+m-2x
$$

考虑dp,f[i][j]表示将i这个集合用j里的元素来表示,最多凑成多少个集合。

  • sum(i) == sum(j)
    $$
    f[i][j] = max(f[i][j\wedge s]) + 1
    $$

阅读全文

NTT学习

$e^{ix}=cosx+isinx$
取素数$p=k*2^m+1$, $g为p的原根$ 设 $n=2^k$ 那么必须保证 $m>=k$
设$g_{n} \equiv g^{\frac{p-1}{n}} (mod p)$
那么$g_{n} \equiv e^{\frac{2\pi i}{n}} (mod p) $
实际中,我们一般选取$998244353=119*2^{23}+1$他的原根是5

阅读全文

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

阅读全文