結果
問題 | No.1195 数え上げを愛したい(文字列編) |
ユーザー | otera |
提出日時 | 2020-08-25 07:10:42 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 4,709 bytes |
コンパイル時間 | 1,656 ms |
コンパイル使用メモリ | 140,280 KB |
実行使用メモリ | 8,452 KB |
最終ジャッジ日時 | 2024-11-06 11:00:54 |
合計ジャッジ時間 | 8,669 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
ソースコード
/*** author: otera**/#include<iostream>#include<string>#include<cstdio>#include<cstring>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<deque>#include<ciso646>#include<random>#include<map>#include<set>#include<complex>#include<bitset>#include<stack>#include<unordered_map>#include<unordered_set>#include<utility>#include<cassert>using namespace std;//#define int long longtypedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;typedef long double ld;const int inf=1e9+7;const ll INF=1LL<<60 ;const ll mod=1e9+7 ;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef complex<ld> Point;const ld eps = 1e-8;const ld pi = acos(-1.0);typedef pair<int, int> P;typedef pair<ld, ld> LDP;typedef pair<ll, ll> LP;#define fr first#define sc second#define all(c) c.begin(),c.end()#define pb push_back#define debug(x) cerr << #x << " = " << (x) << endl;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}long long modinv(long long a, long long mod) {long long b = mod, u = 1, v = 0;while (b) {long long t = a/b;a -= t*b; swap(a, b);u -= t*v; swap(u, v);}u %= mod;if (u < 0) u += mod;return u;}namespace NTT {const int MOD = 998244353; // to be set appropriatelyconst long long PR = 3; // to be set appropriatelyvoid trans(vector<long long> &v, bool inv = false) {int n = (int)v.size();for (int i = 0, j = 1; j < n-1; j++) {for (int k = n>>1; k > (i ^= k); k >>= 1);if (i > j) swap(v[i], v[j]);}for (int t = 2; t <= n; t <<= 1) {long long bw = modpow(PR, (MOD-1)/t, MOD);if (inv) bw = modinv(bw, MOD);for (int i = 0; i < n; i += t) {long long w = 1;for (int j = 0; j < t/2; ++j) {int j1 = i + j, j2 = i + j + t/2;long long c1 = v[j1], c2 = v[j2] * w % MOD;v[j1] = c1 + c2;v[j2] = c1 - c2 + MOD;while (v[j1] >= MOD) v[j1] -= MOD;while (v[j2] >= MOD) v[j2] -= MOD;w = w * bw % MOD;}}}if (inv) {long long inv_n = modinv(n, MOD);for (int i = 0; i < n; ++i) v[i] = v[i] * inv_n % MOD;}}// C is A*Bvector<long long> mult(vector<long long> A, vector<long long> B) {int size_a = 1; while (size_a < A.size()) size_a <<= 1;int size_b = 1; while (size_b < B.size()) size_b <<= 1;int size_fft = max(size_a, size_b) << 1;vector<long long> cA(size_fft, 0), cB(size_fft, 0), cC(size_fft, 0);for (int i = 0; i < A.size(); ++i) cA[i] = A[i];for (int i = 0; i < B.size(); ++i) cB[i] = B[i];trans(cA); trans(cB);for (int i = 0; i < size_fft; ++i) cC[i] = cA[i] * cB[i] % MOD;trans(cC, true);vector<long long> res((int)A.size() + (int)B.size() - 1);for (int i = 0; i < res.size(); ++i) res[i] = cC[i];while(res.size() and res.back() == 0) res.pop_back();return res;}};ll fact[300300], factr[300300];void solve() {string s; cin >> s;int n = (int)s.size();vector<int> cnt(26, 0);rep(i, n) {cnt[s[i] - 'a'] ++;}vector<ll> a(1, 1LL);sort(all(cnt));rep(i, 5) {vector<ll> b(cnt[i] + 1, 1LL);ll cur = 1LL;rep(j, cnt[i] + 1) {if(j != 0) cur *= modinv(j, NTT::MOD);cur %= NTT::MOD;b[j] = cur;}a = NTT::mult(a, b);}ll cur = 1;ll ans = 0;for(ll k = 1; k <= n; ++ k) {cur *= k;cur %= NTT::MOD;ans += (a[k] * cur) % NTT::MOD;if(ans >= NTT::MOD) ans -= NTT::MOD;}cout << ans << endl;}signed main() {ios::sync_with_stdio(false);cin.tie(0);//cout << fixed << setprecision(10);//int t; cin >> t; rep(i, t)solve();solve();return 0;}