zcmimi's blog

arrow_back多项式共11篇文章

avatar
zcmimi
2020-08-27 22:46:00
avatar
zcmimi
2020-08-27 16:32:00

问题

\displaystyle \sum\limits_{i=1}^n i^k

1258 序列求和 V4

普通求法:

$$ (n+1)^{k+1}-

avatar
zcmimi
2020-08-24 19:20:00

给定序列A,B,设

C_i=\sum_{j\oplus k=i}A_j \times B_k

分别当\oplusor,and,xor时求出C

思想

\text{fwt}_A为对A进行快速沃尔什变换后的序列

$A\rightarrow \te

avatar
zcmimi
2020-07-09 22:36:00

平面上n+1个点可以确定一个n次多项式F(x)

拉格朗日插值法可以根据n+1个点确定一个n次多项式

设这n个点为(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)

构造多项式 $\displaystyle \elli(x)=\prod{j=

avatar
zcmimi
2020-06-25

推荐:

定义

生成函数又称母函数

设序列aa_0,a_1,a_2,\dots

avatar
zc
2020-09-15 20:16:00
查看原题

点击跳转

g(n)为点数为n的无向图个数

g(n)=2^{n\choose 2}

f(n)为点数为n的简单无向连通图的数量

枚举连通块个数i可得

\displaystyle g(n)=\sum_{i=0}^n \frac{f(i)}{i!}

发现这个形式很眼熟(生成函数):

g=e^f

那么f=\ln g

求出g\ln就可以得到f

avatar
zc
2020-09-15 18:49:00
查看原题

点击跳转

给两个手环同时增加亮度,与给其中一个增/减亮度是一样的

同时旋转两个手环,旋转其中一个是一样的

设旋转后两个手环分别为a,b,其中一个加上x

那么就是让\sum_{i=1}^n (a_i-b_{i}+x)^2最小

\displaystyle \sum_{i=1}^n (a_i-b_{i}+x)^2\\ =\sum_{i=1}^n a_i^2+\sum_{i=1}^n b_i^2+nx^2+2x(\sum_{i=1}^n a_i-b_i)-2\sum_{i=1}^n a_ib_i

其中只有最后一项是变化的,前几项都可以直接求得

nx^2+2x(\sum_{i=1}^n a_i-b_i)是关于x的二次函数,直接求得最小值

考虑\sum_{i=1}^n a_ib_i

可以发现\sum_{i=1}^n a_{n-i+1}b_i是卷积的形式

那么我们把a倍长,把b翻转,然后再卷积,得到n+12n次项中的最大值就是\sum_{i=1}^n a_ib_i的最大值

avatar
zc
2020-08-23 10:18:00
查看原题

点击跳转

avatar
zc
2020-07-05 13:10:00
查看原题

点击跳转

首先找位置对称的回文子序列个数(多项式求)

由于不能连续,所以减去对称回文子串个数(manacher求)

设字符串为S,|S|=n

假设S_i作为一个子序列的对称中心,x=\sum_{j=1\le j\le i-1}[S_{i-j}=S_{i+j}]

那么以i为中心位置的方案数为2^{x+1}-1

A_i=[S_i=a],B_i=[S_i=b]

那么\displaystyle (A*A)_i=A_i*A_i=\sum_{j=0}^nA_jA_{i-j}就是对称中心为位置\frac i2的两端为a的数量

同理(B*B)_i就是对称中心为位置\frac i2的两端为b的数量

那么上述(A*A)_i+(B*B)_i就是对称中心为位置\frac i2x+1

如果i为偶数,x+1要减去1(对称中心是否在同个字符上)

avatar
zc
2020-02-07 12:02:00
查看原题

点击跳转

1/2
Search
search