結果
問題 | No.171 スワップ文字列(Med) |
ユーザー | はまやんはまやん |
提出日時 | 2017-05-26 15:35:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 3,841 bytes |
コンパイル時間 | 1,968 ms |
コンパイル使用メモリ | 188,520 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 20:06:48 |
合計ジャッジ時間 | 2,386 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } //--------------------------------------------------------------------------------------------------- typedef long long ll; struct CRT { vector<pair<ll, ll>> v; void add(ll a, ll m) { v.push_back({ a, m }); } // x = a (mod m) set<ll> enumpr(ll n) { set<ll> V; for (ll i = 2; i*i <= n; i++) while (n%i == 0) V.insert(i), n /= i; if (n>1) V.insert(n); return V; } ll ext_gcd(ll p, ll q, ll& x, ll& y) { if (q == 0) return x = 1, y = 0, p; ll g = ext_gcd(q, p%q, y, x); y -= p / q*x; return g; } ll inv(ll p, ll q) { ll xx, yy, g = ext_gcd(p, q, xx, yy); if (xx<0) xx += q, yy -= p; return xx; } ll solve(ll mo = 1000000007) { string s; int N = v.size(); set<ll> P; vector<int> num; rep(i, 0, N) { set<ll> S = enumpr(v[i].second); for(ll r : S) P.insert(r);} num = vector<int>(N, 0); for(ll r : P) { int y = 0; rep(x, 0, N) { num[x] = 1; int j = v[x].second; while (j%r == 0) j /= r, num[x] *= r; if (num[y]<num[x]) y = x; } rep(x, 0, N) if (x != y) { if (v[x].first%num[x] != v[y].first%num[x]) return -1; v[x].second /= num[x]; v[x].first %= v[x].second; } } vector<pair<ll, ll> > V2; rep(x, 0, N) if (v[x].second>1) V2.emplace_back(v[x].second, v[x].first); sort(V2.begin(), V2.end()); v = V2; N = v.size(); rep(y, 0, N) rep(x, 0, y) { ll k = v[y].second - v[x].second; if (k<0) k += v[y].first; v[y].second = k*inv(v[x].first, v[y].first) % v[y].first; } ll ret = 0; for (int x = N - 1; x >= 0; x--) ret = (ret*v[x].first + v[x].second) % mo; return ret; } }; int add(int mod, int x, int y) { return (x += y) >= mod ? x - mod : x; } template<class... T> int add(int mod, int x, T... y) { return add(mod, x, add(mod, y...)); } int mul(int mod, int x, int y) { return 1LL * x * y % mod; } template<class... T> int mul(int mod, int x, T... y) { return mul(mod, x, mul(mod, y...)); } int sub(int mod, int x, int y) { return add(mod, x, mod - y); } int modpow(int mod, int a, long long b) { int ret = 1; while (b > 0) { if (b & 1) ret = 1LL * ret * a % mod; a = 1LL * a * a % mod; b >>= 1; } return ret; } int modinv(int mod, int a) { return modpow(mod, a, mod - 2); } map<int, int> enumpr(int n) { map<int, int> V; for (int i = 2; 1LL*i*i <= n; i++) while (n%i == 0) V[i]++, n /= i; if (n>1) V[n]++; return V; } /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ string S; //--------------------------------------------------------------------------------------------------- void _main() { cin >> S; int N = S.length(); map<char, int> m; for (char c : S) m[c]++; map<int, int> up; rep(i, 2, N + 1) { auto mp = enumpr(i); for (auto p : mp) up[p.first] += p.second; } for (auto p : m) { rep(i, 2, p.second + 1) { auto mp = enumpr(i); for (auto pp : mp) up[pp.first] -= pp.second; } } int ans = 1; for (auto p : up) { rep(i, 0, p.second) ans = (ans * p.first) % 573; } ans = (ans + 572) % 573; cout << ans << endl; }