結果

問題 No.2388 At Least K-Characters
ユーザー polylogK
提出日時 2023-08-08 22:28:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 111 ms / 4,000 ms
コード長 4,585 bytes
コンパイル時間 2,140 ms
コンパイル使用メモリ 197,252 KB
最終ジャッジ日時 2025-02-16 00:11:20
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
000.cpp: In function ‘int main()’:
000.cpp:61:9: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘cplib::modint<998244353>::u64’ {aka ‘long unsigned int’} [-Wformat=]
000.cpp:24:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]

ソースコード

diff #
プレゼンテーションモードにする

#line 1 "000.cpp"
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;
#if defined(DONLINE_JUDGE)
    #define NDEBUG
#elif defined(ONLINE_JUDGE)
    #define NDEBUG
#endif
template<typename T> std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T, typename... Ts> auto make_v(size_t a, Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
#line 1 "/home/ecasdqina/cpcpp/libs/library_cpp/math/modint.hpp"
#line 5 "/home/ecasdqina/cpcpp/libs/library_cpp/math/modint.hpp"
namespace cplib {
template <std::uint_fast64_t Modulus>
class modint {
    using u32 = std::uint_fast32_t;
    using u64 = std::uint_fast64_t;
    using i32 = std::int_fast32_t;
    using i64 = std::int_fast64_t;
    inline u64 apply(i64 x) { return (x < 0 ? x + Modulus : x); };
public:
    u64 a;
    static constexpr u64 mod = Modulus;
    constexpr modint(const i64& x = 0) noexcept: a(apply(x % (i64)Modulus)) {}
    constexpr modint operator+(const modint& rhs) const noexcept { return modint(*this) += rhs; }
    constexpr modint operator-(const modint& rhs) const noexcept { return modint(*this) -= rhs; }
    constexpr modint operator*(const modint& rhs) const noexcept { return modint(*this) *= rhs; }
    constexpr modint operator/(const modint& rhs) const noexcept { return modint(*this) /= rhs; }
    constexpr modint operator^(const u64& k) const noexcept { return modint(*this) ^= k; }
    constexpr modint operator^(const modint& k) const noexcept { return modint(*this) ^= k.value(); }
    constexpr modint operator-() const noexcept { return modint(Modulus - a); }
    constexpr modint operator++() noexcept { return (*this) = modint(*this) + 1; }
    constexpr modint operator--() noexcept { return (*this) = modint(*this) - 1; }
    const bool operator==(const modint& rhs) const noexcept { return a == rhs.a; };
    const bool operator!=(const modint& rhs) const noexcept { return a != rhs.a; };
    const bool operator<=(const modint& rhs) const noexcept { return a <= rhs.a; };
    const bool operator>=(const modint& rhs) const noexcept { return a >= rhs.a; };
    const bool operator<(const modint& rhs) const noexcept { return a < rhs.a; };
    const bool operator>(const modint& rhs) const noexcept { return a > rhs.a; };
    constexpr modint& operator+=(const modint& rhs) noexcept {
        a += rhs.a;
        if (a >= Modulus) a -= Modulus;
        return *this;
    }
    constexpr modint& operator-=(const modint& rhs) noexcept {
        if (a < rhs.a) a += Modulus;
        a -= rhs.a;
        return *this;
    }
    constexpr modint& operator*=(const modint& rhs) noexcept {
        a = a * rhs.a % Modulus;
        return *this;
    }
    constexpr modint& operator/=(modint rhs) noexcept {
        u64 exp = Modulus - 2;
        while (exp) {
            if (exp % 2) (*this) *= rhs;
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
    constexpr modint& operator^=(u64 k) noexcept {
        auto b = modint(1);
        while(k) {
            if(k & 1) b = b * (*this);
            (*this) *= (*this);
            k >>= 1;
        }
        return (*this) = b;
    }
    constexpr modint& operator=(const modint& rhs) noexcept {
        a = rhs.a;
        return (*this);
    }
    const modint inverse() const {
        return modint(1) / *this;
    }
    const modint power(i64 k) const {
        if(k < 0) return modint(*this).inverse() ^ (-k);
        return modint(*this) ^ k;
    }
    explicit operator bool() const { return a; }
    explicit operator u64() const { return a; }
    constexpr u64& value() noexcept { return a; }
    constexpr const u64& value() const noexcept { return a; }
    friend std::ostream& operator<<(std::ostream& os, const modint& p) {
        return os << p.a;
    }
    friend std::istream& operator>>(std::istream& is, modint& p) {
        u64 t;
        is >> t;
        p = modint(t);
        return is;
    }
};
}
#line 21 "000.cpp"
using mint = cplib::modint<998244353>;
int main() {
    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    std::string s; std::cin >> s;
    constexpr int sigma = 26;
    if (n < m) s.resize(m, 'a');
    mint ans = 0;
    int count = 0;
    std::vector<int> used(sigma);
    std::vector<mint> dp(sigma + 1);
    for (int i = 0; i < m; ++i) {
        const int ord = s[i] - 'a';
        std::vector<mint> nx(dp.size());
        for (int j = 0; j <= sigma; ++j) nx[j] += dp[j] * j;
        for (int j = 0; j < sigma; ++j) nx[j + 1] += dp[j] * (sigma - j);
        // new
        for (int j = 0; j < ord; ++j) {
            const int nc = (used[j] ? count : count + 1);
            nx[nc] += 1;
        }
        nx.swap(dp);
        if (!used[ord]) {
            ++used[ord];
            ++count;
        }
        if (count >= k and i < n - 1) ++ans;
        ans += std::accumulate(dp.begin() + k, dp.end(), mint(0));
    }
    printf("%lld\n", ans.value());
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0