Submission #70050244

---

Source Code Expand

#pragma GCC target("prefer-vector-width=512")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

int MOD;
pair<map<int, ll>, map<int, ll>> build_MP(vector<ll> v) {
	int n = v.size();
	map<int, ll> res1, res2;
	res2[0] = 1;
	rep(i, 0, n) {
		map<int, ll> nmp;
		for (auto [x, ad] : res2) {
			nmp[(x + v[i]) % MOD] += ad;
			res1[x] += ad;
		}
		swap(res1, nmp);
		swap(res2, nmp);
	}
	return {res1, res2};
}

void solve() {
	int n;
	cin >> n >> MOD;
	vector<ll> a(n);
	rep(i, 0, n) cin >> a[i];
	vector<ll> sa1, sa2;
	rep(i, 0, n / 2) sa1.push_back(a[i]);
	rep(i, n / 2, n) sa2.push_back(a[i]);
	reverse(sa2.begin(), sa2.end());
	auto [bmp1, bmp2] = build_MP(sa1);
	auto [amp1, amp2] = build_MP(sa2);
	ll ans = 0;
	for (auto [ct, ad] : bmp1) {
		auto itr = amp2.find((MOD - ct) % MOD);
		if (itr != amp2.end()) ans += ad * itr->second;
	}
	for (auto [ct, ad] : bmp2) {
		{
			auto itr = amp2.find((MOD - ct) % MOD);
			if (itr != amp2.end()) ans += ad * itr->second;
		}
		{
			auto itr = amp1.find((MOD - ct) % MOD);
			if (itr != amp1.end()) ans += ad * itr->second;
		}
	}
	cout << ans << '\n';
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) solve();
}

Submission Info

Judge Result