Submission #70063317

---

Source Code Expand

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

namespace IO {
	template<typename T> inline void read(T &x) {
		bool f = 1;
		x = 0;
		char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = 0;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch & 15), ch = getchar();
		x = f ? x : -x;
	}
	template<typename T> inline void write(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(('0' + x % 10));
	}
	template <typename T, typename ...Args> inline
	void read(T &x, Args &...args) {read(x), read(args...);}
	template<typename T> inline void write(T x, char c) {write(x), putchar(c);}
}
using namespace IO;
using S = vector<pair<int, int>>;

S merge(const S &a, const S &b) {
	unordered_map<int, int> tmp;
	for (auto [s, c] : a) tmp[s] += c;
	for (auto [s, c] : b) tmp[s] += c;
	return S(tmp.begin(), tmp.end());
}

S add(const S &a, int val, int mod) {
	unordered_map<int, int> tmp;
	for (auto [s, c] : a) {
		int sum = (s + val) % mod;
		tmp[sum] += c;
	}
	return S(tmp.begin(), tmp.end());
}

signed main() {
	int n, m;
	read(n, m);
	vector<int> f(n);
	for (int &x : f) read(x);

	if (m == 1) {
		vector<int> dp(n + 1);
		dp[0] = 1;
		if (n >= 1) dp[1] = 2;
		for (int i = 2; i <= n; ++i)
			dp[i] = dp[i - 1] + dp[i - 2];
		write(dp[n], '\n');
		return 0;
	}

	int mid = (n - 1) / 2;

	S ln = {{0, 1}}, ly;
	for (int i = 0; i <= mid; ++i) {
		S nen = merge(ln, ly);
		S ney = add(ln, f[i], m);
		ln.swap(nen);
		ly.swap(ney);
	}

	S rn = {{0, 1}}, ry;
	if (mid + 1 <= n - 1) {
		rn = {{0, 1}};
		ry.clear();
		for (int i = mid + 1; i < n; ++i) {
			S nen = merge(rn, ry);
			S ney = add(rn, f[i], m);
			rn.swap(nen);
			ry.swap(ney);
		}
	}

	unordered_map<int, int> x, y;
	for (auto [s, c] : rn) x[s] = c;
	for (auto [s, c] : ry) y[s] = c;

	int res = 0;
	for (auto [s, c] : ln) {
		int t = (m - s) % m;
		res += c * (x[t] + y[t]);
	}
	for (auto [s, c] : ly) {
		int t = (m - s) % m;
		res += c * x[t];
	}

	write(res, '\n');
	return 0;
}

Submission Info

Judge Result