题解：AT_arc164_d [ARC164D] 1D Coulomb

Link
dp 小水题。
注：洛谷翻译在某些细节上有问题，请到原网站查看题意。（因为比较复杂就不放了）

符号定义

\operatorname{sgn}(x)=\begin{cases}1&x>0\\0&x=0\\-1&x<0\end{cases}

解法

我们注意到，原子移动的方向恒不变。那么如果把原子移动的左右看成左右括号的话，所有原子的序列正好可以构成一个合法括号序列。而相撞的原子一定是序列中一对匹配的括号。
根据以上结论，我们要求和的式子无非就变成了

\sum\limits_{i=1}^{2n}-\operatorname{sgn}(F_i)\times i

，即括号互相匹配。
于是我们设

f_{i,j}

表示前

i+j

个原子中，有

i

个正原子、

j

个负原子的贡献。
因为我们要对所有情况求和，我们还需要令

g_{i,j}

表示方案数。
接下来推导转移：
当

i+j

位置可以为正原子时：

$g_{i,j}\gets g_{i,j}+g_{i-1,j}$
$f_{i,j}\gets f_{i,j}+f_{i-1,j}-\operatorname{sgn}(2i-2j-1)(i+j)g_{i-1,j}$

负原子时同理。
时间复杂度

O(n^2)

。
CODE:

CPP

//luogu paste jo5j6ogx
cst int N=3e3;
cst ll p=998244353;
string s;
int n;
ll f[N+10][N+10],g[N+10][N+10];
int main(void){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>s;s="="+s;
	g[0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			if(!(i|j)) continue;
			if(s[i+j]!='-'&&i){
				g[i][j]=madd(g[i][j],g[i-1][j],p);
				f[i][j]=madd(f[i][j],f[i-1][j],p);
				f[i][j]=madd(f[i][j],-sgn<int>((i<<1)-(j<<1)-1)*g[i-1][j]%p*(i+j)%p,p);
			}
			if(s[i+j]!='+'&&j){
				g[i][j]=madd(g[i][j],g[i][j-1],p);
				f[i][j]=madd(f[i][j],f[i][j-1],p);
				f[i][j]=madd(f[i][j],sgn<int>((i<<1)-(j<<1)+1)*g[i][j-1]%p*(i+j)%p,p);
			}
		}
	}
	write(f[n][n]);
	ret 0;
}

Record(Atcoder)

题解：AT_arc164_d [ARC164D] 1D Coulomb

文章操作

符号定义

解法

相关推荐

评论

题解：AT_arc164_d [ARC164D] 1D Coulomb