当前位置：首页 > article >正文

取模+背包

article 2024/11/19 7:45:19

前言：一开始我想错了，一开始我想的是直接统计每一项模完后的和，我们只要能够取到一半，那么就有解，但是时间复杂度太大了

我们做推导
$x + y = s u m$
$x - y = k * n$
那么我们可以得到
$2 * x - s u m = k * n$
注意：由于取模相当于绕圈圈，所以我们要交替开两个数组记录

题目地址

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = (int)5e3 + 10;
int n, m;
int a[N];

signed main() {
	cin >> n >> m;
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		int u; cin >> u;
		a[i] = u % n;
		cnt += a[i];
	}
	cnt %= n;
	vector<int> dp(n+10, 0);
	dp[0] = 1;
	for (int i = 1; i <= m; i++) {
		vector<int> temp = dp;
		for (int j = 0; j <= n; j++) {
			if (dp[j]) {
				temp[(j + a[i]) % n] = 1;
			}
		}
		dp = temp;
	}
	// x + y = s , x - y = k*n
	// 2*x - x = k*n
	int ok = 0;
	for (int i = 0; i <= n; i++) {
		if (dp[i] && ((i * 2 - cnt) % n == 0)) {
			//cout << " i " << i << endl;
			ok = 1; break;
		}
	}
	if (ok) {
		cout << "YES";
	}
	else cout << "NO";
	return 0;
}