結果

問題 No.1740 Alone 'a'
ユーザー aiueokaaiueoka
提出日時 2021-11-13 17:21:16
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 5,074 bytes
コンパイル時間 3,615 ms
コンパイル使用メモリ 243,672 KB
実行使用メモリ 14,412 KB
最終ジャッジ日時 2024-11-27 14:59:58
合計ジャッジ時間 4,969 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 21 ms
14,296 KB
testcase_04 AC 23 ms
14,412 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 1 ms
6,820 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 5 ms
6,816 KB
testcase_12 AC 18 ms
12,200 KB
testcase_13 AC 16 ms
11,764 KB
testcase_14 AC 20 ms
13,732 KB
testcase_15 AC 2 ms
6,816 KB
testcase_16 AC 17 ms
11,264 KB
testcase_17 AC 2 ms
6,816 KB
testcase_18 AC 4 ms
6,820 KB
testcase_19 AC 18 ms
12,260 KB
testcase_20 AC 11 ms
7,936 KB
testcase_21 AC 13 ms
9,728 KB
testcase_22 AC 14 ms
10,820 KB
testcase_23 AC 15 ms
10,944 KB
testcase_24 AC 11 ms
7,936 KB
testcase_25 AC 11 ms
7,936 KB
testcase_26 AC 14 ms
9,472 KB
testcase_27 AC 15 ms
9,984 KB
testcase_28 AC 12 ms
8,704 KB
testcase_29 AC 20 ms
13,804 KB
testcase_30 AC 15 ms
9,728 KB
testcase_31 AC 16 ms
11,136 KB
testcase_32 AC 13 ms
8,832 KB
testcase_33 AC 16 ms
10,988 KB
testcase_34 AC 5 ms
6,820 KB
testcase_35 AC 12 ms
8,704 KB
testcase_36 AC 11 ms
7,680 KB
testcase_37 AC 5 ms
6,816 KB
testcase_38 AC 9 ms
7,040 KB
testcase_39 AC 3 ms
6,820 KB
testcase_40 AC 6 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using ld=long double;
using vvi=vector<vector<int>>;
using vi=vector<int>;
using vpi=vector<pair<int,int>>;
using vvl=vector<vector<ll>>;
using vl=vector<ll>;
using vpl=vector<pair<ll,ll>>;
using vb=vector<bool>;
using vvb=vector<vb>;
using mint=modint1000000007;
using mint9=modint998244353;
using P=pair<ll,ll>;
using Pi=pair<int,int>;
#define outs cout << " "
#define outl cout << endl
ll mod1=1000000007,mod2=998244353;
ll intmax=2147483647,llmax=9223372036854775807;
#define rep(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define dep(i, s, n) for (ll i = n-1; i >=(ll)(s); i--)
#define rem(i, s, n, t) for(ll i = s; i < (ll)(n); t, i++) 
#define dem(i, s, n, t) for(ll i = n-1; i >=(ll)(s); t, i--)
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define nr cout << "No" << endl;return 0;
#define print(a) cout << a << " "
#define np next_permutation
#define fi first
#define se second
#define sor(a) sort(all(a))
#define sorr(a) sort(allr(a))
#define grl greater<ll>
#define gri greater<int>
#define sizel(a) ll(a.size())
#define pb push_back
#define alout(a) {rep(i,0,a.size())cout << a[i] << " ";outl;}
#define chmax(a,b) a=max(a,b);
#define chmin(a,b) a=min(a,b);
void fix(ll a){cout << fixed << setprecision(a);}
void yn(bool a){if(a){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
void alllut(vi s){rep(i,0,s.size())cout << s[i] << " ";outl;}
void allout(vl s){
  rep(i,0,s.size()-1)cout << s[i] << " ";
  cout << s[s.size()-1] << endl;
}
void ifout(bool a,ll x,ll y){cout << ((a)?x:y);}
void paut(pair<ll,ll> s){cout << s.fi << " " << s.se << endl;}
void pout(pair<ll,ll> s){cout << s.fi << " " << s.se << endl;}
ll keta(ll i,ll j){i=i%ll(pow(10,j))/ll(pow(10,j-1));return i;}// j = 0 は ダメ
ll pm1(ll x,ll y){ll s=1;for(ll i=0;i<y;i++)s=s*x%mod1;return s;}
ll pm2(ll x,ll y){ll s=1;for(ll i=0;i<y;i++)s=s*x%mod2;return s;}
mint cnvm(ll x,ll y){if(x<y)return 0;mint s=1;rep(i,1,y+1){s=s*(x+1-i)/i;}return s;}
mint9 cnvm9(ll x,ll y){if(x<y)return 0;mint9 s=1;rep(i,1,y+1){s=s*(x+1-i)/i;}return s;}
ll cnv(ll x,ll y){if(x<y)return 0;ll s=1;rep(i,1,y+1){s=s*(x+1-i)/i;}return s;}
ll gcd(ll a,ll b){for(;min(a,b)>0;)if(a<b)b%=a;else a%=b;return max(a,b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
string tak="Takahashi",aok="Aoki",yes="Yes",no="No",fir="First",sec="Second";
ll kosuu(ll a,ll b){return max(ll(0),b-a+1);}
ll modpow(ll a,ll b,ll mod=llmax){
  ll ans=1;
  while(b){
    if(b%2==1)ans=ans*a%mod;
    a=a*a%mod;
    b/=2;
  }
  return ans;
}
void asdf(){cout << "?" << endl;}
/*
ll l=0,r=a.size();
while(l+1<r){
  ll w=(l+r)/2;
  if(w<(=:tarを含むとき)tar)
  else
}
*/
// '0'=48, 'A'=65, 'Z'=90, 'a'=97', 'z'=122
string tolower(string s){
  rep(i,0,s.size())if(s[i]<91)s[i]=s[i]+32;
  return s;
}
string toupper(string s){
  rep(i,0,s.size())if(s[i]>96)s[i]=s[i]-32;
  return s;
}
ll MAX,mod=mod1;
vl fac,finv,inv;
void COMinit(){
  MAX++;
  fac.resize(MAX);
  finv.resize(MAX);
  inv.resize(MAX);
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  rep(i,2,MAX){
    fac[i]=fac[i-1]*i%mod;
    inv[i]=mod-inv[mod%i]*(mod/i)%mod;
    finv[i]=finv[i-1]*inv[i]%mod;
  }
}
ll com(ll n,ll k){
  if(n<k)return 0;
  if(n<0||k<0)return 0;
  return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
ll MAx;
vl fact;
void FACT(){
  fact=vl(MAx+1,1);
  rep(i,1,MAx+1)fact[i]=fact[i-1]*i;
}
ll upper(vl a,ll b){
  //if(a[0]>b)
  ll l=0,r=a.size()-1;
  while(l+1<r){
    ll w=(l+r)/2;
    if(a[w]<=b)l=w;
    else r=w;
  }
  return l+1;
}
ll lower(vl a,ll b){
  ll l=0,r=a.size()-1;
  while(l+1<r){
    ll w=(l+r)/2;
    if(a[w]<b)l=w;
    else r=w;
  }
  return l+1;
}

ll dai(ll n){
  vi s;
  while(n){
    s.push_back(n%10);
    n/=10;
  }
  sort(all(s));
  for(int i=s.size()-1;i>-1;i--){
    n+=s[i]*pow(10,i);
  }
  return n;
}
ll syou(ll n){
  vi s;
  while(n){
    s.push_back(n%10);
    n/=10;
  }
  sort(all(s));
  rep(i,0,s.size()){
    n+=s[i]*pow(10,s.size()-i-1);
  }
  return n;
}
ll yakusuu(ll a){
  ll co=0;
  for(ll i=1;i*i<a;i++)if(a%i==0)co+=2;
  if(a==pow((int)sqrt(a),2))co++;
  return co;
}
void pin(P &a){
  cin>>a.fi>>a.se;
}
bool prime(ll a){
  rep(i,2,sqrt(a)+1)if(a%i==0)return 0;
  return 1;
}
ll LIS(vl a){
  vl ret;
  for(ll u:a){
    auto itr=lower_bound(all(ret),u);
    if(itr!=ret.end())*itr=u;
    else ret.push_back(u);
  }
  return ll(ret.size());
}
// priority_queue<ll,vl,grl> greater
ll sl=1,ls=0,inf=1e18;

// segtree l~r-1


int main(){
    ll n;cin>>n;
    string s;cin>>s;
    vector<vector<mint9>> dp(n+1,vector<mint9>(4));
    // 0:ok,0 1:ok,1 2:out,0 3:out,1
    dp[0][2]=1;
    rep(i,0,n){
        dp[i+1][0]+=dp[i][0]*25+dp[i][2]*max(0,s[i]-'a'-1);
        dp[i+1][1]+=dp[i][0]+dp[i][1]*25+dp[i][2]*(s[i]!='a')+dp[i][3]*max(0,s[i]-'a'-1);
        dp[i+1][2]+=dp[i][2]*(s[i]!='a');
        dp[i+1][3]+=dp[i][2]*(s[i]=='a')+dp[i][3]*(s[i]!='a');
    }
    mint9 ans=dp[n][1]+dp[n][3];
    ll co=0;
    rep(i,0,n)if(s[i]=='a')co++;
    if(co==1)ans--;
    cout << ans.val() << endl;
}
0