敬重爵兰！！！

本人使用了记搜，在某个状态合法时，直接返回

1

，如果最后数值

res>0

，那么显然是有解的。

WA30分部分代码如下：

CPP

int dfs(int u,int nw){
	if(u==n+1){
		if((nw%k+k)%k) return 0;
		return 1;
	}
	if((~mry[u][nw])) return mry[u][nw];
	int res = 0;
	res += dfs(u+1,((nw-num[u])%k+k)%k);
	res += dfs(u+1,((nw+num[u])%k+k)%k);
	mry[u][nw] = res;
	return res;
}

WA是因为 $n \le 1e4$ ，也就是说可能有很多个合法解，每个合法解贡献 $1$ ，那么最后值甚至会爆掉long long，导致判断错误。

稍微转变一下思路将有合法解就贡献

1

，改成布尔值异或

1

即可。

AC代码如下：

CPP

bool dfs(int u,int nw){
	if(u==n+1){
		if((nw%k+k)%k) return 0;
		return 1;
	}
	if((~mry[u][nw])) return mry[u][nw];
	bool res = 0;
	res |= dfs(u+1,((nw-num[u])%k+k)%k);
	res |= dfs(u+1,((nw+num[u])%k+k)%k);
	mry[u][nw] = res;
	return res;
}

讨论操作

回复

相关推荐

敬重爵兰！！！