代码存档
内部包含了：
1、压 8 位的高精度加、减、乘、除、gcd。其中除法指高精除高精。
2、分式计算。包含高精度通分。
3、某道题的部分代码。
PS: 由于题目特性保证了都是正整数，所以并不需要严格判断正负，于是中间省略了一些。
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;
#define fr first
#define sc second
#define ins insert
#define p_b push_back
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define to(k) E[k].to
#define val(k) E[k].val
#define next(k) E[k].next
#define il inline
#define rg register
typedef double db ;
typedef long long ll ;
typedef long double ldb ;
typedef stack <int> sint ;
typedef queue <int> qint ;
typedef vector <int> vint ;
typedef map <int, int> mint ;
typedef pair <int, int> pint ;
const db eps = 1e-7 ;
const int N = 5010 ;
const int M = 10010 ;
const int P = 10000 ;
const int Inf = 1000000007 ;
const int Fni = -1000000007 ;
il int qr(){
int r = 0, f = 1 ;
char c = getchar() ;
while (c > '9' || c < '0'){
if (c == '-') f = -1 ; c = getchar() ;
}
while (c <= '9' && c >= '0'){
r = (r << 1) + (r << 3) + c - '0', c = getchar() ;
}
return r * f ;
}
template <typename T>
void debug(T *const tp, int minn, int maxn, char v = ' ', char c = '\n'){
for (int i = minn ; i <= maxn ; ++ i) cout << tp[i] << v ; cout << c ;
}
int cnt ;
int head[N] ;
struct Edge{
int to ;
int val ;
int next ;
}E[N * 2] ;
il void add_e(int x, int y, int w = 0){
to(++ cnt) = y ; val(cnt) = w ;
next(cnt) = head[x] ; head[x] = cnt ;
}
template <typename T>
il void chkmin(T &x, T y){ x = x > y ? y : x ; }
template <typename T>
il void chkmax(T &x, T y){ x = x < y ? y : x ; }
template <typename T>
il void add(T &x, T y, T mod){
x += y ; x = x >= mod ? x - mod : x ;
}
template <typename T>
il void dec(T &x, T y, T mod){
x -= y ; x = x < 0 ? x + mod : x ;
}
template <typename T>
il T addn(T x, T y, T mod){
x += y ; return (x = x > mod ? x - mod : x) ;
}
template <typename T>
il T decn(T x, T y, T mod){
x -= y ; return (x = x < 0 ? x + mod : x) ;
}
const ll Base = 100000000 ;
int get_L(int x){
int ret = 0 ;
if (!x) return 1 ;
while (x) ret ++, x /= 10 ;
return ret ;
}
struct Big_Num{
ll v[2051] ;
bool mk ; int len, lent ;
void reset(){
len = 0, mk = 0, memset(v, 0, sizeof(v)) ;
}
void out_put(){
if (mk && !(len <= 1 && !v[1])) putchar('-') ;
for (int i = len ; i >= 1 ; -- i){
if (i == len){
printf("%lld", v[i]) ;
continue ;
}
for (int j = 1 ; j <= 8 - get_L(v[i]) ; ++ j) putchar('0') ;
printf("%lld", v[i]) ;
}
//puts("") ;
}
template <typename T>
void set_v(T x){
if (x < 0) mk = 1, x = -x ;
while (x) v[++ len] = x % Base, x /= Base ;
lent = (len - 1) * 8 + get_L(x) ;
}
void set_v(char *x, int L){
int p = 0 ; reset() ;
if (x[1] == '-') ++ p, mk = 1 ;
len = (L - p) / 8 + (((L - p) % 8) > 0) ;
for (int i = L, k = len ; i >= p + 1 ; i -= 8, -- k){
for (int j = min(i - p, 8) ; j >= 1 ; -- j)
v[k] = v[k] * 10ll + (x[i - j + 1] - '0') ;
}
reverse(v + 1, v + len + 1) ; lent = L - p ;
}
Big_Num friend operator ~ (Big_Num A){
A.mk ^= 1 ; return A ;
}
bool friend operator ^ (const Big_Num & A, const Big_Num & B){
if (A.len != B.len) return 0 ;
for (int i = 1 ; i <= A.len ; ++ i)
if (A.v[i] != B.v[i]) return 0 ; return 1 ;
}
bool friend operator < (const Big_Num & A, const Big_Num & B) ;
bool friend operator > (const Big_Num & A, const Big_Num & B) ;
Big_Num friend operator + (const Big_Num & A, const Big_Num & B) ;
Big_Num friend operator - (const Big_Num & A, const Big_Num & B) ;
il bool friend operator < (const Big_Num & A, const Big_Num & B){
if (A.len < B.len) return 1 ;
else if (A.len > B.len) return 0 ;
for (int i = A.len ; i >= 1 ; -- i)
if (A.v[i] < B.v[i]) return 1 ;
else if (A.v[i] > B.v[i]) return 0 ; return 0 ;
}
il bool friend operator > (const Big_Num & A, const Big_Num & B){
if (A.len < B.len) return 0 ;
else if (A.len > B.len) return 1 ;
for (int i = A.len ; i >= 1 ; -- i)
if (A.v[i] > B.v[i]) return 1 ;
else if (A.v[i] < B.v[i]) return 0 ; return 0 ;
}
il bool friend operator <= (const Big_Num & A, const Big_Num & B){
if (A.len < B.len) return 1 ;
else if (A.len > B.len) return 0 ;
for (int i = A.len ; i >= 1 ; -- i)
if (A.v[i] < B.v[i]) return 1 ;
else if (A.v[i] > B.v[i]) return 0 ; return 1 ;
}
il bool friend operator >= (const Big_Num & A, const Big_Num & B){
if (A.len < B.len) return 0 ;
else if (A.len > B.len) return 1 ;
for (int i = A.len ; i >= 1 ; -- i)
if (A.v[i] > B.v[i]) return 1 ;
else if (A.v[i] < B.v[i]) return 0 ; return 1 ;
}
il Big_Num friend operator - (const Big_Num & A, const Big_Num & B){
Big_Num res ; res.reset() ;
Big_Num p, q, t ; p = A, q = B ;
if (p.lent < q.lent) { return (~ (q - p)) ; }
for (rg int i = 1 ; i <= p.len ; ++ i) res.v[i] = p.v[i] - q.v[i] ;
for (rg int i = 1 ; i <= p.len ; ++ i)
if (res.v[i] < 0) res.v[i + 1] --, res.v[i] += Base ;
res.len = p.len ; res.v[0] = -1 ;
for (rg int i = res.len + 20 ; i >= 0 ; -- i)
if (res.v[i]) { res.len = i ; break ; }
if (!res.len) res.len ++ ;
if (res.v[res.len] < 0)
res.mk = 1, res.len --, res.v[res.len] = Base - res.v[res.len] ;
res.lent = (res.len - 1) * 8 + get_L(res.v[res.len]) ;
return res ;
}
il Big_Num friend operator + (const Big_Num & A, const Big_Num & B){
Big_Num res ;
res.reset() ; Big_Num p, q ;
if (A.len > B.len)
p = A, q = B ; else p = B, q = A ;
if (p.mk && q.mk) res.mk = 1 ;
else if (p.mk && !q.mk) { p.mk = 0 ; return (q - p) ; }
else if (!p.mk && q.mk) { q.mk = 0 ; return(p - q) ; }
for (rg int i = 1 ; i <= p.len ; ++ i) res.v[i] = p.v[i] + q.v[i] ;
res.len = p.len ;
for (rg int i = 1 ; i <= p.len + 1 ; ++ i)
if (res.v[i] >= Base)
res.v[i + 1] += res.v[i] / Base, res.v[i] %= Base ;
for (rg int i = res.len + 10 ; i >= 0 ; -- i)
if (res.v[i]) { res.len = i ; break ; }
res.lent = (res.len - 1) * 8 + get_L(res.v[res.len]) ;
return res ;
}
il Big_Num friend operator * (const Big_Num & A, const Big_Num & B){
Big_Num res ; res.reset() ; res.len = A.len + B.len ;
for (rg int i = 1 ; i <= A.len ; ++ i)
for (rg int j = 1 ; j <= B.len ; ++ j)
res.v[i + j - 1] += A.v[i] * B.v[j] ;
for (rg int i = 1 ; i <= res.len + 10 ; ++ i)
res.v[i + 1] += res.v[i] / Base, res.v[i] %= Base ;
res.v[0] = -1 ;
for (rg int i = res.len + 10 ; i >= 0 ; -- i)
if (res.v[i]) { res.len = i ; break ; }
if (!res.len) res.len ++ ;
res.lent = (res.len - 1) * 8 + get_L(res.v[res.len]) ; return res ;
}
il void div2() {
for (rg int i = len ; i >= 1 ; -- i)
v[i - 1] += (v[i] % 2ll) * Base, v[i] >>= 1 ;
v[0] >>= 1 ; while(v[len] == 0) len -- ;
lent = (len - 1) * 8 + get_L(v[len]) ;
}
il void mul2() {
int r = 0 ;
for (rg int i = 1 ; i <= len ; ++ i) {
v[i] = v[i] * 2 + r, r = 0 ;
if(v[i] >= Base) {
r = v[i] / Base, v[i] %= Base ;
if (i == len) len ++ ;
}
}
lent = (len - 1) * 8 + get_L(v[len]) ;
}
Big_Num friend gcd(Big_Num A, Big_Num B){
int cnt2 = 0 ;
while(!(A ^ B)){
if (A < B) swap(A, B) ;
bool a = A.v[1] & 1, b = B.v[1] & 1 ;
if (!a && !b) A.div2(), B.div2(), ++ cnt2 ;
else if (!b) B.div2() ; else if (!a) A.div2() ; else A = A - B ;
}
Big_Num tmp, pmt ;
tmp.set_v(2), pmt.set_v(1) ;
while (cnt2){
if (cnt2 & 1)
pmt = pmt * tmp ;
tmp = tmp * tmp ; cnt2 >>= 1 ;
}
return (A = A * pmt) ;
}
} ;
Big_Num g, t ;
Big_Num l, r, mid, ans ;
struct Frac{
Big_Num fz, fm ;
il void reset(){
fz.reset() ;
fm.reset() ;
}
il void reverse(){
Big_Num t = fz ; fz = fm, fm = t ;
}
il void div(){
g = gcd(fz, fm) ; r.reset() ;
int lnr = fz.len - g.len ; l.reset() ; l.len = lnr ;
l.v[l.len] = 1 ; r.len = lnr + 1 ; r.v[r.len] = 90000000 ;
while (l <= r){
mid = (l + r) ; mid.div2() ;
if (mid * g >= fz) ans = mid, r = mid - t ; else l = mid + t ;
}
fz = ans ; l.reset() ;
lnr = fm.len - g.len ; l.reset() ; l.len = lnr ;
l.v[l.len] = 1 ; r.len = lnr + 1 ; r.v[r.len] = 90000000 ;
while (l <= r){
mid = (l + r) ; mid.div2() ;
if (mid * g >= fm) ans = mid, r = mid - t ; else l = mid + t ;
}
fm = ans ;
}
il void out_put(){
fz.out_put() ;
putchar('/') ;
fm.out_put() ; puts("") ;
}
template <typename T>
il void set_v(T son, T mum){
fz.set_v(son), fm.set_v(mum) ;
}
template <typename T>
il void set_v(char *son, int Lson, char *mum, int Lmum){
fz.set_v(son, Lson) ; fm.set_v(mum, Lmum) ;
}
il Frac friend operator + (Frac A, Frac B){
Frac res ; res.reset() ;
if (!A.fz.len && !A.fm.len) return B ;
if (!B.fz.len && !B.fm.len) return A ;
if (!(A.fm ^ B.fm)){
Big_Num p = A.fm, q = B.fm, o, s, t ;
o = p * q ; s = q * A.fz ; t = p * B.fz ;
A.fm = o ; B.fm = o ; A.fz = s ; B.fz = t ;
}
res.fm = A.fm ; res.fz = A.fz + B.fz ; return res ;
}
il Frac friend operator - (Frac A, Frac B){
Frac res ; res.reset() ;
if (!(A.fm ^ B.fm)){
Big_Num p = A.fm, q = B.fm, o, s, t ;
o = p * q ; s = q * A.fz ; t = p * B.fz ;
A.fm = o ; B.fm = o ; A.fz = s ; B.fz = t ;
}
res.fm = A.fm ; res.fz = A.fz - B.fz ; return res ;
}
il Frac friend operator * (const Frac & A, const Frac & B){
Frac res ; res.reset() ;
res.fm = A.fm * B.fm ;
res.fz = A.fz * B.fz ;
return res ;
}
il Frac friend operator ^ (const Frac & A, const Frac & B){
Frac res ; res.reset() ;
res.fz = A.fz * B.fz ; res.fm = A.fm ; return res ;
}
il Frac friend operator & (const Frac & A, const Frac & B){
Frac res ; res.reset() ;
res.fm = A.fm * B.fm ; res.fz = A.fz ; return res ;
}
} r1, r2, r3, r0 ;
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
int f[N] ;
int A, B ;
Frac res ;
char S[N] ;
Frac Rp[N] ;
Frac Pr[N] ;
int base[N] ;
int T, n, m ;
int main(){
cin >> A >> B ;
cin >> (S + 1) ;
r0.set_v(1, B) ;
r1.set_v(A, 1) ;
Rp[0].set_v(1, 1) ;
r2.set_v(B - A, 1) ;
m = strlen(S + 1), Pr[m].set_v(1, 1) ;
for (rg int i = 1 ; i <= m ; ++ i)
base[i] = (bool)(S[i] == 'H') ;
for (rg int j = m ; j >= 1 ; -- j)
Pr[j - 1] = Pr[j] ^ (base[j] ? r1 : r2) ;
for (rg int j = 1 ; j <= m ; ++ j) Rp[j] = Rp[j - 1] & r0 ;
for (rg int i = 2, j = 0 ; i <= m ; ++ i){
while (j && base[j + 1] != base[i]) j = f[j] ;
if (base[j + 1] == base[i]) ++ j ; f[i] = j ;
}
t.reset() ; t.set_v(1) ;
r3 = Pr[0] * Rp[m] ; r3.reverse() ; int k = m ;
while (m) res = res + Pr[m] * Rp[k - m] , m = f[m] ;
res = res * r3 ; res.div() ; res.out_put() ; return 0 ;
}