求解答三个问题

代码的时间复杂度是多少？用了 lowbit 优化的时间复杂度还是 $\mathcal{O}(N * 2 ^ N + N * M)$ 吗？如果是，为什么不超时？代码运行的大致次数超过了四个亿……？“常数优化”到底优化在哪使得运行次数小于两个亿？AC 代码连样例 2 都超时……
开 long long 会爆空间 MLE，但是 $a_i \le 1e9$ ，三个幸运数字（即 $3 * a_i$ ）就会超过 int 范围（ $3000000000 \gt 2147483647$ ），更何况说 $n$ 个幸运数字……所以为什么不会爆 int 而导致答案错误呢？
在不考虑时间复杂度的情况下，下面这两份代码实现内容上的区别是什么？为什么一个得十分一个 AC？

这两份代码的 dp 都是一模一样的，不一样的点在于

a_i

，即对判断是否踩在厄运数字上的统计和的方式不同。

CPP

//WA，仅 AC #3
int main(){
	int n, m, S;
	n = read();
	S = (1 << n) - 1;
	for(int i = 1; i <= n; ++i){
		a[i] = read() % Mod;
	} 
	m = read();
	for(int i = 1; i <= m; ++i){
		b[i] = read() % Mod;
	}
	for(int i = 2; i <= S; ++i){
		lg[i] = lg[i >> 1] + 1;
	}
	f[0] = 1;
	for(int i = 1; i <= S; ++i){
		int s = 0, ff = 1;
		for(int j = i; j > 0; j -= lowbit(j)){
			s += a[lg[lowbit(j)] + 1];
		}
		for(int j = 1; j <= m; ++j){
			if(s == b[i]){
				ff = 0;
				break;
			}
		}
		if(ff == 0) continue;;
		for(int j = i; j > 0; j -= lowbit(j)){
			f[i] += f[i ^ lowbit(j)];
			f[i] %= Mod;
		}
	}
	write(f[S]);
	return 0;
}

CPP

//AC，题解做法
int main(){
	int n, m, S;
	n = read();
	S = (1 << n) - 1;
	for(int i = 1; i <= n; ++i){
		a[1 << i - 1] = read() % Mod;
	} 
	m = read();
	for(int i = 1; i <= m; ++i){
		b[i] = read() % Mod;
	}
	f[0] = 1;
	for(int i = 1; i <= S; ++i){
		a[i] = a[i ^ lowbit(i)] + a[lowbit(i)];
		if(a[i] == b[1] || a[i] == b[2]) continue;
		for(int j = i; j > 0; j -= lowbit(j)){
			f[i] += f[i ^ lowbit(j)];
			f[i] %= Mod;
		}
	}
	write(f[S]);
	return 0;
}

讨论操作

回复

相关推荐

求解答三个问题