赛时通过 \(\text{A,B,C,D}\)，排名 \(255\)。
A
略。
B
绝了，我被这题卡了 \(40\) 分钟。。。
考虑所有能被表示出来的数一定是这样的：\(a^m+k_1ba^m+k_2ba^{m-1}+\dots +k_mb(k_i,m\in \mathbb{N^+})\)。枚举 \(m\)，并判断 \(n-a^m\) 能否被 \(b\) 整除即可。
C
可以发现 \(f(i)\) 不会很大，因为当 \(f(i)=y\) 时，\(1\dots (y-1)\) 都需要整除 \(i\)，即 \(\operatorname{lcm}(1,2,\dots,y-1)\mid i\)，而 \(\operatorname{lcm}(1,2,\dots,41)>10^{16}\)。
于是枚举 \(f(i)\) 的取值 \(y\)，此时 \(i\) 需要满足 \(\operatorname{lcm}(1,2,\dots,y-1)\mid i \land \operatorname{lcm}(1,2,\dots,y)\nmid i\)。满足条件的 \(i\) 有 \(\lfloor \frac{n}{\operatorname{lcm}(1,2,\dots,y-1)}\rfloor-\lfloor\frac{n}{\operatorname{lcm}(1,2,\dots,y)}\rfloor\) 个。
D
考虑计算每一个 + 操作对答案的贡献。即，钦定一个 + 操作必须选，我们需要计算有多少种方案使得这个 + 操作不会被 pop 掉。
设这个 + 操作在位置 \(i\)，数字为 \(x\)，那么：
- 假如一个操作
+ y的位置小于 \(i\)，且 \(y\le x\)，那么这个数 \(y\) 是否被 pop 掉是随意的，但我们需要记录有多少个 \(y\) 满足 \(y\le x\) 没有被 pop 掉。 - 假如一个操作
+ y的位置小于 \(i\)，且 \(y>x\)，那么它是否被 pop 掉也是随意的，但需要注意它要在所有 \(<x\) 的数都被 pop 掉的情况下才能被 pop。而且我们不需要知道有多少个这样的数。 - 假如一个操作
-的位置小于 \(i\)，那么它会优先 pop 掉 \(<x\) 的数。而且当没有 \(<x\) 的数时，加入这样的操作也是合法的。 - 假如一个操作
+ y的位置大于 \(i\)，且 \(y<x\)，那么它可以随意地被加入、删除。 - 假如一个操作
+ y的位置大于 \(i\)，且 \(y\ge x\)，那么它只能被加入而不能被删除，因为我们需要保证 \(x\) 没有被删除。 - 假如一个操作
-的位置大于 \(i\)，那么仅当 满足 \(y<x\) 的 \(y\) 个数大于 \(0\) 时，这个-操作才能被选择。
注意到上面第一条是 \(\le\) 而第四条是 \(<\)。这是因为当集合里有多个相同元素时，pop 只会 pop 掉一个。所以我们需要钦定哪一个被 pop 掉。
大力 dp 即可。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
typedef long long ll;
const int N=505,Mod=998244353;
int n;ll a[N],f[N][N],g[N][N];
int main(){
scanf("%d",&n);
char tmp[10];
For(i,1,n){
scanf("%s",tmp);
if(tmp[0]==‘-‘) a[i]=-1;
else scanf("%lld",&a[i]);
}
ll ans=0;
For(i,1,n){
if(a[i]<0) continue;
memset(f,0,sizeof f);
memset(g,0,sizeof g);
f[0][0]=1;
For(j,1,i-1){
For(k,0,j){
if(a[j]<0){
if(!k) f[j][k]=(f[j-1][k]*2+f[j-1][k+1])%Mod;
else f[j][k]=(f[j-1][k]+f[j-1][k+1])%Mod;
}else if(a[j]<=a[i]){
if(!k) f[j][k]=f[j-1][k];
else f[j][k]=(f[j-1][k-1]+f[j-1][k])%Mod;
}else f[j][k]=f[j-1][k]*2%Mod;
// printf("f:%d,%d:%lld\n",j,k,f[j][k]);
}
}
For(k,0,i-1) g[i][k]=f[i-1][k];
For(j,i+1,n){
For(k,0,j){
if(a[j]<0){
if(!k) g[j][k]=(g[j-1][k]+g[j-1][k+1])%Mod;
else g[j][k]=(g[j-1][k]+g[j-1][k+1])%Mod;
}else if(a[j]<a[i]){
if(!k) g[j][k]=g[j-1][k];
else g[j][k]=(g[j-1][k-1]+g[j-1][k])%Mod;
}else g[j][k]=g[j-1][k]*2%Mod;
// printf("g:%d,%d:%lld\n",j,k,g[j][k]);
}
}
ll res=0;
For(k,0,n) res=(res+g[n][k])%Mod;
ans=(ans+a[i]*res%Mod)%Mod;
}
printf("%lld\n",ans);
return 0;
}