1、求逆元
1 int inv(int a) { 2 if(a == 1) return 1; 3 return (MOD - MOD / a) * inv(MOD % a); 4 }
2、线性筛法
1 bool isPrime[MAXN]; 2 int label[MAXN], prime[MAXN]; 3 int n, total; 4 5 void makePrime() { 6 n = 100000; 7 for(int i = 2; i <= n; ++i) { 8 if(!label[i]) { 9 prime[total++] = i; 10 label[i] = total; 11 } 12 for(int j = 0; j < label[i]; ++j) { 13 if(i * prime[j] > n) break; 14 label[i * prime[j]] = j + 1; 15 } 16 } 17 for(int i = 0; i < total; ++i) isPrime[prime[i]] = true; 18 }
3、欧拉函数
1 void phi_table(int n) { 2 //for(int i = 2; i <= n; ++i) phi[i] = 0; 3 phi[1] = 1; 4 for(int i = 2; i <= n; ++i) if(!phi[i]) 5 for(int j = i; j <= n; j += i) { 6 if(!phi[j]) phi[j] = j; 7 phi[j] = phi[j] / i * (i - 1); 8 } 9 }
4、高精度类模板（减法除法的正确性未验证）
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <algorithm> 6 using namespace std; 7 8 const int MAXN = 100010; 9 10 struct bign { 11 int len, s[MAXN]; 12 13 bign () { 14 memset(s, 0, sizeof(s)); 15 len = 1; 16 } 17 bign (int num) { *this = num; } 18 bign (const char *num) { *this = num; } 19 20 void clear() { 21 memset(s, 0, sizeof(s)); 22 len = 1; 23 } 24 25 bign operator = (const int num) {//数字 26 char s[MAXN]; 27 sprintf(s, "%d", num); 28 *this = s; 29 return *this; 30 } 31 bign operator = (const char *num) {//字符串 32 for(int i = 0; num[i] == '0'; num++) ; //去前导0 33 if(*num == 0) --num; 34 len = strlen(num); 35 for(int i = 0; i < len; ++i) s[i] = num[len-i-1] - '0'; 36 return *this; 37 } 38 39 bign operator + (const bign &b) const { 40 bign c; 41 c.len = 0; 42 for(int i = 0, g = 0; g || i < max(len, b.len); ++i) { 43 int x = g; 44 if(i < len) x += s[i]; 45 if(i < b.len) x += b.s[i]; 46 c.s[c.len++] = x % 10; 47 g = x / 10; 48 } 49 return c; 50 } 51 52 bign operator += (const bign &b) { 53 *this = *this + b; 54 return *this; 55 } 56 57 void clean() { 58 while(len > 1 && !s[len-1]) len--; 59 } 60 61 bign operator * (const bign &b) { 62 bign c; 63 c.len = len + b.len; 64 for(int i = 0; i < len; ++i) { 65 for(int j = 0; j < b.len; ++j) { 66 c.s[i+j] += s[i] * b.s[j]; 67 } 68 } 69 for(int i = 0; i < c.len; ++i) { 70 c.s[i+1] += c.s[i]/10; 71 c.s[i] %= 10; 72 } 73 c.clean(); 74 return c; 75 } 76 bign operator *= (const bign &b) { 77 *this = *this * b; 78 return *this; 79 } 80 81 bign operator *= (const int &b) {//使用前要保证>len的位置都是空的 82 for(int i = 0; i < len; ++i) s[i] *= b; 83 for(int i = 0; i < len; ++i) { 84 s[i + 1] += s[i] / 10; 85 s[i] %= 10; 86 } 87 while(s[len]) { 88 s[len + 1] += s[len] / 10; 89 s[len] %= 10; 90 ++len; 91 } 92 return *this; 93 } 94 95 bign operator - (const bign &b) { 96 bign c; 97 c.len = 0; 98 for(int i = 0, g = 0; i < len; ++i) { 99 int x = s[i] - g; 100 if(i < b.len) x -= b.s[i]; 101 if(x >= 0) g = 0; 102 else { 103 g = 1; 104 x += 10; 105 } 106 c.s[c.len++] = x; 107 } 108 c.clean(); 109 return c; 110 } 111 bign operator -= (const bign &b) { 112 *this = *this - b; 113 return *this; 114 } 115 116 bign operator / (const bign &b) { 117 bign c, f = 0; 118 for(int i = len - 1; i >= 0; i--) { 119 f *= 10; 120 f.s[0] = s[i]; 121 while(f >= b) { 122 f -= b; 123 c.s[i]++; 124 } 125 } 126 c.len = len; 127 c.clean(); 128 return c; 129 } 130 bign operator /= (const bign &b) { 131 *this = *this / b; 132 return *this; 133 } 134 135 bign operator % (const bign &b) { 136 bign r = *this / b; 137 r = *this - r*b; 138 return r; 139 } 140 bign operator %= (const bign &b) { 141 *this = *this % b; 142 return *this; 143 } 144 145 bool operator < (const bign &b) { 146 if(len != b.len) return len < b.len; 147 for(int i = len-1; i >= 0; i--) { 148 if(s[i] != b.s[i]) return s[i] < b.s[i]; 149 } 150 return false; 151 } 152 153 bool operator > (const bign &b) { 154 if(len != b.len) return len > b.len; 155 for(int i = len-1; i >= 0; i--) { 156 if(s[i] != b.s[i]) return s[i] > b.s[i]; 157 } 158 return false; 159 } 160 161 bool operator == (const bign &b) { 162 return !(*this > b) && !(*this < b); 163 } 164 165 bool operator != (const bign &b) { 166 return !(*this == b); 167 } 168 169 bool operator <= (const bign &b) { 170 return *this < b || *this == b; 171 } 172 173 bool operator >= (const bign &b) { 174 return *this > b || *this == b; 175 } 176 177 string str() const { 178 string res = ""; 179 for(int i = 0; i < len; ++i) res = char(s[i]+'0') + res; 180 return res; 181 } 182 }; 183 184 istream& operator >> (istream &in, bign &x) { 185 string s; 186 in >> s; 187 x = s.c_str(); 188 return in; 189 } 190 191 ostream& operator << (ostream &out, const bign &x) { 192 out << x.str(); 193 return out; 194 }
5、单纯形（UVA 10498）//只能解标准形式
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 8 const double EPS = 1e-10; 9 const int MAXN = 55; 10 const int INF = 0x3fff3fff; 11 12 inline int sgn(double x) { 13 return (x > EPS) - (x < -EPS); 14 } 15 16 double A[MAXN][MAXN]; 17 double b[MAXN], c[MAXN]; 18 int N[MAXN], B[MAXN]; 19 int n, m; 20 double v; 21 22 bool init() { 23 N[0] = B[0] = v = 0; 24 for(int i = 1; i <= n; ++i) N[++N[0]] = i; 25 for(int i = 1; i <= m; ++i) B[++B[0]] = n + i; 26 return true; 27 } 28 29 void pivot(int l, int e) { 30 b[e] = b[l] / A[l][e]; 31 A[e][l] = 1.0 / A[l][e]; 32 for(int i = 1; i <= N[0]; ++i) { 33 int &x = N[i]; 34 if(x != e) A[e][x] = A[l][x] / A[l][e]; 35 } 36 for(int i = 1; i <= B[0]; ++i) { 37 int &y = B[i]; 38 b[y] -= A[y][e] * b[e]; 39 A[y][l] = -A[y][e] * A[e][l]; 40 for(int j = 1; j <= N[0]; ++j) { 41 int &x = N[j]; 42 if(x != e) A[y][x] -= A[e][x] * A[y][e]; 43 } 44 } 45 v += b[e] * c[e]; 46 c[l] = -A[e][l] * c[e]; 47 for(int i = 1; i <= N[0]; ++i) { 48 int &x = N[i]; 49 if(x != e) c[x] -= A[e][x] * c[e]; 50 } 51 for(int i = 1; i <= N[0]; ++i) if(N[i] == e) N[i] = l; 52 for(int i = 1; i <= B[0]; ++i) if(B[i] == l) B[i] = e; 53 } 54 55 bool simplex() { 56 while(true) { 57 int e = MAXN; 58 for(int i = 1; i <= N[0]; ++i) { 59 int &x = N[i]; 60 if(sgn(c[x]) > 0 && x < e) e = x; 61 } 62 if(e == MAXN) break; 63 double delta = -1; 64 int l = MAXN; 65 for(int i = 1; i <= B[0]; ++i) { 66 int &y = B[i]; 67 if(sgn(A[y][e]) > 0) { 68 double tmp = b[y] / A[y][e]; 69 if(delta == -1 || sgn(tmp - delta) < 0 || (sgn(tmp - delta) == 0 && y < l)) { 70 delta = tmp; 71 l = y; 72 } 73 } 74 } 75 if(l == MAXN) return false; 76 pivot(l, e); 77 } 78 return true; 79 } 80 81 int main() { 82 while(scanf("%d%d", &n, &m) != EOF) { 83 for(int i = 1; i <= n; ++i) scanf("%lf", &c[i]); 84 for(int i = 1; i <= m; ++i) { 85 for(int j = 1; j <= n; ++j) scanf("%lf", &A[n + i][j]); 86 scanf("%lf", &b[n + i]); 87 } 88 init(); 89 simplex(); 90 printf("Nasa can spend %d taka. ", (int)ceil(v * m)); 91 } 92 }
6、高斯消元（-1无解，0无穷解，1唯一解）
1 int guess_eliminatioin() { 2 int rank = 0; 3 for(int i = 0, t = 0; i < m && t < n; ++i, ++t) { 4 int r = i; 5 for(int j = i + 1; j < m; ++j) 6 if(mat[r][t].val < mat[j][t].val) r = j; 7 if(mat[r][t].isZero()) { --i; continue;} 8 else ++rank; 9 if(r != i) for(int j = 0; j <= n; ++j) swap(mat[i][j], mat[r][j]); 10 for(int j = n; j >= t; --j) 11 for(int k = i + 1; k < m; ++k) mat[k][j] -= mat[i][j] * mat[k][t] / mat[i][t]; 12 } 13 for(int i = rank; i < m; ++i) 14 if(!mat[i][n].isZero()) return -1; 15 if(rank < n) return 0; 16 for(int i = n - 1; i >= 0; --i) { 17 for(int j = i + 1; j < n; ++j) 18 mat[i][n] -= mat[j][n] * mat[i][j]; 19 mat[i][n] = mat[i][n] / mat[i][i]; 20 } 21 return 1; 22 }
7、离散对数（小步大步算法）（POJ 3243）
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 typedef long long LL; 8 9 const int SIZEH = 65537; 10 11 struct hash_map { 12 int head[SIZEH], size; 13 int next[SIZEH]; 14 LL state[SIZEH], val[SIZEH]; 15 16 void init() { 17 memset(head, -1, sizeof(head)); 18 size = 0; 19 } 20 21 void insert(LL st, LL sv) { 22 LL h = st % SIZEH; 23 for(int p = head[h]; ~p; p = next[p]) 24 if(state[p] == st) return ; 25 state[size] = st; val[size] = sv; 26 next[size] = head[h]; head[h] = size++; 27 } 28 29 LL find(LL st) { 30 LL h = st % SIZEH; 31 for(int p = head[h]; ~p; p = next[p]) 32 if(state[p] == st) return val[p]; 33 return -1; 34 } 35 } hashmap; 36 37 void exgcd(LL a, LL b, LL &x, LL &y) { 38 if(!b) x = 1, y = 0; 39 else { 40 exgcd(b, a % b, y, x); 41 y -= x * (a / b); 42 } 43 } 44 45 LL inv(LL a, LL n) { 46 LL x, y; 47 exgcd(a, n, x, y); 48 return (x + n) % n; 49 } 50 51 LL pow_mod(LL x, LL p, LL n) { 52 LL ret = 1; 53 while(p) { 54 if(p & 1) ret = (ret * x) % n; 55 x = (x * x) % n; 56 p >>= 1; 57 } 58 return ret; 59 } 60 61 LL BabyStep_GiantStep(LL a, LL b, LL n) { 62 for(LL i = 0, e = 1; i <= 64; ++i) { 63 if(e == b) return i; 64 e = (e * a) % n; 65 } 66 LL k = 1, cnt = 0; 67 while(true) { 68 LL t = __gcd(a, n); 69 if(t == 1) break; 70 if(b % t != 0) return -1; 71 n /= t; b /= t; k = (k * a / t) % n; 72 ++cnt; 73 } 74 hashmap.init(); 75 hashmap.insert(1, 0); 76 LL e = 1, m = LL(ceil(sqrt(n + 0.5))); 77 for(int i = 1; i < m; ++i) { 78 e = (e * a) % n; 79 hashmap.insert(e, i); 80 } 81 LL p = inv(pow_mod(a, m, n), n), v = inv(k, n); 82 for(int i = 0; i < m; ++i) { 83 LL t = hashmap.find((b * v) % n); 84 if(t != -1) return i * m + t + cnt; 85 v = (v * p) % n; 86 } 87 return -1; 88 } 89 90 int main() { 91 LL x, z, k; 92 while(cin>>x>>z>>k) { 93 if(x == 0 && z == 0 && k == 0) break; 94 LL ans = BabyStep_GiantStep(x % z, k % z, z); 95 if(ans == -1) puts("No Solution"); 96 else cout<<ans<<endl; 97 } 98 }
8、母函数
1 /* 2 G(x) = 1 + x + x^2 + x^3 + …… = 1 / (1 - x) 3 G(x) = 1 + 2x + 3x^2 + 4x^3 + …… = 1 / (1 - x)^2 4 5 指数型母函数 6 G(x) = 1 + x + x^2 / 2! + x^3 / 3! + x^4 / 4! + …… = e^x 7 <1, -1, 1, -1, 1, -1, ……> = e^(-x) 8 <0, 1, 0, 1, 0, 1, ……> = (e^x - e^(-x)) / 2 9 <1, 0, 1, 0, 1, 0, ……> = (e^x + e^(-x)) / 2 10 */
9、插头DP（URAL1519 括号表示法）
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 typedef long long LL; 7 8 const int MAXH = 20010; 9 const int SIZEH = 13131; 10 11 struct hash_map { 12 int head[SIZEH]; 13 int next[MAXH], state[MAXH]; 14 LL value[MAXH]; 15 int size; 16 17 void init() { 18 memset(head, -1, sizeof(head)); 19 size = 0; 20 } 21 22 void insert(int st, LL tv) { 23 int h = st % SIZEH; 24 for(int i = head[h]; ~i; i = next[i]) { 25 if(state[i] == st) { 26 value[i] += tv; 27 return ; 28 } 29 } 30 value[size] = tv; state[size] = st; 31 next[size] = head[h]; head[h] = size++; 32 } 33 } hashmap[2]; 34 35 hash_map *cur, *last; 36 int acc[] = {0, -1, 1, 0}; 37 38 int n, m, en, em; 39 char mat[14][14]; 40 41 int getB(int state, int i) { 42 i <<= 1; 43 return (state >> i) & 3; 44 } 45 46 int getLB(int state, int i) { 47 int ret = i, cnt = 1; 48 while(cnt) cnt += acc[getB(state, --ret)]; 49 return ret; 50 } 51 52 int getRB(int state, int i) { 53 int ret = i, cnt = -1; 54 while(cnt) cnt += acc[getB(state, ++ret)]; 55 return ret; 56 } 57 58 void setB(int &state, int i, int tv) { 59 i <<= 1; 60 state = (state & ~(3 << i)) | (tv << i); 61 } 62 63 void update(int x, int y, int state, LL tv) { 64 int left = getB(state, y); 65 int up = getB(state, y + 1); 66 if(mat[x][y] == '*') { 67 if(left == 0 && up == 0) cur->insert(state, tv); 68 return ; 69 } 70 if(left == 0 && up == 0) { 71 if(x == n - 1 || y == m - 1) return ; 72 int newState = state; 73 setB(newState, y, 1); 74 setB(newState, y + 1, 2); 75 cur->insert(newState, tv); 76 } else if(left == 0 || up == 0) { 77 if(x < n - 1) { 78 int newState = state; 79 setB(newState, y, up + left); 80 setB(newState, y + 1, 0); 81 cur->insert(newState, tv); 82 } 83 if(y < m - 1) { 84 int newState = state; 85 setB(newState, y, 0); 86 setB(newState, y + 1, up + left); 87 cur->insert(newState, tv); 88 } 89 } else { 90 int newState = state; 91 setB(newState, y, 0); 92 setB(newState, y + 1, 0); 93 if(left == 1 && up == 1) setB(newState, getRB(state, y + 1), 1); 94 if(left == 1 && up == 2 && !(x == en && y == em)) return ; 95 if(left == 2 && up == 2) setB(newState, getLB(state, y), 2); 96 cur->insert(newState, tv); 97 } 98 } 99 100 void findend() { 101 for(en = n - 1; en >= 0; --en) 102 for(em = m - 1; em >= 0; --em) if(mat[en][em] == '.') return ; 103 } 104 105 LL solve() { 106 findend(); 107 cur = hashmap, last = hashmap + 1; 108 last->init(); 109 last->insert(0, 1); 110 for(int i = 0; i < n; ++i) { 111 int sz = last->size; 112 for(int k = 0; k < sz; ++k) last->state[k] <<= 2; 113 for(int j = 0; j < m; ++j) { 114 cur->init(); 115 sz = last->size; 116 for(int k = 0; k < sz; ++k) 117 update(i, j, last->state[k], last->value[k]); 118 swap(cur, last); 119 } 120 } 121 return last->size ? last->value[0] : 0; 122 } 123 124 int main() { 125 scanf("%d%d", &n, &m); 126 for(int i = 0; i < n; ++i) scanf("%s", mat[i]); 127 cout<<solve()<<endl; 128 }
10、快速傅里叶变换（HDU1402）
1 #include <cmath> 2 #include <algorithm> 3 #include <cstdio> 4 #include <iostream> 5 #include <cstring> 6 #include <complex> 7 using namespace std; 8 typedef complex<double> Complex; 9 const double PI = acos(-1); 10 11 void fft_prepare(int maxn, Complex *&e) { 12 e = new Complex[2 * maxn - 1]; 13 e += maxn - 1; 14 e[0] = 1; 15 for (int i = 1; i < maxn; i <<= 1) 16 e[i] = Complex(cos(2 * PI * i / maxn), sin(2 * PI * i / maxn)); 17 for (int i = 3; i < maxn; i++) 18 if ((i & -i) != i) e[i] = e[i - (i & -i)] * e[i & -i]; 19 for (int i = 1; i < maxn; i++) e[-i] = e[maxn - i]; 20 } 21 /* f = 1: dft; f = -1: idft */ 22 void dft(Complex *a, int N, int f, Complex *e, int maxn) { 23 int d = maxn / N * f; 24 Complex x; 25 for (int n = N, m; m = n / 2, m >= 1; n = m, d *= 2) 26 for (int i = 0; i < m; i++) 27 for (int j = i; j < N; j += n) 28 x = a[j] - a[j + m], a[j] += a[j + m], a[j + m] = x * e[d * i]; 29 for (int i = 0, j = 1; j < N - 1; j++) { 30 for (int k = N / 2; k > (i ^= k); k /= 2); 31 if (j < i) swap(a[i], a[j]); 32 } 33 } 34 35 const int MAXN = 131072; 36 Complex x1[MAXN], x2[MAXN]; 37 char s1[MAXN / 2], s2[MAXN / 2]; 38 int sum[MAXN]; 39 40 int main() { 41 Complex* e = 0; 42 fft_prepare(MAXN, e); 43 while(scanf("%s%s",s1,s2) != EOF) { 44 int n1 = strlen(s1); 45 int n2 = strlen(s2); 46 int n = 1; 47 while(n < n1 * 2 || n < n2 * 2) n <<= 1; 48 for(int i = 0; i < n; ++i) { 49 x1[i] = i < n1 ? s1[n1 - 1 - i] - '0' : 0; 50 x2[i] = i < n2 ? s2[n2 - 1 - i] - '0' : 0; 51 } 52 53 dft(x1, n, 1, e, MAXN); 54 dft(x2, n, 1, e, MAXN); 55 for(int i = 0; i < n; ++i) x1[i] = x1[i] * x2[i]; 56 dft(x1, n, -1, e, MAXN); 57 for(int i = 0; i < n; ++i) x1[i] /= n; 58 59 for(int i = 0; i < n; ++i) sum[i] = round(x1[i].real()); 60 for(int i = 0; i < n; ++i) { 61 sum[i + 1] += sum[i] / 10; 62 sum[i] %= 10; 63 } 64 65 n = n1 + n2 - 1; 66 while(sum[n] <= 0 && n > 0) --n; 67 for(int i = n; i >= 0;i--) printf("%d", sum[i]); 68 puts(""); 69 } 70 }
11、求解线性同余方程组（POJ 2891 exgcd）
1 void exgcd(LL a, LL b, LL &d, LL &x, LL &y) { 2 if(!b) d = a, x = 1, y = 0; 3 else { 4 exgcd(b, a % b, d, y, x); 5 y -= x * (a / b); 6 } 7 } 8 9 int main() { 10 LL k, a1, a2, r1, r2; 11 while(scanf("%I64d", &k) != EOF) { 12 bool flag = true; 13 scanf("%I64d%I64d", &a1, &r1); 14 for(int i = 1; i < k; ++i) { 15 scanf("%I64d%I64d", &a2, &r2); 16 if(!flag) continue; 17 LL r = r2 - r1, d, k1, k2; 18 exgcd(a1, a2, d, k1, k2); 19 if(r % d) flag = false; 20 LL t = a2 / d; 21 k1 = (r / d * k1 % t + t) % t; 22 r1 = r1 + a1 * k1; 23 a1 = a1 / d * a2; 24 } 25 printf("%I64d ", flag ? r1 : -1); 26 } 27 }