結果
問題 | No.1972 Modulo Set |
ユーザー |
![]() |
提出日時 | 2022-06-10 22:40:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 20,305 bytes |
コンパイル時間 | 4,739 ms |
コンパイル使用メモリ | 276,160 KB |
最終ジャッジ日時 | 2025-01-29 20:08:27 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h>/*#include <boost/multiprecision/cpp_dec_float.hpp>#include <boost/multiprecision/cpp_int.hpp>namespace mp = boost::multiprecision;using bint = mp::cpp_int;*/#include <atcoder/all>#define rep(i,n) for (int i = 0; i < int(n); ++i)#define repp(i,n,m) for (int i = m; i < int(n); ++i)#define repb(i,n) for (int i = int(n)-1; i >= 0; --i)#define endl "\n"using namespace std;using namespace atcoder;using ll = long long;using ld = long double;using P = pair<int, int>;using PL = pair<long long, long long>;using pdd = pair<long double, long double>;using pil = pair<int,ll>;using pli = pair<ll,int>;using ppi = pair<P,int>;using pip = pair<int,P>;const int INF = 1001001007;const long long mod1 = 1000000007LL;const long long mod2 = 998244353LL;const ll inf = 2e18;const ld pi = 3.14159265358979323;const ld eps = 1e-7;const char _ = ' ';template<typename T>void o(T a);template<class T>istream &operator>>(istream &is,vector<T> &v){for(auto &e:v)is>>e;return is;}template<class T>ostream &operator<<(ostream &os,const vector<T> &v){if(v.size()!=0){rep(i,v.size())os<<v[i]<<(i+1==v.size()?"":" ");}return os;}template<class T>istream &operator>>(istream &is,vector<vector<T>> &v){for(auto &e:v)is>>e;return is;}template<class T>ostream &operator<<(ostream &os,const vector<vector<T>> &v){if(v.size()!=0){for(auto &e:v)o(e);}return os;}template<typename T>bool range(T a,T b,T x){return (a<=x&&x<b);}template<typename T>bool rrange(T a,T b,T c,T d,T x,T y){return (range(a,c,x)&&range(b,d,y));}template<typename T>void rev(vector<T> &v){reverse(v.begin(),v.end());}void revs(string &s) {reverse(s.begin(),s.end());}template<typename T>void sor(vector<T> &v, int f=0){sort(v.begin(),v.end());if(f!=0) rev(v);}template<typename T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}template<typename T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<typename T>void eru(vector<T> &v){sor(v);v.erase(unique(v.begin(),v.end()),v.end());}template<typename T>T cel(T a,T b){if(a%b==0)return a/b;return a/b +1;}void o(){cout<<"!?"<<endl;}template<typename T>void o(T a){cout<<a<<endl;}template<typename T>void mout(T a){cout<<a.val()<<endl;}void print(){ putchar(' '); }void print(bool a){ printf("%d", a); }void print(int a){ printf("%d", a); }void print(long a){ printf("%ld", a); }void print(long long a){ printf("%lld", a); }void print(char a){ printf("%c", a); }void print(char a[]){ printf("%s", a); }void print(const char a[]){ printf("%s", a); }void print(long double a){ printf("%.15Lf", a); }void print(const string& a){ for(auto&& i : a) print(i); }template<class T> void print(const T& a){ cout << a; }int out(){ putchar('\n'); return 0; }template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }void yes(){cout << "Yes" << endl;}void no (){cout << "No" << endl;}void yn (bool t){if(t)yes();else no();}template<typename T>void dame(bool t, T s){if(!t){cout << s << endl;exit(0);}}void fast_io(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);}template<typename T,typename U>void o2(pair<T,U> a){out(a.first,a.second);}vector<int> dx = {0,1,0,-1,1,1,-1,-1};vector<int> dy = {1,0,-1,0,1,-1,-1,1};const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";const string alp = "abcdefghijklmnopqrstuvwxyz";const string NUM = "0123456789";ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}ll lcm(ll a,ll b){return a/gcd(a,b)*b;}ll mpow(ll x,ll n,ll m){if(n==0)return 1LL;x%=m;ll a=mpow(x,n/2,m);a=a*a%m;return (n&1)?a*x%m:a;}template<typename T> ll tentou(vector<T> ar){int n = ar.size();set<T> st;rep(i,n) st.insert(ar[i]);map<T,int> mp;int ind = 0;for (T x : st){mp[x] = ind;ind++;}fenwick_tree<ll> fw(ind);ll ans = 0;rep(i,n){int a = mp[ar[i]];ans += i - fw.sum(0,a+1);fw.add(a,1);}return ans;}struct edge{int from, to;long long cost;edge(int _from = -1, int _to = -1, long long _cost = 1LL) : from(_from), to(_to), cost(_cost) {}};struct vertex{vector<edge> adj;};struct Graph{int n;vector<vertex> vs;void add_edge(int from, int to, long long cost = 1LL){assert(0 <= from && from < n);assert(0 <= to && to < n);vs[from].adj.emplace_back(edge(from,to,cost));}void add_dual_edge(int from, int to, long long cost = 1LL){assert(0 <= from && from < n);assert(0 <= to && to < n);vs[from].adj.emplace_back(edge(from,to,cost));vs[to].adj.emplace_back(edge(to,from,cost));}Graph(int _n) : n(_n) , vs(n) {}vector<long long> dijkstra(int s){using pli = pair<long long, int>;priority_queue<pli, vector<pli>, greater<pli>> pque;vector<long long> dist(n,inf);dist[s] = 0LL;pque.push(pli(0,s));while (!pque.empty()){pli p = pque.top(); pque.pop();if (dist[p.second] < p.first) continue;for (edge x : vs[p.second].adj){if (dist[x.to] > p.first + x.cost){dist[x.to] = p.first + x.cost;pque.push(pli(dist[x.to],x.to));}}}return dist;}vector<long long> bfs01(int s){deque<int> que;vector<long long> dist(n,inf);dist[s] = 0LL;que.push_front(s);while (!que.empty()){int p = que.front(); que.pop_front();for (edge x : vs[p].adj){if (dist[x.to] > dist[p] + x.cost){dist[x.to] = dist[p] + x.cost;if (x.cost == 0LL) que.push_front(x.to);else que.push_back(x.to);}}}return dist;}vector<int> dfs(int s){vector<int> ans;vector<int> vis(n,0);_dfs(s,ans,vis);return ans;}private:void _dfs(int s, vector<int> &ans, vector<int> &vis){vis[s]++;for (edge x : vs[s].adj){if (vis[x.to] == 0){_dfs(x.to,ans,vis);}}ans.emplace_back(s);}};struct Tree{Tree(int _n, int _root = 0) : n(_n), root(_root) {assert(0 <= root && root < n);initialize();}void add_edge(int from, int to, long long cost = 1LL){assert(0 <= from && from < n);assert(0 <= to && to < n);vs[from].adj.emplace_back(edge(from,to,cost));}void add_dual_edge(int from, int to, long long cost = 1LL){assert(0 <= from && from < n);assert(0 <= to && to < n);vs[from].adj.emplace_back(edge(from,to,cost));vs[to].adj.emplace_back(edge(to,from,cost));}int size(){return n;}int parent(int v){assert(0 <= v && v < n);if (is_done_par_rdist_init == false) par_rdist_init();return par[v];}int depth(int v){assert(0 <= v && v < n);if (dep[v] != -1) return dep[v];if (v == root) return dep[v] = 0;return dep[v] = depth(parent(v)) + 1;}int subtree_size(int v){assert(0 <= v && v < n);if (sub[v] != 0) return sub[v];sub[v] = 1;for (edge x : vs[v].adj){if (x.to != parent(v)) sub[v] += subtree_size(x.to);}return sub[v];}int lca(int u, int v){assert(0 <= u && u < n);assert(0 <= v && v < n);if (is_done_lca_init == false) lca_init();if (depth(u) > depth(v)) swap(u,v);for (int i = 0; i < 30; i++) if ((depth(v) - depth(u)) >> i & 1) v = par2[i][v];if (u == v) return u;for (int k = 29; k >= 0; k--){if (par2[k][u] != par2[k][v]) {u = par2[k][u];v = par2[k][v];}}return par2[0][u];}long long dist(int u, int v){assert(0 <= u && u < n);assert(0 <= v && v < n);if (is_done_par_rdist_init == false) par_rdist_init();return rdist[u] + rdist[v] - rdist[lca(u,v)] * 2LL;}vector<int> path(int f, int t){assert(0 <= f && f < n);assert(0 <= t && t < n);int v = lca(f,t);vector<int> fp = {f};vector<int> tp = {t};int fn = f, tn = t;while (fn != v){fn = parent(fn);fp.emplace_back(fn);}while (tn != v){tn = parent(tn);tp.emplace_back(tn);}for (int i = int(tp.size()) - 2; i >= 0; i--){fp.emplace_back(tp[i]);}return fp;}vector<long long> alldists(int v){assert(0 <= v && v < n);if (v == 0) return rdist;vector<long long> dists(n,1e18);vector<int> vis(n,0);dists[v] = 0LL;queue<int> que;que.push(v);while (!que.empty()){int p = que.front(); que.pop();vis[p]++;for (edge x : vs[p].adj){if (vis[x.to] == 0){dists[x.to] = dists[p] + x.cost;que.push(x.to);}}}return dists;}vector<int> dfs(int v){assert(0 <= v && v < n);vector<int> ans;vector<int> vis(n,0);_dfs(v,vis,ans);return ans;}vector<vertex> vs;private:int n;int root;bool is_done_lca_init;bool is_done_par_rdist_init;vector<int> par;vector<int> dep;vector<int> sub;vector<long long> rdist;vector<vector<int>> par2;void initialize(){is_done_lca_init = false;is_done_par_rdist_init = false;vs.resize(n);dep.resize(n,-1);sub.resize(n,0);}void lca_init(){par2.resize(30,vector<int>(n,-1));for (int i = 0; i < n; i++) par2[0][i] = parent(i);for (int i = 0; i < 29 ; i++) {for (int j = 0; j < n; j++) {if (par2[i][j] < 0) par2[i+1][j] = -1;else par2[i+1][j] = par2[i][par2[i][j]];}}is_done_lca_init = true;}void par_rdist_init(){par.resize(n,-2);rdist.resize(n,-1);par[root] = -1;rdist[root] = 0;queue<int> que;que.push(root);while (!que.empty()){int p = que.front(); que.pop();for (edge x : vs[p].adj){if (par[x.to] == -2){par[x.to] = p;rdist[x.to] = rdist[p] + x.cost;que.push(x.to);}}}is_done_par_rdist_init = true;}void _dfs(int v, vector<int> &vis, vector<int> &ans){vis[v]++;for (edge x : vs[v].adj){if (vis[x.to] == 0) _dfs(x.to,vis,ans);}ans.emplace_back(v);}};template<typename T> struct doubling{vector<T> vec;doubling (vector<T> _vec) : vec(_vec) {}map<T,ll> mp;ll length_of_loop = -1;ll top_of_loop = -1;void init(){ll ind = 0;for (T x : vec){if (mp.find(x) == mp.end()) mp[x] = ind, ind++;else {length_of_loop = ind - mp[x];top_of_loop = mp[x];break;}}}ll len(){if (length_of_loop == -1) init();return length_of_loop;}ll top(){if (top_of_loop == -1) init();return top_of_loop;}T get(ll n){assert(0 <= n);if (n < top()) return vec[n];ll d = n - top();return vec[top() + (d % len())];}};struct Mo{vector<int> left, right, order, v;int width, nl, nr, ptr;Mo (int n = 0) : width(sqrt(n)), nl(0), nr(0), ptr(0), left(0), right(0), v(n,-1) {}void insert(int l, int r){ // [l,r)left.emplace_back(l);right.emplace_back(r);}void build(){ // sort all queryorder.resize(left.size());iota(order.begin(),order.end(),0);sort(order.begin(),order.end(),[&](int a, int b){if(left[a] / width != left[b] / width) return left[a] < left[b];return right[a] < right[b];});}int process(){ // do 1 queryif (ptr == int(order.size())) return -1;const int id = order[ptr];while (nl > left[id]) distribute(--nl);while (nl < left[id]) distribute(nl++);while (nr > right[id]) distribute(--nr);while (nr < right[id]) distribute(nr++);return order[ptr++];}inline void distribute(int idx){ // x x x (nl) o o o (nr) x x ...v[idx] *= -1;if (v[idx] == 1) add(idx);else del(idx);}void add(int idx);void del(int idx);};template<typename T> struct Matrix{int rows;int cols;vector<vector<T>> m;Matrix (int h = 0, int w = 0, T init = T(0)) : m(h,vector<T>(w,init)), rows(h), cols(w){}Matrix (vector<vector<T>> _init) : m(_init), rows(_init.size()), cols(_init.at(0).size()){}vector<T> operator[](const int i) const {return m[i];}vector<T>& operator[](const int i) {return m[i];}Matrix &operator+= (const Matrix &r){assert(this->rows == r.rows && this->cols == r.cols);for (int i = 0; i < r.rows; ++i){for (int j = 0; j < r.cols; ++j){m[i][j] += r.m[i][j];}}return *this;}Matrix &operator-= (const Matrix &r){assert(this->rows == r.rows && this->cols == r.cols);for (int i = 0; i < r.rows; ++i){for (int j = 0; j < r.cols; ++j){m[i][j] -= r.m[i][j];}}return *this;}Matrix &operator*= (const Matrix &r){assert(this->cols == r.rows);Matrix res(rows, r.cols);for (int i = 0; i < rows; ++i){for (int j = 0; j < r.cols; ++j){for (int k = 0; k < r.rows; ++k){res[i][j] += m[i][k] * r.m[k][j];}}}return *this = res;}Matrix operator+ (const Matrix &r) const {return Matrix(*this) += r;}Matrix operator- (const Matrix &r) const {return Matrix(*this) -= r;}Matrix operator* (const Matrix &r) const {return Matrix(*this) *= r;}bool operator== (const Matrix &r){if (rows != r.rows || cols != r.cols) return false;for (int i = 0; i < r.rows; ++i){for (int j = 0; j < r.cols; ++j){if (m[i][j] != r.m[i][j]) return false;}}return true;}Matrix& operator+=(const T &r){for (int i = 0; i < rows; ++i){for (int j = 0; j < cols; ++j){m[i][j] += r;}}return *this;}Matrix& operator-=(const T &r){for (int i = 0; i < rows; ++i){for (int j = 0; j < cols; ++j){m[i][j] -= r;}}return *this;}Matrix& operator*=(const T &r){for (int i = 0; i < rows; ++i){for (int j = 0; j < cols; ++j){m[i][j] *= r;}}return *this;}Matrix& operator/=(const T &r){for (int i = 0; i < rows; ++i){for (int j = 0; j < cols; ++j){m[i][j] /= r;}}return *this;}Matrix operator+ (const T &r) const {return Matrix(*this) += r;}Matrix operator- (const T &r) const {return Matrix(*this) -= r;}Matrix operator* (const T &r) const {return Matrix(*this) *= r;}Matrix operator/ (const T &r) const {return Matrix(*this) /= r;}Matrix e(){assert(this->rows == this->cols);Matrix res(this->rows, this->rows);for (int i = 0; i < rows; ++i) res[i][i] = 1;return res;}Matrix matpow(ll n){assert(this->rows == this->cols);if (n == 0) return e();Matrix f = matpow(n / 2);Matrix ans = f * f;if (n % 2 == 1) ans *= *this;return ans;}// for T = int, long long, double, long doublevoid show(){for (int i = 0; i < rows; ++i){for (int j = 0; j < cols; ++j){cout << m[i][j] << (j+1 == this->cols ? "\n" : " ");}}}};template<class S, S op(S l, S r), S e()> struct Rui{/*- op(e,x) = op(x,e) = x- op(l,opinv(l,lr)) = lr*/int n;vector<S> vec, lrui, rrui;Rui (vector<S> _vec) : n(int(_vec.size())), vec(_vec) {lrui.resize(n+1), rrui.resize(n+1);lrui[0] = rrui[n] = e();for (int i = 0; i < n; i++) lrui[i+1] = op(lrui[i],vec[i]);for (int i = n; i > 0; i--) rrui[i-1] = op(rrui[i],vec[i-1]);}template<S opinv(S l, S lr)> S prod(int l, int r = -1){ // [l,r)if (r == -1) return vec[l];return opinv(lrui[l],lrui[r]);}S nprod(int l, int r = -1){ // [0,l) * [r,n)if (r == -1) r = l+1;return op(lrui[l],rrui[r]);}};struct MINT998244353{using mint = modint998244353;vector<mint> kaijo, kainv;int N;MINT998244353 (int lim = 200000) : N(lim), kaijo(lim+1,1), kainv(lim+1,1) {rep(i,N) kaijo[i+1] = kaijo[i] * (i+1);rep(i,N) kainv[i+1] = kainv[i] / (i+1);}mint factrial(int x){return kaijo[x];}mint inv_factorial(int x){return kainv[x];}mint ncr(int n, int r){return kaijo[n] * kainv[r] * kainv[n-r];}template<typename T> vector<mint> beki(T r, int n = -1){if (n == -1) n = N;vector<mint> res(n+1,1);rep(i,n) res[i+1] = res[i] * mint(r);return res;}vector<mint> vec_inv(vector<mint> &a){vector<mint> res(a.size());rep(i,int(a.size())) res[i] = a[i].inv();return res;}};struct MINT1000000007{using mint = modint1000000007;vector<mint> kaijo, kainv;int N;MINT1000000007 (int lim = 200000) : N(lim), kaijo(lim+1,1), kainv(lim+1,1) {rep(i,N) kaijo[i+1] = kaijo[i] * (i+1);rep(i,N) kainv[i+1] = kainv[i] / (i+1);}mint factrial(int x){return kaijo[x];}mint inv_factorial(int x){return kainv[x];}mint ncr(int n, int r){if (n < r) return mint(0);return kaijo[n] * kainv[r] * kainv[n-r];}template<typename T> vector<mint> beki(T r, int n = -1){if (n == -1) n = N;vector<mint> res(n+1,1);rep(i,n) res[i+1] = res[i] * mint(r);return res;}vector<mint> vec_inv(vector<mint> &a){vector<mint> res(a.size());rep(i,int(a.size())) res[i] = a[i].inv();return res;}};ll op(ll a, ll b){if (a == -1) return b;if (b == -1) return a;return gcd(a,b);}ll e(){return -1;}ll opinv(int a, int ab){return ab - a;}template<typename T> void vmint(vector<T> &v){int n = v.size();if (n == 0) {cout << endl;return ;}rep(i,n) cout << v[i].val() << (i < n-1 ? " " : "\n");}template<typename T> void vvmint(vector<vector<T>> &v){int n = v.size();if (n == 0) {cout << endl;return ;}rep(i,n) vmint(v[i]);}#include<random>random_device rd;mt19937_64 mt(rd());void shf(vector<int> &a){int n = a.size();rep(i,n){int j = i + (mt() % (n - i));swap(a[i],a[j]);}}void solve(){int n; cin >> n;ll m; cin >> m;map<ll,int> mp;rep(i,n){ll x; cin >> x;mp[x%m]++;}int ans = 0;set<ll> st;for (auto p : mp){ll x = p.first;int cnt = p.second;if (st.find(x) != st.end()) continue;if ((x + x) % m == 0){ans++;continue;}ans += max(cnt,mp[m-x]);st.insert(x), st.insert(m-x);}o(ans);}int main(){fast_io();int t = 1; //cin >> t;while (t--) solve();}