結果

問題 No.1702 count good string
コンテスト
ユーザー harurun
提出日時 2021-09-11 14:07:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 9 ms / 2,000 ms
コード長 973 bytes
コンパイル時間 1,289 ms
コンパイル使用メモリ 90,532 KB
最終ジャッジ日時 2025-01-24 12:46:07
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

int main(){
  const long long mod=1000000007;
  int N;
  cin>>N;
  string S;
  cin>>S;
  unordered_map<char,int> d={
    {'y',0},
    {'u',1},
    {'k',2},
    {'i',3},
    {'c',4},
    {'o',5},
    {'d',6},
    {'e',7},
    {'r',8}
  };
  vector<vector<long long>> dp(10,vector<long long>(2,0));
  long long x;
  for(int i=0;i<N;i++){
    if(d.find(S.at(i))!=d.end()){
      if(S.at(i)=='y'){
        dp.at(0).at(0)++;
      }else{
        x=d.at(S.at(i));
        dp.at(x).at(0)+=dp.at(x-1).at(0);
        dp.at(x).at(0)%=mod;
        dp.at(x).at(1)+=dp.at(x-1).at(1);
        dp.at(x).at(1)%=mod;
      }
    }else if(S.at(i)=='?'){
      dp.at(0).at(1)++;
      for(int j=0;j<8;j++){
        dp.at(j+1).at(1)+=dp.at(j).at(0);
        dp.at(j+1).at(1)%=mod;
      }
    }
  }
  long long ans=dp.at(8).at(0)+dp.at(8).at(1);
  ans%=mod;
  cout<<ans<<endl;
  return 0;
}
0