結果
問題 | No.2755 行列の共役類 |
ユーザー |
|
提出日時 | 2024-05-10 23:19:52 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,986 bytes |
コンパイル時間 | 3,078 ms |
コンパイル使用メモリ | 257,432 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 07:36:56 |
合計ジャッジ時間 | 8,866 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 59 WA * 7 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> // #include <x86intrin.h> using namespace std; #if __cplusplus >= 202002L using namespace numbers; #endif template<bool Enable_small_to_large = true> struct disjoint_set{ int n, _group_count; vector<int> p; vector<list<int>> group; disjoint_set(){ } disjoint_set(int n): n(n), _group_count(n), p(n, -1), group(n){ assert(n >= 0); for(auto i = 0; i < n; ++ i) group[i] = {i}; } int make_set(){ p.push_back(-1); group.push_back(list<int>{n}); ++ _group_count; return n ++; } int root(int u){ return p[u] < 0 ? u : p[u] = root(p[u]); } bool share(int a, int b){ return root(a) == root(b); } int size(int u){ return -p[root(u)]; } bool merge(int u, int v){ u = root(u), v = root(v); if(u == v) return false; -- _group_count; if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v); p[u] += p[v], p[v] = u; group[u].splice(group[u].end(), group[v]); return true; } bool merge(int u, int v, auto act){ u = root(u), v = root(v); if(u == v) return false; -- _group_count; bool swapped = false; if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true; act(u, v, swapped); p[u] += p[v], p[v] = u; group[u].splice(group[u].end(), group[v]); return true; } int group_count() const{ return _group_count; } const list<int> &group_of(int u){ return group[root(u)]; } vector<vector<int>> group_up(){ vector<vector<int>> g(n); for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i); g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end()); return g; } void clear(){ _group_count = n; fill(p.begin(), p.end(), -1); for(auto i = 0; i < n; ++ i) group[i] = {i}; } friend ostream &operator<<(ostream &out, disjoint_set dsu){ auto gs = dsu.group_up(); out << "{"; if(!gs.empty()) for(auto i = 0; i < (int)gs.size(); ++ i){ out << "{"; for(auto j = 0; j < (int)gs[i].size(); ++ j){ out << gs[i][j]; if(j + 1 < (int)gs[i].size()) out << ", "; } out << "}"; if(i + 1 < (int)gs.size()) out << ", "; } return out << "}"; } }; // DEBUG BEGIN #ifdef LOCAL // DECLARATION BEGIN template<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p); template<class Tuple, size_t N> struct _tuple_printer; template<class... Args> ostream &_print_tuple(ostream &out, const tuple<Args...> &t); template<class ...Args> ostream &operator<<(ostream &out, const tuple<Args...> &t); template<class T> ostream &operator<<(typename enable_if<!is_same<T, string>::value, ostream>::type &out, const T &arr); ostream &operator<<(ostream &out, const _Bit_reference &bit); template<size_t SZ> ostream &operator<<(ostream &out, const bitset<SZ> &b); template<class T, class A, class C> ostream &operator<<(ostream &out, priority_queue<T, A, C> pq); // DECLARATION END template<class L, class R> ostream &operator<<(ostream &out, const pair<L, R> &p){ return out << "{" << p.first << ", " << p.second << "}"; } template<class Tuple, size_t N> struct _tuple_printer{ static ostream &_print(ostream &out, const Tuple &t){ return _tuple_printer<Tuple, N-1>::_print(out, t) << ", " << get<N-1>(t); } }; template<class Tuple> struct _tuple_printer<Tuple, 1>{ static ostream &_print(ostream &out, const Tuple& t){ return out << get<0>(t); } }; template<class... Args> ostream &_print_tuple(ostream &out, const tuple<Args...> &t){ return _tuple_printer<decltype(t), sizeof...(Args)>::_print(out << "{", t) << "}"; } template<class ...Args> ostream &operator<<(ostream &out, const tuple<Args...> &t){ return _print_tuple(out, t); } template<class T> ostream &operator<<(typename enable_if<!is_same<T, string>::value, ostream>::type &out, const T &arr){ if(arr.empty()) return out << "{}"; out << "{"; for(auto it = arr.begin(); it != arr.end(); ++ it){ out << *it; next(it) != arr.end() ? out << ", " : out << "}"; } return out; } ostream &operator<<(ostream &out, const _Bit_reference &bit){ return out << bool(bit); } template<size_t SZ> ostream &operator<<(ostream &out, const bitset<SZ> &b){ for(auto i = 0; i < SZ; ++ i) out << b[i]; return out; } template<class T, class A, class C> ostream &operator<<(ostream &out, priority_queue<T, A, C> pq){ vector<T> a; while(!pq.empty()) a.push_back(pq.top()), pq.pop(); return out << a; } template<class Head> void debug_out(Head H){ cerr << H << endl; } template<class Head, class... Tail> void debug_out(Head H, Tail... T){ cerr << H << ", ", debug_out(T...); } void debug2_out(){ } template<class Head, class... Tail> void debug2_out(Head H, Tail... T){ cerr << "\n"; for(auto x: H) cerr << x << ",\n"; debug2_out(T...); } template<class Width, class Head> void debugbin_out(Width w, Head H){ for(auto rep = w; rep; -- rep, H >>= 1) cerr << (H & 1); cerr << endl; } template<class Width, class Head, class... Tail> void debugbin_out(Width w, Head H, Tail... T){ for(auto rep = w; rep; -- rep, H >>= 1) cerr << (H & 1); cerr << ", "; debugbin_out(w, T...); } enum CODE{ CCRED = 31, CCGREEN = 32, CCYELLOW = 33, CCBLUE = 34, CCDEFAULT = 39 }; #define debug_endl() cerr << endl #define debug(...) cerr << "\033[" << (int)CODE(CCRED) << "mL" << setw(3) << std::left << __LINE__ << std::right << " [" << #__VA_ARGS__ << "] \033[" << (int)CODE(CCBLUE) << "m", debug_out(__VA_ARGS__), cerr << "\33[" << (int)CODE(CCDEFAULT) << "m" #define debug2(...) cerr << "\033[" << (int)CODE(CCRED) << "mL" << setw(3) << std::left << __LINE__ << std::right << " [" << #__VA_ARGS__ << "] \033[" << (int)CODE(CCBLUE) << "m", debug2_out(__VA_ARGS__), cerr << "\33[" << (int)CODE(CCDEFAULT) << "m" #define debugbin(...) cerr << "\033[" << (int)CODE(CCRED) << "mL" << setw(3) << std::left << __LINE__ << std::right << " [" << #__VA_ARGS__ << "] \033[" << (int)CODE(CCBLUE) << "m", debugbin_out(__VA_ARGS__), cerr << "\33[" << (int)CODE(CCDEFAULT) << "m" #else #define debug_endl() 42 #define debug(...) 42 #define debug2(...) 42 #define debugbin(...) 42 #endif // DEBUG END int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int B, C; cin >> B >> C, C = B / C; vector<vector<int>> g(C + 1, vector<int>(C + 1)); for(auto x = 0; x <= C; ++ x){ for(auto y = 0; y <= C; ++ y){ g[x][y] = gcd(x, y); } } int res = 0; disjoint_set dsu(C); for(auto a = 1; a <= B; ++ a){ if(gcd(a, B) != 1){ continue; } dsu.clear(); for(auto b = 0; b < C; ++ b){ for(auto d = b + 1; d < C; ++ d){ if(d % g[(a - 1) % C][g[b][C]] == 0 && b % g[d][g[(a - 1) % C][C]] == 0){ dsu.merge(b, d); } } } debug(a); debug2(dsu.group_up()); res += dsu.group_count(); } if(res >= 100){ cout << "100+\n"; } else{ cout << res << "\n"; } return 0; } /* a b*C c d*C 0 1 0 1 0<=a<B, 0<=b<B/C (a,b)*(c*d) = (a*c, a*d+b) = (1, 0) c=invB(a) d=-b*invC(a) (a*x, a*y+b) = (c*x, d*x+y) for some x, y (gcd(x, B) = 1) a=c d*x + (1-a)*y - b = 0 mod C has a solution */