#570982 (C++14) No.1195 数え上げを愛したい（文字列編）

提出ソース

結果

問題	No.1195 数え上げを愛したい（文字列編）
ユーザー	🍮かんプリン
提出日時	2020-10-24 00:57:59
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	576 ms / 3,000 ms
コード長	11,837 bytes
コンパイル時間	1,929 ms
コンパイル使用メモリ	192,584 KB
実行使用メモリ	23,084 KB
最終ジャッジ日時	2024-07-21 14:36:03
合計ジャッジ時間	11,685 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	562 ms 22,984 KB
testcase_01	AC	568 ms 22,900 KB
testcase_02	AC	576 ms 23,032 KB
testcase_03	AC	110 ms 12,520 KB
testcase_04	AC	117 ms 13,204 KB
testcase_05	AC	114 ms 21,020 KB
testcase_06	AC	52 ms 7,936 KB
testcase_07	AC	52 ms 7,888 KB
testcase_08	AC	135 ms 10,160 KB
testcase_09	AC	531 ms 22,856 KB
testcase_10	AC	324 ms 15,656 KB
testcase_11	AC	510 ms 22,700 KB
testcase_12	AC	489 ms 22,708 KB
testcase_13	AC	423 ms 16,008 KB
testcase_14	AC	290 ms 16,424 KB
testcase_15	AC	324 ms 15,652 KB
testcase_16	AC	300 ms 15,388 KB
testcase_17	AC	145 ms 10,080 KB
testcase_18	AC	487 ms 22,720 KB
testcase_19	AC	507 ms 22,488 KB
testcase_20	AC	413 ms 16,284 KB
testcase_21	AC	509 ms 23,084 KB
testcase_22	AC	392 ms 15,900 KB
testcase_23	AC	52 ms 7,936 KB
testcase_24	AC	52 ms 7,852 KB
testcase_25	AC	54 ms 7,936 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.10.24 00:57:54
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

