分零食[JSOI2012]

标签：its   swa   lld   names   main   lan   就是   数组   http   

题目描述

题面太长
有\(n\)个人，\(m\)颗糖，要求给前若干个人分糖(把所有糖分完)，如果一个人得到了\(x\)颗糖，那他的欢乐度就是\(Ox^2+Sx+U\)，一个分糖方案的总欢乐度是所有分到糖的人的欢乐度的乘积，求所有可行分糖方案的总欢乐度的总和。

题解

首先有一个显然的dp方程：

设\(dp[i][j]\)表示给前\(i\)个人分了\(j\)颗糖，设\(f(x)=Ox^2+Sx+U\)，
则\(dp[i][j]=\sum\limits_{k=1}^{j-i+1} dp[i-1][j-k]*f(k)\)

答案即为\(\sum\limits_{i=1}^{n} dp[i][m]\)

考虑如何优化这个式子

如果把\(dp[i-1][j-k]*f(k)\)看作一个卷积形式的话，我们会发现\(dp[i]\)这一个数组就是\(dp[i-1]\)和\(f\)的卷积

我们把\(f\)以及\(dp[i]\)看作一个多项式，那么有\(f=f(1)x+f(2)x^2+f(3)x^3+\dots+f(m)x^m\)

由于\(dp[i]=dp[i-1]*f\)，所以显然\(dp[i]=f^i\) (这里的乘方是指\(i\)次卷积，不是指\(i\)次方。。。)

可以使用FFT优化卷积

但是\(n\le 10^8\)，这样还是跑不过，还需要进行优化：

卷积满足交换律，所以可以进行快速幂优化。但是我们要求的答案是\(\sum\limits_{i=1}^{n} dp[i][m]\)，如果用快速幂的话没法计算答案啊

所以我们再定义一个多项式\(sum[i]=\sum\limits_{j=1}^i dp[i]\)，也就是前缀和

首先要意识到，根据上面的定义\(dp[i]=f^i\)，那么显然\(dp[a+b]=dp[a]*dp[b]\)

然后看一下\(sum\)是怎么快速幂递推的

假设现在在计算\(sum[x]\)和\(dp[x]\)

若\(x\)为偶，

则\(dp[x]=dp[\frac{x}{2}]*dp[\frac{x}{2}]\)；

\(sum[x]=sum[\frac{x}{2}]+\sum\limits_{i=x/2+1}^x dp[i]\)
\(=sum[\frac{x}{2}]+dp[\frac{x}{2}]\sum\limits_{i=1}^{x/2} dp[i]\)
\(=sum[\frac{x}{2}]+dp[\frac{x}{2}]*sum[\frac{x}{2}]\)

若\(x\)为奇

那就先把\(dp[x-1]\)和\(sum[x-1]\)用上面的方法算出来，然后\(dp[x]=dp[x-1]*f\)，\(sum[x]=sum[x-1]+dp[x]\)

最后的答案就是\(sum[n][m]\)

时间复杂度\(O(m\log m\log n)\)

代码

#include 
using namespace std;
typedef long long ll;

const ll mod = 998244353, G = 3, invg = 332748118;
int N, m, lim, l, rev[100005], tot;
ll dp[100005], sum[100005], F[100005], tmp[100005], invn, O, S, U, p;
ll aa[100005], bb[100005];

inline ll fpow(ll x, ll t) {
	ll ret = 1;
	for (; t; t >>= 1, x = x * x % mod) if (t & 1) ret = ret * x % mod;
	return ret;
}

void NTT(ll *c, int tp) {
	for (int i = 0; i > 1);
	tot++;
	Mul(dp, sum, tmp);
	Mul(dp, dp, dp);
	for (int i = 0; i >1]>>1)|((i&1)

分零食[JSOI2012]

标签：its   swa   lld   names   main   lan   就是   数组   http   

原文地址：https://www.cnblogs.com/ak-dream/p/AK_DREAM88.html