2016百度之星 - 资格赛（Astar Round1）Problem A

A

题解

用 dp[i] 表示前 i 个字符的 hash 值，那么子串 Sa...b的 hash 值：
H(s)=dp[b]/dp[a−1]%mod
嗯，这里1/dp[a−1]%mod的计算是一个逆元。

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int maxn = 100000 + 10; const int mod = 9973; int n, a, b; char s[maxn]; int dp[maxn];int inv(int x, int y) {if(x == 1) return 1;return inv(y % x, y) * (y - y / x) % y; }int main() {while(scanf("%d", &n) != EOF){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; }

总结

以上是生活随笔为你收集整理的2016百度之星 - 资格赛（Astar Round1）Problem A的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。