template< int MOD >
struct mint {
public:
    long long x;
    mint(long long x = 0) :x((x%MOD+MOD)%MOD) {}
    mint(std::string &s) {
        long long z = 0;
        for (int i = 0; i < s.size(); i++) {
            z *= 10;
            z += s[i] - '0';
            z %= MOD;
        }
        this->x = z;
    }
    mint& operator+=(const mint &a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint &a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint &a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint& operator/=(const mint &a) {
        long long n = MOD - 2;
        mint u = 1, b = a;
        while (n > 0) {
            if (n & 1) {
                u *= b;
            }
            b *= b;
            n >>= 1;
        }
        return *this *= u;
    }
    mint operator+(const mint &a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-() const {return mint() -= *this; }
    mint operator-(const mint &a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint &a) const {
        mint res(*this);
        return res *= a;
    }
    mint operator/(const mint &a) const {
        mint res(*this);
        return res /= a;
    }
    friend std::ostream& operator<<(std::ostream &os, const mint &n) {
        return os << n.x;
    }
    friend std::istream &operator>>(std::istream &is, mint &n) {
        long long x;
        is >> x;
        n = mint(x);
        return is;
    }
    bool operator==(const mint &a) const {
        return this->x == a.x;
    }
    bool operator!=(const mint &a) const {
        return this->x != a.x;
    }
    mint pow(long long k) const {
        mint ret = 1;
        mint p = this->x;
        while (k > 0) {
            if (k & 1) {
                ret *= p;
            }
            p *= p;
            k >>= 1;
        }
        return ret;
    }
};
constexpr int MOD = 998244353;




template < const int MOD , bool any = false>
struct FormalPowerSeries {
private:
    using P = FormalPowerSeries< MOD, any >;
    template < class T, class F = multiplies< T > >
    T power(T a, long long n, F op = multiplies< T >(), T e = {1}) const {
        assert(n >= 0);
        T res = e;
        while (n) {
            if (n & 1) res = op(res, a);
            if (n >>= 1) a = op(a, a);
        }
        return res;
    }
    template< int _MOD >
    void ntt(vector< mint < _MOD > >& a, bool inverse) {
        static vector< mint< _MOD > > dw(30), idw(30);
        if (dw[0] == 0) {
            mint< _MOD > root = 2;
            while (power(root, (_MOD - 1) / 2) == 1) root += 1;
            for (int i = 0; i < 30; i++) dw[i] = -power(root, (_MOD - 1) >> (i + 2)), idw[i] = mint<_MOD>(1) / dw[i];
        }
        int n = a.size();
        assert((n & (n - 1)) == 0);
        if (not inverse) {
            for (int m = n; m >>= 1;) {
                mint< _MOD > w = 1;
                for (int s = 0, k = 0; s < n; s += 2 * m) {
                    for (int i = s, j = s + m; i < s + m; i++, j++) {
                        auto x = a[i], y = a[j] * w;
                        if (x.x >= _MOD) x.x -= _MOD;
                        a[i].x = x.x + y.x, a[j].x = x.x + (_MOD - y.x);
                    }
                    w *= dw[__builtin_ctz(++k)];
                }
            }
        } else {
            for (int m = 1; m < n; m *= 2) {
                mint< _MOD > w = 1;
                for (int s = 0, k = 0; s < n; s += 2 * m) {
                    for (int i = s, j = s + m; i < s + m; i++, j++) {
                        auto x = a[i], y = a[j];
                        a[i] = x + y, a[j].x = x.x + (_MOD - y.x), a[j] *= w;
                    }
                    w *= idw[__builtin_ctz(++k)];
                }
            }
        }
        auto c = mint<_MOD>(1) / mint< _MOD >(inverse ? n : 1);
        for (auto&& e : a) e *= c;
    }
    template< int _MOD >
    vector< mint< _MOD > > convolution(vector< mint< _MOD > > l, vector< mint< _MOD > > r) {
        if (l.empty() || r.empty()) return {};
        int n = l.size(), m = r.size(), sz = 1 << __lg(2 * (n + m - 1) - 1);
        if (min(n, m) < 30) {
            vector< long long > res(n + m - 1);
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++) res[i + j] += (l[i] * r[j]).x;
            return {begin(res), end(res)};
        }
        bool eq = l == r;
        l.resize(sz), ntt(l, false);
        if (eq) r = l;
        else r.resize(sz), ntt(r, false);
        for (int i = 0; i < sz; i++) l[i] *= r[i];
        ntt(l, true), l.resize(n + m - 1);
        return l;
    }
    P pre(const P &p, int sz) const {
        P ret;
        ret.a = vector<mint<MOD>>(p.a.begin(), p.a.begin() + min((int)p.a.size(), sz));
        return ret;
    }
public:
    vector<mint<MOD>> a;
    FormalPowerSeries(int sz = 0) {
        this->a.resize(sz, 0);
    }
    
    P resize(int k) const {
        return pre(*this,k);
    }
    FormalPowerSeries(std::initializer_list<mint<MOD>> v) {
        this->a = v;
    }
    
    size_t size() const { return this->a.size(); }
    bool operator<(const P& r) const { return this->a.size() < r.a.size(); }
    bool operator>(const P& r) const { return this->a.size() > r.a.size(); }
    P operator+(const P &a) const { return P(*this) += a; }
    P operator+(const long long a) const { return P(*this) += a; }
    P operator-(const P &a) const { return P(*this) -= a; }
    P operator*(const P &a) const { return P(*this) *= a; }
    P operator*(const long long a) const { return P(*this) *= a; }
    P operator/(const P &a) const { return P(*this) /= a; }
    P &operator+=(const P &r) {
        this->a.resize(max(this->a.size(),r.size()));
        for(int i = 0; i < (int)r.size(); i++) this->a[i] += r.a[i];
        return *this;
    }
    
    P &operator+=(const long long v) {
        if (this->a.size() == 0) this->a.resize(1,(v % MOD + MOD) % MOD);
        else this->a[0] += v;
        return *this;
    }
    P &operator-=(const P &r) {
        this->a.resize(max(this->a.size(),r.size()));
        for(int i = 0; i < (int)r.size(); i++) this->a[i] -= r.a[i];
        return *this;
    }
    P &operator*=(const P &b) {
        if (!any) {
            this->a = convolution(this->a, b.a);
            return *this;
        }
        else {
            if (this->a.empty() || b.a.empty()) {
                this->a.clear();
                return *this;
            }
            int n = this->a.size(), m = b.a.size();
            static constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617;
            using Mint0 = mint< mod0 >;
            using Mint1 = mint< mod1 >;
            using Mint2 = mint< mod2 >;
            vector< Mint0 > l0(n), r0(m);
            vector< Mint1 > l1(n), r1(m);
            vector< Mint2 > l2(n), r2(m);
            for (int i = 0; i < n; i++) l0[i] = this->a[i].x, l1[i] = this->a[i].x, l2[i] = this->a[i].x;
            for (int j = 0; j < m; j++) r0[j] = b.a[j].x, r1[j] = b.a[j].x, r2[j] = b.a[j].x;
            l0 = convolution(l0,r0);
            l1 = convolution(l1,r1);
            l2 = convolution(l2,r2);
            this->a.resize(n + m - 1);
            static const Mint1 im0 = Mint1(1) / Mint1(mod0);
            static const Mint2 im1 = Mint2(1) / Mint2(mod1), im0m1 = im1 / mod0;
            static const mint<MOD> m0 = mod0, m0m1 = m0 * mod1;
            for (int i = 0; i < n + m - 1; i++) {
                int y0 = l0[i].x;
                int y1 = (im0 * (l1[i] - y0)).x;
                int y2 = (im0m1 * (l2[i] - y0) - im1 * y1).x;
                this->a[i] = m0m1 * y2 + y0 + m0 * y1;
            }
            return *this;
        }
    }
    P &operator*=(const long long v) {
        for (int i = 0; i < this->a.size(); i++) this->a[i] *= v;
        return *this;
    }
    
    P &operator/=(const P &a) {
        *this *= a.inverse();
        return *this;
    }
    
    P inverse(int deg = -1) const {
        assert(this->a.size() != 0 && this->a[0].x != 0);
        const int n = (int)this->a.size();
        if(deg == -1) deg = n;
        P ret(1);
        ret[0] = mint<MOD>(1) / a[0];
        for(int i = 1; i < deg; i <<= 1) {
            ret = pre((ret + ret - ret * ret * pre(*this,i << 1)),i << 1);
        }
        return pre(ret,deg);
    }
    
    P differential() const {
        const int n = (int) this->a.size();
        P ret(max(0, n - 1));
        for(int i = 1; i < n; i++) ret[i-1] = this->a[i] * i;
        return ret;
    }
    
    P integral() const {
        const int n = (int) this->a.size();
        P ret(n + 1);
        for(int i = 0; i < n; i++) ret[i + 1] = this->a[i] / (i + 1);
        return ret;
    }
    
    P log(int deg = -1) const {
        assert(this->a.size() != 0 && this->a[0] == 1);
        const int n = (int)this->a.size();
        if(deg == -1) deg = n;
        return pre((this->differential() * this->inverse(deg)),deg - 1).integral();
    }
    
    P exp(int deg = -1) const {
        if (this->a.size() == 0) return P(0);
        assert(this->a[0] == 0);
        const int n = (int)this->a.size();
        if(deg == -1) deg = n;
        P ret(1);
        ret.a[0] = 1;
        for(int i = 1; i < deg; i <<= 1) {
            ret = pre((ret * (pre(*this,i << 1) + 1 - ret.log(i << 1))),i << 1);
        }
        return pre(ret,deg);
    }
    
    P pow(long long k, int deg = -1) const {
        const int n = (int) this->a.size();
        if(deg == -1) deg = n;
        for(int i = 0; i < n; i++) {
            if(this->a[i].x != 0) {
                long long rev = (mint<MOD>(1) / this->a[i]).x;
                P C = *this * rev;
                P D(n - i);
                for(int j = i; j < n; j++) D[j - i] = C[j];
                D = (D.log() * k).exp() * power(this->a[i], k).x;
                P E(deg);
                if(i * k > deg) return E;
                auto S = i * k;
                for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j];
                return E;
            }
        }
        return *this;
    }
    mint< MOD > &operator[](int x) {
        assert(0 <= x && x < (int)this->a.size());
        return a[x];
    }
    friend std::ostream &operator<<(std::ostream &os, const P &p) {
        os << "[ ";
        for (int i = 0; i < p.size(); ++i) {
            os << p.a[i] << " ";
        }
        os << "]";
        return os;
    }
};

