結果

問題 No.2388 At Least K-Characters
ユーザー soto800
提出日時 2023-07-21 22:18:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,225 ms / 4,000 ms
コード長 5,572 bytes
コンパイル時間 1,878 ms
コンパイル使用メモリ 176,224 KB
実行使用メモリ 242,280 KB
最終ジャッジ日時 2024-07-05 03:48:06
合計ジャッジ時間 28,081 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
 
template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

#define ll lli

template <long long mod>
struct modint {
  modint(ll v = 0) : value(normalize(v)) {}
  ll val() const { return value; }
  void normalize() { value = normalize(value); }
  ll normalize(ll v) {
    if (v <= mod && v >= -mod) {
      if (v < 0) v += mod;
      return v;
    }
    if (v > 0 && v < 2 * mod) {
      v -= mod;
      return v;
    }
    if (v < 0 && v > -2 * mod) {
      v += 2 * mod;
      return v;
    }
    v %= mod;
    if (v < 0) v += mod;
    return v;
  }
  modint<mod>& operator=(ll v) {
    value = normalize(v);
    return *this;
  }
  bool operator==(const modint& o) const { return value == o.val(); }
  bool operator!=(const modint& o) const { return value != o.val(); }
  const modint& operator+() const { return *this; }
  const modint& operator-() const { return value ? mod - value : 0; }
  const modint operator+(const modint& o) const {
    return value + o.val();
  }
  modint& operator+=(const modint& o) {
    value += o.val();
    if (value >= mod) value -= mod;
    return *this;
  }
  const modint operator-(const modint& o) const {
    return value - o.val();
  }
  modint& operator-=(const modint& o) {
    value -= o.val();
    if (value < 0) value += mod;
    return *this;
  }
  const modint operator*(const modint& o) const {
    return (value * o.val()) % mod;
  }
  modint& operator*=(const modint& o) {
    value *= o.val();
    value %= mod;
    return *this;
  }
  const modint operator/(const modint& o) const { return operator*(o.inv()); }
  modint& operator/=(const modint& o) { return operator*=(o.inv()); }
  const modint pow(ll n) const {
    modint ans = 1, x(value);
    while (n > 0) {
      if (n & 1) ans *= x;
      x *= x;
      n >>= 1;
    }
    return ans;
  }
  const modint inv() const {
    ll a = value, b = mod, u = 1, v = 0;
    while (b) {
      ll t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    return u;
  }
  friend ostream& operator<<(ostream& os, const modint& x) {
    return os << x.val();
  }
  template <typename T>
  friend modint operator+(T t, const modint& o) {
    return o + t;
  }
  template <typename T>
  friend modint operator-(T t, const modint& o) {
    return -o + t;
  }
  template <typename T>
  friend modint operator*(T t, const modint& o) {
    return o * t;
  }
  template <typename T>
  friend modint operator/(T t, const modint& o) {
    return o.inv() * t;
  }

 private:
  ll value;
};

using mint = modint<998244353>;
#define MAX 0
#define MIN 1

lli a[500100];
mint dp[2][30][500100];

void solve(){

    lli N,M,K;
    cin>>N>>M>>K;

    string s;
    cin>>s;

    REP(i,0,s.size()){
        a[i] = s[i] - 'a';
    }
    while(s.size() < M){
        s.push_back(0);
    }

    dp[MAX][0][0] = 1;

    set<lli> ss;

    REP(i,0,s.size()+1){
        REP(j,0,27){
            LOG4(i,j,dp[MAX][j][i],dp[MIN][j][i]);
            if(i==s.size())continue;
            //MAX->MAX
            //今までに使った数字かどうかで遷移が変わる
            if(ss.find(a[i]) == ss.end()){//使ってない場合は使用数が増える
                dp[MAX][j+1][i+1] += dp[MAX][j][i];
            }
            else{//使ってる場合は遷移を増やさない
                dp[MAX][j][i+1] += dp[MAX][j][i];
            }

            //MAX->MIN
            //今まで使用しうる数を数える必要がある
            lli usedNum = 0;
            for(auto e:ss){
                if(e < a[i]){
                    usedNum++;
                }
                else{
                    break;
                }
            }
            //使える数は今見ている数字 - 使用している数字
            lli usableNum = a[i] - usedNum;
            LOG2(usedNum,usableNum)
            dp[MIN][j+1][i+1] += usableNum * dp[MAX][j][i];
            dp[MIN][j][i+1] += usedNum * dp[MAX][j][i];


            //MIN -> MIN
            //今まで使ってる数字を当てるか外すかに依存する
            dp[MIN][j+1][i+1] += (26-j)*dp[MIN][j][i];
            dp[MIN][j][i+1] += j*dp[MIN][j][i];
        }
        ss.insert(a[i]);
    }

    mint ans = 0;

    REP(i,0,s.size()+1){
        REP(j,K,30){
            ans += dp[MIN][j][i];
            if(i < N){
                ans+=dp[MAX][j][i];
            }
        }
    }

    cout<<ans<<endl;
}

// Generated by 2.11.0 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){

    lli n=1;
    //cin>>n;
    std::random_device seed_gen;
    std::mt19937 engine(seed_gen());
    while(n--)solve();
    return 0;
}
0