Problem A 【算法|HDU 5685 (前缀+逆元)】题意：给出你哈希值的计算方式，然后多次询问子串的哈希值。
题解：我们通过观察哈希值的计算式子就可以发现是连乘，又是多次询问，因此我们可以想到打表的方式。前缀积即可。 a n s [ a , b ] = d p [ b ] d p [ a ? 1 ] ans[a,b] = \frac{dp[b]}{dp[a - 1]} ans[a,b]=dp[a?1]dp[b]?
然后要注意到取模，所以需要乘法逆元。用扩欧或者费马小定理都可以求。
代码
#includeusing namespace std;
const int N = 1E5+10, mod = 9973;
char s[N];
int dp[N], n, a, b;
int Inv(int x,int y)
{
if(x == 1) return 1;
return Inv(y % x, y) * (y - y / x) % y;
}int main()
{
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
#endif
while(cin >> n) {
scanf("%s",s);
int len = strlen(s);
dp[0] = 1;
for(int i = 1;
i <= len;
++i) {
dp[i] = dp[i - 1] * (s[i - 1] - 28) % mod;
}
for(int i = 0;
i < n;
++i) {
scanf("%d %d",&a, &b);
printf("%d\n",dp[b] * Inv(dp[a - 1], mod) % mod);
}
}
return 0;
} 推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络