传送门：牛客 - 3947I
题目描述
此时相望不相闻，愿逐月华流照君。
一纸情书，到底蕴含了多少倍的爱情呢？
I love you, not only for what you are, but for what I am when I am with you.
输入描述
共一行：一封若干个字符的情书（大小写不敏感）。
情书不会超过684594个字符（大写、小写字母）。
输出描述
共一行：包含一个整数，即iloveyou在情书中作为子序列出现的次数。
由于答案可能很大，请输出对20010905取模后的值。
思路分析
令dp[i]表示遍历到当前位置，已经匹配了字符串的第i位。
- dp[1]=dp[1]+s[i]== i
- dp[2]=dp[2]+dp[1]*s[i]== l
- dp[3]=dp[3]+dp[2]*s[i]== o
- ……
dp[8]就是答案
样例输入
IloveyouNotonlyforwhatyouareButforwhatIamWhen
样例输出
17
AC代码
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int INF = 0x3f3f3f3f;
const int MOD=20010905;
ll dp[8];
int main() {
IOS;
string s;
cin>>s;
for(auto i:s){
if( i=='i' || i=='I')dp[1]=(dp[1]+1)%MOD;
if( i=='l' || i=='L')dp[2]=(dp[2]+dp[1])%MOD;
if( i=='o' || i=='O')dp[3]=(dp[3]+dp[2])%MOD;
if( i=='v' || i=='V')dp[4]=(dp[4]+dp[3])%MOD;
if( i=='e' || i=='E')dp[5]=(dp[5]+dp[4])%MOD;
if( i=='y' || i=='Y')dp[6]=(dp[6]+dp[5])%MOD;
if( i=='o' || i=='O')dp[7]=(dp[7]+dp[6])%MOD;
if( i=='u' || i=='U')dp[8]=(dp[8]+dp[7])%MOD;
}
cout<<dp[8]<<endl;
return 0;
}
