結果
問題 |
No.1740 Alone 'a'
|
ユーザー |
|
提出日時 | 2022-01-18 21:04:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 143 ms / 2,000 ms |
コード長 | 739 bytes |
コンパイル時間 | 1,554 ms |
コンパイル使用メモリ | 166,916 KB |
実行使用メモリ | 28,656 KB |
最終ジャッジ日時 | 2024-11-23 13:28:57 |
合計ジャッジ時間 | 4,700 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ll long long int #define mod 998244353 ll dp[200005][2][2]; string s; int n; ll solve(int pos,bool used,bool small){ if(pos>=n){ return (ll)(used&&small); } if(dp[pos][used][small]!=-1) return dp[pos][used][small]; ll ans=0; char r=small?'z':s[pos]; char l='a'; if(used) l++; for(char c=l;c<=r;c++){ ans+=solve(pos+1,(c=='a')|used,small|(c<r)); ans%=mod; } return dp[pos][used][small]=ans; } int main() { int t=1; //cin>>t; assert(1<=t&&t<=10); while(t--){ cin >> n >> s; assert(1<=n&&n<=200000); assert(s.size()==n); for(int i=0;i<n;i++){ assert(s[i]>='a'&&s[i]<='z'); } memset(dp,-1,sizeof(dp)); cout<<solve(0,0,0)<<"\n"; } }