分零食[JSOI2012]

题目描述题面太长有$n$个人,$m$颗糖,要求给前若干个人分糖(把所有糖分完),如果一个人得到了$x$颗糖,那他的欢乐度就是$Ox^2+Sx+U$,一个分糖方案的总欢乐度是所有分到糖的人的欢乐度的乘积,求所有可行分糖方案的总欢乐度的总和。 题解首先有一个显然的dp方程: 设$dp[i][j]$表示给前$i$个人分了$j$颗糖,设$f(x)=Ox^2+Sx+U$,则$dp[i][j]=\sum...

任意模数NTT(拆系数FFT)

题目描述给定$2$个多项式$F(x), G(x)$,请求出$F(x) * G(x)$。 系数对$p$取模,且不保证$p$可以分解成$p = a \cdot 2^k + 1$之形式。 输入/输出不关心 $1 \leq n \leq 10^5, 0 \leq a_i, b_i \leq 10^9, 2 \leq p \leq 10^9 + 9$ 题解主要是记录一下一次FFT同时对两个多项式进行D...

力[ZJOI2014]

【题目描述】 给出$n$个数$q_1,q_2, \dots q_n$,定义 $F_j=\sum\limits_{i = 1}^{j - 1} \frac{q_i \times q_j}{(i - j)^2}-\sum\limits_{i = j + 1}^{n} \frac{q_i \times q_j}{(i - j)^2}$ $E_i=\frac{F_i}{q_i}$ 对$1 \leq ...