UVA10069 Distinct Subsequences 超级大数 + DP(二)
st bignum_t a){ int t, ret; for (ret = (a[0] - 1)*DIGIT, t = a[a[0]]; t; t /= 10, ret++); return ret>0 ret : 1; } int digit(const bignum_t a, const int b){ int i, ret; for (ret = a[(b - 1) / DIGIT + 1], i = (b - 1) % DIGIT; i; ret /= 10, i--); return ret % 10; } int zeronum(const bignum_t a){ int ret, t; for (ret = 0; !a[ret + 1]; ret++); for (t = a[ret + 1], ret *= DIGIT; !(t % 10); t /= 10, ret++); return ret; } void comp(int* a, const int l, const int h, const int d){ int i, j, t; for (i = l; i <= h; i++) for (t = i, j = 2; t>1; j++) while (!(t%j)) a[j] += d, t /= j; } void convert(int* a, const int h, bignum_t b){ int i, j, t = 1; memset(b, 0, sizeof(bignum_t)); for (b[0] = b[1] = 1, i = 2; i <= h; i++) if (a[i]) for (j = a[i]; j; t *= i, j--) if (t*i>DEPTH) mul(b, t), t = 1; mul(b, t); } void combination(bignum_t a, int m, int n){ int* t = new int[m + 1]; memset((void*)t, 0, sizeof(int)*(m + 1)); comp(t, n + 1, m, 1); comp(t, 2, m - n, -1); convert(t, m, a); delete[]t; } void permutation(bignum_t a, int m, int n){ int i, t = 1; memset(a, 0, sizeof(bignum_t)); a[0] = a[1] = 1; for (i = m - n + 1; i <= m; t *= i++) if (t*i>DEPTH) mul(a, t), t = 1; mul(a, t); } #define SGN(x) ((x)>0 1:((x)<0 -1:0)) #define ABS(x) ((x)>0 (x):-(x)) int read(bignum_t a, int &sgn, istream& is = cin){ char str[MAX*DIGIT + 2], ch, *buf; int i, j; memset((void*)a, 0, sizeof(bignum_t)); if (!(is >> str)) return 0; buf = str, sgn = 1; if (*buf == '-') sgn = -1, buf++; for (a[0] = strlen(buf), i = a[0] / 2 - 1; i >= 0; i--) ch = buf[i], buf[i] = buf[a[0] - 1 - i], buf[a[0] - 1 - i] = ch; for (a[0] = (a[0] + DIGIT - 1) / DIGIT, j = strlen(buf); j
1; a[0]--); if (a[0] == 1 && !a[1]) sgn = 0; return 1; } struct bignum{ bignum_t num; int sgn; public: inline bignum(){ memset(num, 0, sizeof(bignum_t)); num[0] = 1; sgn = 0; } inline int operator!(){ return num[0] == 1 && !num[1]; } inline bignum& operator=(const bignum& a){ memcpy(num, a.num, sizeof(bignum_t)); sgn = a.sgn; return *this; } inline bignum& operator=(const int a){ memset(num, 0, sizeof(bignum_t)); num[0] = 1; sgn = SGN(a); add(num, sgn*a); return *this; }; inline bignum& operator+=(const bignum& a){ if (sgn == a.sgn)add(num, a.num); else if (sgn&&a.sgn){ int ret = comp(num, a.num); if (ret>0)sub(num, a.num); else if (ret<0){ bignum_t t; memcpy(t, num, sizeof(bignum_t)); memcpy(num, a.num, sizeof(bignum_t)); sub(num, t); sgn = a.sgn; } else memset(num, 0, sizeof(bignum_t)), num[0] = 1, sgn = 0; } else if (!sgn)memcpy(num, a.num, sizeof(bignum_t)), sgn = a.sgn; return *this; } inline bignum& operator+=(const int a){ if (sgn*a>0)add(num, ABS(a)); else if (sgn&&a){ int ret = comp(num, ABS(a)); if (ret>0)sub(num, ABS(a)); else if (ret<0){ bignum_t t; memcpy(t, num, sizeof(bignum_t)); memset(num, 0, sizeof(bignum_t)); num[0] = 1; add(num, ABS(a)); sgn = -sgn; sub(num, t); } else memset(num, 0, sizeof(bignum_t)), num[0] = 1, sgn = 0; } else if (!sgn)sgn = SGN(a), add(num, ABS(a)); return *this; } inline bignum operator+(const bignum& a){ bignum ret; memcpy(ret.num, num, sizeof(bignum_t)); ret.sgn = sgn; ret += a; return ret; } inline bignum operator+(const int a){ bignum ret; memcpy(ret.num, num, sizeof(bignum_t)); ret.sgn = sgn; ret += a; return ret; } inline bignum& operator-=(const bignum& a){ if (sgn*a.sgn<0)add(num, a.num); else if (sgn&&a.sgn){ int ret = comp(num, a.num); if (ret>0)sub(num, a.num); else if (ret<0){ bignum_t t; memcpy(t, num, sizeof(bignum_t)); memcpy(num, a.num, sizeof(bignum_t)); sub(num, t); sgn = -sgn; } else memset(num, 0, sizeof(bignum_t)), num[0] = 1, sgn = 0; } else if (!sgn)add(num, a.num), sgn = -a.sgn; return *this; } inline bignum& operator-=(const int a){ if (sgn*a<0)add(num, ABS(a)); else if (sgn&&a){ int ret = comp(num, ABS(a)); if (ret>0)sub(num, ABS(a)); else if (ret<0){ bignum_t t; memcpy(t, num, sizeof(bignum_t)); memset(num, 0, sizeof(bignum_t)); num[0] = 1; add(num, ABS(a)); sub(num, t); sgn = -sgn; } else memset(num, 0, sizeof(bignum_t)), num[0] = 1, sgn = 0; } else if (!sgn)sgn = -SGN(a), add(num, ABS(a)); return *this; } inline bignum operator-(const bignum& a){ bignum ret; memcpy(ret.num, num, sizeof(bignum_t)); ret.sgn = sgn; ret -= a; return ret; } inline bignum operator-(const int a){ bignum ret; memcpy(ret.num, num, sizeof(bignum_t)); ret.sgn = sgn; ret -= a; return ret; } inline bignum& operator*=(const bignum& a){ bignum_t t; mul(t, num, a.num); memcpy(num, t, sizeof(bignum_t)); sgn *= a.sgn; return *this; } inline bignum& operator*=(const int a){ mul(num, ABS(a)); sgn *= SGN(a); return *this; } inline bignum operator*(const bignum& a){ bignum ret; mul(ret.num, num, a.num); ret.sgn = sgn*a.sgn; return ret; } inline bignum operator*(const int a){ bignum ret; memcpy(ret.num, num, sizeof(bignum_t)); mul(ret.num, ABS(a)); ret.sgn = sgn*SGN(a); return ret; } inline bignum& operator/=(const bignum& a){ bignum_t t; div(t, num, a.num); memcpy(num, t, sizeof(bignum_t)); sgn = (num[0] == 1 && !num[1]) 0 : sgn*a.sgn; return *this; } inline bignum& operator/=(const int a){ int t; div(num, ABS(a), t); sgn = (num[0] == 1 && !num[1]) 0 : sgn*SGN(a); return *this; } inline bignum operator/(const bignum& a){ bignum ret; bignum_t t; memcpy(t, num, sizeof(bignum_t)); div(ret.num, t, a.num); ret.sgn = (ret.num[0] == 1 && !ret.num[1]) 0 : sgn*a.sgn; return ret; } inline bignum operator/(const int a){ bignum ret; int t; memcpy(ret.num, num, sizeof(bignum_t)); div(ret.num, ABS(a), t); ret.sgn = (ret.num[0] == 1 && !ret.num[1]) 0 : sgn*SGN(a); return ret; } inline bignum& operator%=(const bignum& a){ bignum_t t; div(t, num, a.num); if (num[0] == 1 && !num[1])sgn = 0; return *this; } inline int operator%=(const int a){ int t; div(num, ABS(a), t); memset(num, 0, sizeof(bignum_t)); num[0] = 1; add(num, t); return t; } inline bignum operator%(const bignum& a){ bignum ret; bignum_t t; memcpy(ret.num, num, sizeof(bignum_t)); div(t, ret.num, a.num); ret.sgn = (ret.num[0] == 1 && !ret.num[1]) 0 : sgn; return ret; } inline int operator%(const int a){ bignum ret; int t; memcpy(ret.num, num, sizeof(bignum_t)); div(ret.num, ABS(a), t); memset(ret.num, 0, sizeof(bignum_t)); ret.num[0] = 1; add(ret.num, t); return t; } inline bignum& operator++(){ *this += 1; return *this; } inline bignum& operator--(){ *this -= 1; return *this; }; inline int operator>(const bignum& a){ return sgn>0 (a.sgn>0 comp(num, a.num)>0:1) : (sgn<0 (a.sgn<0 comp(num, a.num)<0 : 0) : a.sgn<0); } inline int operator>(const int a){ return sgn>0 (a>0 comp(num, a)>0:1) : (sgn<0 (a<0 comp(num, -a)<0 : 0) : a<0); } inline int operator>=(const bignum& a){ return sgn>0 (a.sgn>0 comp(num, a.num) >= 0 : 1) : (sgn<0 (a.sgn<0 comp(num, a.num) <= 0 : 0) : a.sgn <= 0); } inline int operator>=(const int a){ return sgn>0 (a>0 comp(num, a) >= 0 : 1) : (sgn<0 (a<0 comp(num, -a) <= 0 : 0) : a <= 0); } inline int operator<(const bignum& a){ return sgn<0 (a.sgn<0 comp(num, a.num)>0:1) : (sgn>0 (a.sgn>0 comp(num, a.num)<0 : 0) : a.sgn>0); } inline int operator<(const int a){ return sgn<0 (a<0 comp(num, -a)>0:1) : (sgn>0 (a>0 comp(num, a)<0 : 0) : a>0); } inline int operator<=(const bignum& a){ return sgn<0 (a.sgn<0 comp(num, a.num) >= 0 : 1) : (sgn>0 (a.sgn>0 comp(num, a.num) <= 0 : 0) : a.sgn >= 0); } inline int operator<=(const int a){ return sgn<0 (a<0 comp(num, -a) >= 0 : 1) : (sgn>0 (a>0 comp(num, a) <= 0 : 0) : a >= 0); } inline int operator==(const bignum& a){ return (sgn == a.sgn) !comp(num, a.num) : 0; } inline int operator==(const int a){ return (sgn*a >= 0) !comp(num, ABS(a)) : 0; } inline int operator!=(const bignum& a){ return (sgn == a.sgn) comp(num, a.num) : 1; } inline int operator!=(const int a){ return (sgn*a >= 0) comp(num, ABS(a)) : 1; } inline int operator[](const int a){ return digit(num, a); } friend inline istream& operator>>(istream& is, bignum& a){ read(a.num, a.sgn, is); return is; } friend inline ostream& operator<<(ostream& os, const bignum& a){ if (a.sgn<0)os << '-'; write(a.num, os); return os; } friend inline bignum sqrt(const bignum& a){ bignum ret; bignum_t t; memcpy(t, a.num, sizeof(bignum_t)); sqrt(ret.num, t); ret.sgn = ret.num[0] != 1 || ret.num[1]; return ret; } friend inline bignum sqrt(const bignum& a, bignum& b){ bignum ret; memcpy(b.num, a.num, sizeof(bignum_t)); sqrt(ret.num, b.num); ret.sgn = ret.num[0] != 1 || ret.num[1]; b.sgn = b.num[0] != 1 || ret.num[1]; return ret; } inline int length(){ return ::length(num); } inline int zeronum(){ return ::zeronum(num); } inline bignum C(const int m, const int n){ combination(num, m, n); sgn = 1; return *this; } inline bignum P(const int m, const int n){ permutation(num, m, n); sgn = 1; return *this; } }; /**********************************************/ bignum dp[N][M]; char a[N], b[M]; int n,m; void clear() { for (int i = 0; i <= n; ++i) dp[i][0] = 1; } int main() { int t; cin>>t; while (t--) { scanf("%s%s", a + 1, b + 1); a[0] = b[0] = '&'; n = strlen(a) - 1; m = strlen(b) - 1; clear(); for (int i=1; i<=n;++i) { for (int j=1; j<=m;++j) { dp[i][j] = dp[i - 1][j]; if (a[i] == b[j]) dp[i][j] += dp[i - 1][j - 1]; } } cout<