$O(n^3)$ 能过 n=1000?
by generals @ 2024-09-19 23:14:53
```cpp
for(int k=l;k<=r;k++){
if(a[k]!=v) continue;
int s=f[l][k-1]+f[k+1][r]+query(l,k-1)+query(k+1,r);
if(s<f[l][r]) f[l][r]=s;
}
for(int k=l;k<=r;k++){
if(a[k]!=v) continue;
int s=f[l][k-1]+f[k+1][r]+query(l,k-1)+query(k+1,r);
if(s==f[l][r]){
g[l][r]=(g[l][r]+(long long)g[l][k-1]*g[k+1][r]%998244353*c[r-l][k-l]%998244353)%998244353;
}
}
```
这个可以写成一个循环
by generals @ 2024-09-19 23:16:19
1e9再怎么搞也过不去吧，除非你常数几乎没有
by 枫原千叶 @ 2024-09-19 23:17:06
你都
`const int N=1006,mod=998244353;`
了，建议把`998244353`换成`mod`增加可读性
by generals @ 2024-09-19 23:17:40
@[xyz123](/user/379926) 先把 st 表大小两维交换个位置。
by Purslane @ 2024-09-19 23:22:07