Codeforces 729 Div.2

赛时通过 \(\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;
}
上一篇:牛客挑战赛51 A.NIT的签到题(暴力gcd)


下一篇:习题4-7 最大公约数和最小公倍数 (15 分)