首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#13127

金字塔 给定长度为 n 的字符串 s。从 s 中提取子序列,组成 pyramid 字符串的方法有多少种?答案需对 10 9 +7取模后输出。 时间限制:1000…

金字塔

给定长度为 n 的字符串 s。从 s 中提取子序列,组成 pyramid 字符串的方法有多少种?答案需对 109+7取模后输出。

时间限制:1000ms内存限制:256MB

输入格式

第一行:一个整数 n;

第二行:一个字符串 s。

输出格式

输出组成 pyramid 的方法数(取模 109+7)。


输入样例#1

5
pxxxx

输出样例#1

0

输入样例#2

10
pyyradmiid

输出样例#2

4

数据范围:

1≤N≤105,s 仅包含小写英文字母。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;string&gt; #include &lt;vector&gt; using namespace std; const int MOD = 1e9 + 7; const string TARGET = "pyramid"; int main() {     int n;     string s;     cin &gt;&gt; n &gt;&gt; s;          vector&lt;long long&gt; dp(TARGET.length() + 1, 0);     dp[0] = 1;  // 空子序列,作为起点          for (int i = 0; i &lt; n; i++) {         char c = s[i];         // 检查当前字符能匹配TARGET中的哪个位置         for (int j = TARGET.length() - 1; j &gt;= 0; j--) {             if (c == TARGET[j]) {                 dp[j + 1] = (dp[j + 1] + dp[j]) % MOD;             }         }     }          cout &lt;&lt; dp[TARGET.length()] &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。