結果
問題 | No.171 スワップ文字列(Med) |
ユーザー | はまやんはまやん |
提出日時 | 2017-05-26 15:00:07 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,837 bytes |
コンパイル時間 | 2,211 ms |
コンパイル使用メモリ | 193,036 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-19 20:06:34 |
合計ジャッジ時間 | 3,070 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | WA | - |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | AC | 2 ms
6,940 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); } /*--------------------------------------------------------------------------------------------------- ∧_∧ ∧_∧ (´<_` ) Welcome to My Coding Space! ( ´_ゝ`) / ⌒i / \ | | / / ̄ ̄ ̄ ̄/ | __(__ニつ/ _/ .| .|____ \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ string S; //--------------------------------------------------------------------------------------------------- int fac[1010]; int calc(int mod) { int N = S.length(); map<char, int> m; for (char c : S) m[c]++; fac[0] = 1; rep(i, 1, 1010) fac[i] = mul(mod, fac[i - 1], i); if (m.size() == 1) return 1; int res = fac[N]; for (auto p : m) { res = mul(mod, res, modinv(mod, fac[p.second])); } return res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> S; CRT crt; int a; a = calc(3); a = (a - 1 + 3) % 3; crt.add(a, 3); //cout << a << endl; a = calc(191); a = (a - 1 + 191) % 191; crt.add(a, 191); //cout << a << endl; cout << crt.solve(573) << endl; }