UVA10069 Distinct Subsequences 超级大数 + DP - c++编程基础

一万多的代码，看着好乱，有点吓人，JAVA还没学会，不然就很短了

题意是给你一个母串一个子串，问你子串在母串中出现的次数，一个字母可以用多次，但是没找到一个子串它的元素下标组合必须不同

比如母串babgbag

子串bag,

你可以找到五个，

rabbbit
rabbit

你可以找到三个

总是做算法，不如来个陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/

数的时候用的是排列组合的方法来数的，DP方程比较简单的，直接for两层找相同的，有点话就加上之前保存的

dp[i][j] += dp[i-][j-1]

一开始找案例找了半天不是到哪里错，后来看到题目说保证答案不超过 10^100，那这个数就太大了，只能用大数来做

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; const int N = 10000 + 5; const int M = 100 + 5; #define DIGIT 4 #define DEPTH 10000 #define MAX 101 typedef int bignum_t[MAX + 1]; int read(bignum_t a, istream& is = cin){ char buf[MAX*DIGIT + 1], ch; int i, j; memset((void*)a, 0, sizeof(bignum_t)); if (!(is >> buf)) return 0; 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]--); return 1; } void write(const bignum_t a, ostream& os = cout){ int i, j; for (os << a[i = a[0]], i--; i; i--) for (j = DEPTH / 10; j; j /= 10) os << a[i] / j % 10; } int comp(const bignum_t a, const bignum_t b){ int i; if (a[0] != b[0]) return a[0] - b[0]; for (i = a[0]; i; i--) if (a[i] != b[i]) return a[i] - b[i]; return 0; } int comp(const bignum_t a, const int b){ int c[12] = { 1 }; for (c[1] = b; c[c[0]] >= DEPTH; c[c[0] + 1] = c[c[0]] / DEPTH, c[c[0]] %= DEPTH, c[0]++); return comp(a, c); } int comp(const bignum_t a, const int c, const int d, const bignum_t b){ int i, t = 0, O = -DEPTH * 2; if (b[0] - a[0]
                     
                      d; i--){ t = t*DEPTH + a[i - d] * c - b[i]; if (t>0) return 1; if (t
                      
                       0) return 1; if (t
                       
                        0; } void add(bignum_t a, const bignum_t b){ int i; for (i = 1; i <= b[0]; i++) if ((a[i] += b[i]) >= DEPTH) a[i] -= DEPTH, a[i + 1]++; if (b[0] >= a[0]) a[0] = b[0]; else for (; a[i] >= DEPTH&&i
                        
                         0); } void add(bignum_t a, const int b){ int i = 1; for (a[1] += b; a[i] >= DEPTH&&i
                         
                          = DEPTH; a[a[0] + 1] = a[a[0]] / DEPTH, a[a[0]] %= DEPTH, a[0]++); } void sub(bignum_t a, const bignum_t b){ int i; for (i = 1; i <= b[0]; i++) if ((a[i] -= b[i])<0) a[i + 1]--, a[i] += DEPTH; for (; a[i]<0; a[i] += DEPTH, i++, a[i]--); for (; !a[a[0]] && a[0]>1; a[0]--); } void sub(bignum_t a, const int b){ int i = 1; for (a[1] -= b; a[i]<0; a[i + 1] += (a[i] - DEPTH + 1) / DEPTH, a[i] -= (a[i] - DEPTH + 1) / DEPTH*DEPTH, i++); for (; !a[a[0]] && a[0]>1; a[0]--); } void sub(bignum_t a, const bignum_t b, const int c, const int d){ int i, O = b[0] + d; for (i = 1 + d; i <= O; i++) if ((a[i] -= b[i - d] * c)<0) a[i + 1] += (a[i] - DEPTH + 1) / DEPTH, a[i] -= (a[i] - DEPTH + 1) / DEPTH*DEPTH; for (; a[i]<0; a[i + 1] += (a[i] - DEPTH + 1) / DEPTH, a[i] -= (a[i] - DEPTH + 1) / DEPTH*DEPTH, i++); for (; !a[a[0]] && a[0]>1; a[0]--); } void mul(bignum_t c, const bignum_t a, const bignum_t b){ int i, j; memset((void*)c, 0, sizeof(bignum_t)); for (c[0] = a[0] + b[0] - 1, i = 1; i <= a[0]; i++) for (j = 1; j <= b[0]; j++) if ((c[i + j - 1] += a[i] * b[j]) >= DEPTH) c[i + j] += c[i + j - 1] / DEPTH, c[i + j - 1] %= DEPTH; for (c[0] += (c[c[0] + 1]>0); !c[c[0]] && c[0]>1; c[0]--); } void mul(bignum_t a, const int b){ int i; for (a[1] *= b, i = 2; i <= a[0]; i++){ a[i] *= b; if (a[i - 1] >= DEPTH) a[i] += a[i - 1] / DEPTH, a[i - 1] %= DEPTH; } for (; a[a[0]] >= DEPTH; a[a[0] + 1] = a[a[0]] / DEPTH, a[a[0]] %= DEPTH, a[0]++); for (; !a[a[0]] && a[0]>1; a[0]--); } void mul(bignum_t b, const bignum_t a, const int c, const int d){ int i; memset((void*)b, 0, sizeof(bignum_t)); for (b[0] = a[0] + d, i = d + 1; i <= b[0]; i++) if ((b[i] += a[i - d] * c) >= DEPTH) b[i + 1] += b[i] / DEPTH, b[i] %= DEPTH; for (; b[b[0] + 1]; b[0]++, b[b[0] + 1] = b[b[0]] / DEPTH, b[b[0]] %= DEPTH); for (; !b[b[0]] && b[0]>1; b[0]--); } void div(bignum_t c, bignum_t a, const bignum_t b){ int h, l, m, i; memset((void*)c, 0, sizeof(bignum_t)); c[0] = (b[0]
                          
                           > 1; h>l; m = (h + l + 1) >> 1) if (comp(b, m, i - 1, a)) h = m - 1; else l = m; for (; !c[c[0]] && c[0]>1; c[0]--); c[0] = c[0]>1   c[0] : 1; } void div(bignum_t a, const int b, int& c){ int i; for (c = 0, i = a[0]; i; c = c*DEPTH + a[i], a[i] = c / b, c %= b, i--); for (; !a[a[0]] && a[0]>1; a[0]--); } void sqrt(bignum_t b, bignum_t a){ int h, l, m, i; memset((void*)b, 0, sizeof(bignum_t)); for (i = b[0] = (a[0] + 1) >> 1; i; sub(a, b, m, i - 1), b[i] += m, i--) for (h = DEPTH - 1, l = 0, b[i] = m = (h + l + 1) >> 1; h>l; b[i] = m = (h + l + 1) >> 1) if (comp(b, m, i - 1, a)) h = m - 1; else l = m; for (; !b[b[0]] && b[0]>1; b[0]--); for (i = 1; i <= b[0]; b[i++] >>= 1); } int length(con

UVA10069 Distinct Subsequences 超级大数 + DP(一)