Atomic String

任意の英小文字列  s ( 1 \leq |s| \leq 10^5) が与えられます。この文字列からいくつかの小文字を大文字にすることで、元素記号を並べた文字列にできるかを判定し、ないなら"No"、あるならそのような文字列の個数を 10^9 + 7で割った余りで答えます。

s = "co" が与えられたとき、元素記号での表記が "CO", "Co" の2通りあるので2と答えます。
s = "a" には対応する表記が無いのでNoと答えます。

以下C++での解答:

#include <iostream>
#include <vector>
#include <set>
#define LMAX 100000
using namespace std;
const int MOD = 1000000007;


int main(){
    vector<string> p = {"H", "He", "Li", "Be", "B", "C", "N", "O", "F", "Ne", "Na", "Mg", "Al", "Si", "P", "S", "Cl", "Ar", "K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu", "Zn", "Ga", "Ge", "As", "Se", "Br", "Kr", "Rb", "Sr", "Y", "Zr", "Nb", "Mo", "Tc", "Ru", "Rh", "Pd", "Ag", "Cd", "In", "Sn", "Sb", "Te", "I", "Xe", "Cs", "Ba", "La", "Ce", "Pr", "Nd", "Pm", "Sm", "Eu", "Gd", "Tb", "Dy", "Ho", "Er", "Tm", "Yb", "Lu", "Hf", "Ta", "W", "Re", "Os", "Ir", "Pt", "Au", "Hg", "Tl", "Pb", "Bi", "Po", "At", "Rn", "Fr", "Ra", "Ac", "Th", "Pa", "U", "Np", "Pu", "Am", "Cm", "Bk", "Cf", "Es", "Fm", "Md", "No", "Lr", "Rf", "Db", "Sg", "Bh", "Hs", "Mt", "Ds", "Rg", "Cn", "Nh", "Fl", "Mc", "Lv", "Ts", "Og"};
    set<string> atom;
    for(auto q: p){
        q[0] = tolower(q[0]);
        atom.insert(q);
    }
    
    string s;
    cin >> s;
    
    int l = s.size();
    /*
    if(l>LMAX){
        cout << "s is longer than the limit.\n";
        return 0;
    }
    if(!l){
        cout << "s is null.\n";
        return 0;
    }
    */
    vector<long long> dp(l+1, 0);
    dp[0] = 1;
    
    for(int i=0; i<l; i++){
        string a;
        a += s[i];
        if(atom.count(a))dp[i+1] += dp[i];
        if(!i)continue;
        a = s[i-1] + a;
        if(atom.count(a))dp[i+1] += dp[i-1];
        dp[i+1] %= MOD;
    }
    
    if(!dp[l])cout << "No" << endl;
    else cout << dp[l] << endl;
    
    return 0;
    
}

元素記号名は高々長さ2なので、「i文字目までが何通りで表せるか」は「i-1文字目~」と「i-2文字目~」を使った漸化式で表せます。上のプログラムではdpにしてるけど変数は3個とっておけばよいです。