C/C++教程

[ARC124E] Pass to Next

本文主要是介绍[ARC124E] Pass to Next，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言

这题补了一万年，终于过了。

模拟赛撞原题不会可太艹了

题目

AtCoder

题目大意：

给定一个整数 \(N\) 表示人数，接下来给出序列 \(A\)，\(A_i\) 表示第 \(i\) 个人拥有的球的数量。

这 \(N\) 个人坐成一个环，接下来他们会同时给右边那个人自己的一部分球(当然可以全给或者不给)，记操作后的序列为 \(S\)，定义其权值 \(f(S)=\prod S_i\)，求所有不同的 \(S\) 的权值和，答案对 \(998244353\) 取模。

\(3\le N\le 10^5;0\le A_i\le 10^9.\)

讲解

解题前的热身

首先不要把题目想错了，每个人给的球数量不同并不一定等同于最后的 \(S\) 序列不同。

然后我们挖掘性质：如果每个人都至少给出了一个球，其实可以让每个人都少给相同的个数，效果相同，所以至少有一个人没给球。

从简单入手

考虑最暴力的 dp，令 \(dp_{i,j}\) 表示第 \(i\) 个人给 \(j\) 个球的前缀乘积和，然后我们指定 \(i\) 不给球，为了不算重，需要指定他前面的人必须给球。

然后我们就有了一个 \(O(n^2A_i^2)\) 的超高效做法(注意我并没有把指定给球或不给球体现在转移方程中)：

\[dp_{j,k}=\sum_{l=0}^{a_{j-1}}dp_{j-1,l}\times (a_j + l-k) \]

最后只需要把所有的 \(dp_{i,0}\) 累加起来即可。

优化1

这时间复杂度看上去非常恐怖，但事实上它完全可以优化：

\[\begin{aligned}dp_{j,k}&=\sum_{l=0}^{a_{j-1}}dp_{j-1,l}\times (a_j+l-k)\\&=\sum_{l=0}^{a_{j-1}}dp_{j-1,l}\times l+\sum_{l=0}^{a_{j-1}}dp_{j-1,l}\times (a_j-k)\\\end{aligned} \]

可以发现只需求出 \(\sum_{l=0}^{a_{j-1}}dp_{j-1,l}\times l\) 和 \(\sum_{l=0}^{a_{j-1}}dp_{j-1,l}\times (a_j-k)\) 即可完成转移，可以简单优化为 \(O(n^2A_i)\)。

优化2

既然我们已经发现可以维护上面那两个东西就完成转移，我们令：

\[\begin{aligned}f(j)&=\sum_{l=0}^{a_{j}}dp_{j,l}\\g(j)&=\sum_{l=0}^{a_{j}}dp_{j,l}\times l\end{aligned} \]

不难写出转移(其实是把草稿本的内容抄过来)：

\[\begin{aligned}f(j)&=(a_j-[j<i]+1) * (g(j-1) + a_j * f(j-1)) - lr(a_j) * f(j-1)\\g(j)&=lr(a_j) * (g(j-1) + a_j * f(j-1)) - lr2(a_j) * f(j-1)\times l\end{aligned} \]

注：\(lr(x)=\frac{(1+x)\times x}{2},lr2(x)=\frac{x\times (x+1)\times (2x+1)}{6}\)，分别对应 \(1\) 次和 \(2\) 次的求和公式。

此时我们需要累加的就是 \(f(i-1)\times a_i+g(i-1)\)。

现在时间复杂度已经优化到了 \(O(n^2)\)。

优化3

到这一步其实已经很简单了，用矩阵转移相当方便，分别维护一下前后缀即可。

时间复杂度 \(O(n)\)。

代码

附赠草稿纸的代码 
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;
 
typedef long long LL;
const int MAXN = 100005;
const int MOD = 998244353;
const int inv2 = (MOD+1) >> 1;
const int inv6 = 166374059;
int N,ans;
int a[MAXN];
 
