上海市计算机学会竞赛平台2024年12月月赛丙组查找 404
发布时间
阅读量：
阅读量
题目描述
Eve 有一个字符串 SS，该字符串仅由字符 *、4 和 0 组成。字符 * 可以被替换为 4 或 0。
Eve 想要计算在所有可能通过替换 * 生成的字符串中，包含子序列 404 的总数。由于这个数字可能非常大，你需要其输出模 109+7109+7 的结果。
例如，当 SS 为 4*4* 时，可以替换为 4040,4044,4440,4444，其中分别有 1,2,0,01,2,0,0 个 404 子序列，共 33 个。
输入格式
第一行一个整数 TT 表示数据组数。对于每组数据：
第一行一个整数 nn 表示 SS 的长度。
第二行一个字符串 SS。
输出格式
对于每组数据，输出一行一个整数表示答案。
数据范围
对于 30%30% 的数据，1≤T≤101≤T≤10，1≤n,∑n≤101≤n,∑n≤10。
对于 60%60% 的数据，1≤T≤1001≤T≤100，1≤n,∑n≤1001≤n,∑n≤100。
对于 100%100% 的数据，1≤T≤1051≤T≤105，1≤n≤1051≤n≤105，1≤∑n≤1061≤∑n≤106，SS 中仅包含 4、0 和 * 三种字符。
样例数据
输入:
2
4
404
4
44*
输出:
4
3
说明:
第二组数据即为题目描述中举的例子。
详见代码:
#include<bits/stdc++.h>
using namespace std;
int t, m, n;
int mod = 1e9 + 7;
long long dp4;
long long dp40;
long long dp404;
long long p;
int main()
{
cin >> t;
while(t--)
{
dp4=0;
dp40=0;
dp404=0;
p=1;
cin >> n;
string s;
cin >> s;
for(int i = 0; i < n; i++)
{
if (s[i] == '4')
{
dp4 += p;
dp404 += dp40;
}
else if (s[i] == '0')
{
dp40 += dp4;
}
else if (s[i] == '*')
{
dp404 = dp404 * 2 + dp40;
dp40 = dp40 * 2 + dp4;
dp4 = dp4 * 2 + p;
p *= 2;
}
dp4 %= mod;
dp40 %= mod;
dp404 %= mod;
p %= mod;
}
cout << dp404 << "\n";
}
return 0;
}
全部评论 (0)
还没有任何评论哟~