template<typename T>
struct Combination {
private:
    int N;
public:
    vector< T > FACT, IFACT;
    
    Combination(int n) : N(n) {
        FACT.resize(n + 1);
        IFACT.resize(n + 1);
        FACT[0] = 1;
        IFACT[0] = 1;
        for (int i = 1; i <= n; i++) {
            FACT[i] = FACT[i - 1] * i;
            IFACT[i] = T(1) / FACT[i];
        }
    }
    T comb(int n, int r) {
        if (n < 0 || r < 0 || r > n) return 0;
        if (r > n / 2) r = n - r;
        return FACT[n] * IFACT[n - r] * IFACT[r];
    }
};
int main() {
    string s;cin >> s;
    vector<int> cnt(26);
    Combination<mint<MOD>> cb(3*100000+1);
    for (int i = 0; i < s.size(); i++) {
        cnt[s[i]-'a']++;
    }
    vector<FormalPowerSeries<MOD>> fps(26);
    FormalPowerSeries<MOD> t({1});
    for (int i = 0; i < 26; i++) {
        fps[i] = FormalPowerSeries<MOD>(cnt[i]+1);
        for (int j = 0; j <= cnt[i]; j++) {
            fps[i][j] = cb.IFACT[j];
        }
        t *= fps[i];
    }
    mint<MOD> ans = 0;
    for (int i = 1; i < t.size(); i++) {
        ans += t[i] * cb.FACT[i];
    }
    cout << ans << endl;
    return 0;
}

yukicoder

結果

テストケース

ソースコード