题解 | #书中自有______#(C++)

C 书中自有______

观察题面备注：

黄金很稀有，美人不稀有

所以观察题目样例可以得出

答案是gold这个单词的子序列数 * (g,i,r,l) 四个字母分别的个数

#define fp(i, l, r) for(int i=(l); i<=(r); ++i)
#define fq(i, r, l) for(int i=(r); i>=(l); --i)

void solve(){
   string s;
   cin>>s;
   ll n=s.size();
   s=" "+s;
   vector<ll> dp(5);
   fp(i,1,n){
       if(s[i]=='g') dp[1]=(dp[1]+1)%MOD;
       if(s[i]=='o') dp[2]=(dp[2]+dp[1])%MOD;
       if(s[i]=='l') dp[3]=(dp[3]+dp[2])%MOD;
       if(s[i]=='d') dp[4]=(dp[4]+dp[3])%MOD;
   }

   vector<ll> cnt(5);
   fp(i,1,n){
       if(s[i]=='g') cnt[1]++;
       if(s[i]=='i') cnt[2]++;
       if(s[i]=='r') cnt[3]++;
       if(s[i]=='l') cnt[4]++;
   }
   ll cnt1=cnt[1]*cnt[2]%MOD*cnt[3]%MOD*cnt[4]%MOD;

   cout<<dp[4]*cnt1%MOD<<"\n";
}