题解：AT_arc164_d [ARC164D] 1D Coulomb

Elairin176 · 2025-01-15 11:46:55 · 题解

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

符号定义

解法

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

//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)