結果
問題 | No.2388 At Least K-Characters |
ユーザー | soto800 |
提出日時 | 2023-07-21 22:18:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,217 ms / 4,000 ms |
コード長 | 5,572 bytes |
コンパイル時間 | 1,895 ms |
コンパイル使用メモリ | 174,072 KB |
実行使用メモリ | 242,128 KB |
最終ジャッジ日時 | 2023-09-18 12:54:47 |
合計ジャッジ時間 | 27,977 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 82 ms
237,832 KB |
testcase_01 | AC | 63 ms
237,812 KB |
testcase_02 | AC | 59 ms
237,860 KB |
testcase_03 | AC | 59 ms
237,804 KB |
testcase_04 | AC | 60 ms
237,836 KB |
testcase_05 | AC | 59 ms
237,940 KB |
testcase_06 | AC | 60 ms
238,072 KB |
testcase_07 | AC | 60 ms
238,832 KB |
testcase_08 | AC | 59 ms
238,884 KB |
testcase_09 | AC | 59 ms
238,972 KB |
testcase_10 | AC | 60 ms
238,920 KB |
testcase_11 | AC | 60 ms
239,152 KB |
testcase_12 | AC | 60 ms
238,932 KB |
testcase_13 | AC | 65 ms
239,036 KB |
testcase_14 | AC | 64 ms
238,896 KB |
testcase_15 | AC | 64 ms
238,912 KB |
testcase_16 | AC | 1,001 ms
241,864 KB |
testcase_17 | AC | 547 ms
241,916 KB |
testcase_18 | AC | 1,107 ms
241,916 KB |
testcase_19 | AC | 1,122 ms
241,976 KB |
testcase_20 | AC | 1,177 ms
241,904 KB |
testcase_21 | AC | 1,205 ms
241,892 KB |
testcase_22 | AC | 1,194 ms
241,884 KB |
testcase_23 | AC | 1,217 ms
241,868 KB |
testcase_24 | AC | 1,174 ms
241,912 KB |
testcase_25 | AC | 1,108 ms
241,864 KB |
testcase_26 | AC | 1,212 ms
241,964 KB |
testcase_27 | AC | 1,167 ms
241,912 KB |
testcase_28 | AC | 1,215 ms
241,828 KB |
testcase_29 | AC | 1,167 ms
241,880 KB |
testcase_30 | AC | 1,121 ms
241,864 KB |
testcase_31 | AC | 1,117 ms
241,980 KB |
testcase_32 | AC | 1,158 ms
241,896 KB |
testcase_33 | AC | 1,135 ms
241,872 KB |
testcase_34 | AC | 1,171 ms
241,924 KB |
testcase_35 | AC | 1,207 ms
242,128 KB |
testcase_36 | AC | 1,169 ms
241,880 KB |
ソースコード
#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; }