#include <cstdio> #include <cstdlib> #include <cstring> using namespace std; #define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i) #define debug(...) fprintf(stderr, __VA_ARGS__) #define mp make_pair #define x first #define y second #define pb push_back #define SZ(x) (int((x).size())) #define ALL(x) (x).begin(), (x).end() template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } typedef long long LL; const int oo = 0x3f3f3f3f; const int maxn = 100100; const int Mod = 9973; inline int fpm(int b, int e, int m) { LL t = 1; for ( ; e; e >>= 1, (b *= b) %= m) if (e & 1) (t *= b) %= m; return t; } int n; int val[maxn + 5]; int invval[maxn + 5]; int inv[Mod + 5]; char s[maxn + 5]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif REP(i, 1, Mod) inv[i] = fpm(i, Mod - 2, Mod); int N; while (~scanf("%d", &N)) { scanf("%s", s + 1); n = strlen(s + 1); val[0] = 1; REP(i, 1, n + 1) val[i] = val[i - 1] * (s[i] - 28) % Mod; REP(i, 0, n + 1) invval[i] = inv[val[i]]; REP(i, 0, N) { int a, b; scanf("%d%d", &a, &b), --a; int ans = val[b] * invval[a] % Mod; (ans += Mod) %= Mod; printf("%d\n", ans); } } return 0; } 就WA了 #include <cmath> #include <cstdio> #include <cstdlib> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; #define REP(i, a, b) for (int i = (a), _end_ = (b); i < _end_; ++i) #define debug(...) fprintf(stderr, __VA_ARGS__) #define mp make_pair #define x first #define y second #define pb push_back #define SZ(x) (int((x).size())) #define ALL(x) (x).begin(), (x).end() template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } typedef long long LL; const int oo = 0x3f3f3f3f; const int Mod = 9973; const int maxn = 100000; int n, ml[maxn + 5], ny[maxn + 5], l, r; char s[maxn + 5]; inline int fpm(int b, int e, int m) { LL t = 1; for ( ; e; e >>= 1, (b *= b) %= m) if (e & 1) (t *= b) %= m; return t; } int inv[Mod]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output0.txt", "w", stdout); #endif REP(i, 1, Mod) inv[i] = fpm(i, Mod - 2, Mod); while (~scanf("%d", &n)) { scanf("%s", s + 1); ml[0] = ny[0] = 1; int nn = strlen(s + 1); for (int i = 1; i <= nn; i++) { ml[i] = ml[i - 1] * (s[i] - 28) % Mod; ny[i] = inv[ml[i]]; } for (int i = 1; i <= n; i++) { scanf("%d%d", &l, &r); printf("%d\n", ml[r] * ny[l - 1] % Mod); } } return 0; }