LL Read()
{
    LL x = 0,f = 1; char c = getchar();
    while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
    return x * f;
}
TT void Put1(T x)
{
    if(x > 9) Put1(x/10);
    putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
    if(x < 0) putchar('-'),x = -x;
    Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
 
LL lr(LL x){return (x+1) * x % MOD * inv2 % MOD;}
LL lr2(LL x){return x * (x+1) % MOD * (2*x+1) % MOD * inv6 % MOD;}

struct Matrix
{
	int n,m,a[2][2];
	
	Matrix(){memset(a,0,sizeof(a));}
	
	Matrix operator * (const Matrix &C)const{
		Matrix ret; ret.n = n; ret.m = C.m;
		for(int i = 0;i < n;++ i)
			for(int k = 0;k < m;++ k)
				if(a[i][k])
					for(int j = 0;j < C.m;++ j)
						ret.a[i][j] = (ret.a[i][j] + 1ll * a[i][k] * C.a[k][j]) % MOD;
		return ret;
	}
	
	void print()
	{
		putchar('\n');
		for(int i = 0;i < n;++ i,putchar('\n'))
			for(int j = 0;j < m;++ j)
				Put(a[i][j],' ');
	}
}pre[MAXN],suf[MAXN],I,A,tt;
 
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
	I.n = I.m = 2; I.a[0][0] = I.a[1][1] = 1;
    N = Read();
	tt = pre[0] = suf[N+1] = I;
    for(int i = 1;i <= N;++ i) a[i] = Read();
    for(int j = 1;j <= N;++ j)
    {
    	pre[j].n = pre[j].m = 2;
    	pre[j].a[0][0] = (1ll*a[j]*a[j]-lr(a[j])) % MOD;
    	pre[j].a[1][0] = a[j];
    	pre[j].a[0][1] = (lr(a[j])*a[j]-lr2(a[j])) % MOD;
    	pre[j].a[1][1] = lr(a[j]);
    	if(j > 1 && j < N) tt = tt * pre[j];
    	pre[j] = pre[j-1] * pre[j];
	}
	for(int j = N;j >= 1;-- j)
	{
    	suf[j].n = suf[j].m = 2;
    	suf[j].a[0][0] = ((a[j]+1ll)*a[j]-lr(a[j])) % MOD;
    	suf[j].a[1][0] = (a[j]+1)%MOD;
    	suf[j].a[0][1] = (lr(a[j])*a[j]-lr2(a[j])) % MOD;
    	suf[j].a[1][1] = lr(a[j]);
    	suf[j] = suf[j] * suf[j+1];
	}
	A.n = 1;A.m = 2;
	for(int i = 1;i <= N;++ i)
	{
		int i1 = i+1; if(i1 > N) i1 = 1;
		A.a[0][0] = lr(a[i1]); A.a[0][1] = (lr(a[i1]) * a[i1] - lr2(a[i1])) % MOD;
		if(i1 < i) A.a[0][0] = (A.a[0][0] - a[i1] + MOD) % MOD;
		if(i+2 <= N) A = A * suf[i+2];
		if(i^N) A = A * pre[i-1];
		else A = A * tt;
		ans = (ans + A.a[0][1] + 1ll * a[i] * A.a[0][0]) % MOD;
	}
    Put((ans+MOD)%MOD,'\n');
    return 0;
}
/*
如果过了把 define int LL 删了 
现在已经是 O(n^2) 啦，下午来套个矩阵就过了！ 
好家伙，现在到晚上了 
\sum i * (x-i) = ix - i^2 = lr(x)x - lr2(x)

搞错啦搞错啦，
应该是枚举一个不给，前面枚举过的都必给 
f(j) = \sum(k) dp[j][k]
g(j) = \sum(k) dp[j][k] * k
dp[j][k] += dp[j-1][l] * (a[j] - k + l)   l\in[0,a[j-1]]
dp[j][k] = g(j-1) - k * f(j-1) + a[j] * f(j-1)

f(j) = \sum(k:(j<i)~a[j]) g(j-1) - k * f(j-1) + a[j] * f(j-1)
	 = (a[j]-(j<i)+1) * g(j-1) - lr(a[j]) * f(j-1) + (a[j]-(j<i)+1) * a[j] * f(j-1)
	 = (a[j]-(j<i)+1) * (g(j-1) + a[j] * f(j-1)) - lr(a[j]) * f(j-1)

pre 
f 					g
a[j]*a[j]-lr(a[j])  lr(a[j])*a[j]-lr2(a[j])
a[j]                lr(a[j])
	 
g(j) = \sum(k:(j<i)~a[j]) (g(j-1) - k * f(j-1) + a[j] * f(j-1)) * k
	 = \sum(k:(j<i)~a[j]) k * g(j-1) - k^2 * f(j-1) + k * a[j] * f(j-1)
	 = lr(a[j]) * g(j-1) - lr2(a[j]) * f(j-1) + lr(a[j]) * a[j] * f(j-1)
	 = lr(a[j]) * (g(j-1) + a[j] * f(j-1)) - lr2(a[j]) * f(j-1)
dp[j][0] = g(j-1) - a[j] * f(j-1)

suf
f 				     	g
(a[j]+1)*a[j]-lr(a[j])  lr(a[j])*a[j]-lr2(a[j])
a[j]+1                  lr(a[j])
*/

总结

有些题的 dp 可以由相当暴力的转移方程优化得到正解，然而我们要怎么确定这条路一定走得通呢？

这道题的特点是最初 \(j,k,l\) 转移的时候 \(k,l\) 其实并没有恐怖地揉在一起，使得我们有将其拆开的机会。

后来定义 \(f,g\) 的时候我们是发现其实并不需要这么多状态，只需要整体即可，故可以整体转移。

当然还是要多做题找经验。

我没有暗示水子哥。

这篇关于[ARC124E] Pass to Next的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航