結果
問題 |
No.2388 At Least K-Characters
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }