[关闭]
@dongshunyao 2019-11-11T15:51:51.000000Z 字数 70524 阅读 930

2019-11-11 %版


Tutorial


前言

一份可以用于ACM和OI的模版,有问题或建议请留下批注QAQ

不断更新(挖坑)中

感谢付老师、小黄老师、郑老师和QDD的大力滋兹,Orz%%%


目录


基础

通用模版

  1. #include<bits/stdc++.h>
  2. #define endl "\n" //防止卡endl
  3. #define rg register int //循环变量专用
  4. #pragma GCC optimize("Ofast,no-stack-protector") //神仙优化,比较假
  5. #include<iostream>
  6. #include<cstdio>
  7. #include<algorithm>
  8. #include<cmath>
  9. #include<string>
  10. #include<vector>
  11. #include<stack>
  12. #include<map>
  13. #include<ctime>
  14. using namespace std;
  15. int main()
  16. {
  17. freopen("input.in", "r", stdin);
  18. freopen("output.out", "w", stdout);
  19. ios::sync_with_stdio(false); //cin、cout不能与scanf、printf混用
  20. cin.tie(0); //输入一定要在输出之前
  21. cout.tie(0);
  22. printf("%.5lf", (double)clock() / CLOCKS_PER_SEC);//输出时间
  23. return 0;
  24. }

性能测试

  1. //用已经AC了的题交这个代码,以测试评测机性能
  2. int a;
  3. for (int i = 0; i < 1000000000; i++) a ^= i;
  4. cout << a;

玄学优化

  1. #pragma GCC optimize ("O3") //开O3
  2. #pragma GCC -mcmodle=large //开巨型数组不RE(编译时间变长)
  3. // 以下慎用
  4. #pragma GCC optimize(2)
  5. #pragma GCC optimize(3)
  6. #pragma GCC optimize("Ofast")
  7. #pragma GCC optimize("inline")
  8. #pragma GCC optimize("-fgcse")
  9. #pragma GCC optimize("-fgcse-lm")
  10. #pragma GCC optimize("-fipa-sra")
  11. #pragma GCC optimize("-ftree-pre")
  12. #pragma GCC optimize("-ftree-vrp")
  13. #pragma GCC optimize("-fpeephole2")
  14. #pragma GCC optimize("-ffast-math")
  15. #pragma GCC optimize("-fsched-spec")
  16. #pragma GCC optimize("unroll-loops")
  17. #pragma GCC optimize("-falign-jumps")
  18. #pragma GCC optimize("-falign-loops")
  19. #pragma GCC optimize("-falign-labels")
  20. #pragma GCC optimize("-fdevirtualize")
  21. #pragma GCC optimize("-fcaller-saves")
  22. #pragma GCC optimize("-fcrossjumping")
  23. #pragma GCC optimize("-fthread-jumps")
  24. #pragma GCC optimize("-funroll-loops")
  25. #pragma GCC optimize("-freorder-blocks")
  26. #pragma GCC optimize("-fschedule-insns")
  27. #pragma GCC optimize("inline-functions")
  28. #pragma GCC optimize("-ftree-tail-merge")
  29. #pragma GCC optimize("-fschedule-insns2")
  30. #pragma GCC optimize("-fstrict-aliasing")
  31. #pragma GCC optimize("-falign-functions")
  32. #pragma GCC optimize("-fcse-follow-jumps")
  33. #pragma GCC optimize("-fsched-interblock")
  34. #pragma GCC optimize("-fpartial-inlining")
  35. #pragma GCC optimize("no-stack-protector")
  36. #pragma GCC optimize("-freorder-functions")
  37. #pragma GCC optimize("-findirect-inlining")
  38. #pragma GCC optimize("-fhoist-adjacent-loads")
  39. #pragma GCC optimize("-frerun-cse-after-loop")
  40. #pragma GCC optimize("inline-small-functions")
  41. #pragma GCC optimize("-finline-small-functions")
  42. #pragma GCC optimize("-ftree-switch-conversion")
  43. #pragma GCC optimize("-foptimize-sibling-calls")
  44. #pragma GCC optimize("-fexpensive-optimizations")
  45. #pragma GCC optimize("inline-functions-called-once")
  46. #pragma GCC optimize("-fdelete-null-pointer-checks")

手动扩栈

  1. //C++使用,在开头写
  2. #pragma comment(linker, "/STACK:1024000000,1024000000")
  3. //G++使用
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. extern void MAIN(void) __asm__("MAIN");
  7. void MAIN()
  8. {
  9. //在这里写代码
  10. exit(0);
  11. }
  12. int main()
  13. {
  14. long long size = 4096ll << 20; // 4096 MB
  15. char* p = new char[size] + size;
  16. __asm__ __volatile__(
  17. "movq %0, %%rsp\n"
  18. "pushq $exit\n"
  19. "jmp MAIN\n"
  20. ::"r"(p));
  21. MAIN();
  22. }

输入输出

特殊格式

  1. char s[MAX];
  2. scanf(" %[^\n]", s); //遇到回车结束(读一整行)
  3. scanf(" %[^#]", s); //遇到#结束
  4. scanf(" %[^ ]", s); //遇到空格结束
  5. char str[20];
  6. cin.getline(name); //读入一行
  7. cin.getline(name, 20); //读入一行,指定长度
  8. string s;
  9. getline(cin, s); //string的读入一行
  10. //读到文件尾
  11. while (cin) {}
  12. while(~scanf) {}
  13. // 输出为二进制
  14. cout << "x = " << bitset<32>(x) << endl;

精度控制

  1. //设置有效数字位数。
  2. cout << setprecision(位数) << number << endl;
  3. //设置小数精度(小数点后的有效位数)
  4. cout <<setiosflags(ios::fixed);
  5. cout << setprecision(位数) << number << endl;
  6. //设置小数精度(小数点后的有效位数)
  7. cout << fixed << setprecision(10) << number << endl;

  1. // 本机测试需要EOF才能看到输出结果
  2. // 快速输入挂
  3. // 读入1e7 大约0.4s
  4. namespace fastinput
  5. {
  6. #define BUF_SIZE 1048576
  7. inline char nc()
  8. {
  9. static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
  10. if (p1 == pend)
  11. {
  12. p1 = buf;
  13. pend = buf + fread(buf, 1, BUF_SIZE, stdin);
  14. assert(pend != p1);
  15. }
  16. return *p1++;
  17. }
  18. inline bool blank(char c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t'; }
  19. // non-negative integer
  20. inline int get_unsigned_int()
  21. {
  22. int x = 0;
  23. char c = nc();
  24. while (blank(c)) c = nc();
  25. for (; c >= '0' && c <= '9'; c = nc()) x = x * 10 + c - '0';
  26. return x;
  27. }
  28. // integer
  29. inline int get_int()
  30. {
  31. int x = 0, sgn = 1;
  32. char c = nc();
  33. while (blank(c)) c = nc();
  34. if (c == '-') sgn = -1, c = nc();
  35. for (; c >= '0' && c <= '9'; c = nc()) x = x * 10 + c - '0';
  36. return sgn * x;
  37. }
  38. #undef BUF_SIZE
  39. };
  40. //使用
  41. using namespace fastinput;
  42. int n = get_int();
  43. unsigned int n = get_unsigned_int();
  44. //输入输出挂
  45. namespace fastIO
  46. {
  47. #define BUF_SIZE 100000
  48. #define OUT_SIZE 100000
  49. #define ll long long
  50. //fread->read
  51. bool IOerror = 0;
  52. inline char nc()
  53. {
  54. static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
  55. if (p1 == pend)
  56. {
  57. p1 = buf; pend = buf + fread(buf, 1, BUF_SIZE, stdin);
  58. if (pend == p1) { IOerror = 1; return -1; }
  59. //{printf("IO error!\n"); system("pause"); for (;;); exit(0);}
  60. }
  61. return *p1++;
  62. }
  63. inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
  64. inline void read(int &x)
  65. {
  66. bool sign = 0; char ch = nc(); x = 0;
  67. for (; blank(ch); ch = nc());
  68. if (IOerror) return;
  69. if (ch == '-') sign = 1, ch = nc();
  70. for (; ch >= '0'&&ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  71. if (sign) x = -x;
  72. }
  73. inline void read(ll &x)
  74. {
  75. bool sign = 0; char ch = nc(); x = 0;
  76. for (; blank(ch); ch = nc());
  77. if (IOerror) return;
  78. if (ch == '-') sign = 1, ch = nc();
  79. for (; ch >= '0'&&ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  80. if (sign) x = -x;
  81. }
  82. inline void read(double &x)
  83. {
  84. bool sign = 0; char ch = nc(); x = 0;
  85. for (; blank(ch); ch = nc());
  86. if (IOerror) return;
  87. if (ch == '-') sign = 1, ch = nc();
  88. for (; ch >= '0'&&ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  89. if (ch == '.')
  90. {
  91. double tmp = 1; ch = nc();
  92. for (; ch >= '0'&&ch <= '9'; ch = nc())tmp /= 10.0, x += tmp * (ch - '0');
  93. }
  94. if (sign) x = -x;
  95. }
  96. inline void read(char *s)
  97. {
  98. char ch = nc();
  99. for (; blank(ch); ch = nc());
  100. if (IOerror) return;
  101. for (; !blank(ch) && !IOerror; ch = nc()) *s++ = ch;
  102. *s = 0;
  103. }
  104. inline void read(char &c)
  105. {
  106. for (c = nc(); blank(c); c = nc());
  107. if (IOerror) { c = -1; return; }
  108. }
  109. //fwrite->write
  110. struct Ostream_fwrite
  111. {
  112. char *buf, *p1, *pend;
  113. Ostream_fwrite() { buf = new char[BUF_SIZE]; p1 = buf; pend = buf + BUF_SIZE; }
  114. void out(char ch)
  115. {
  116. if (p1 == pend) { fwrite(buf, 1, BUF_SIZE, stdout); p1 = buf; }
  117. *p1++ = ch;
  118. }
  119. void print(int x)
  120. {
  121. static char s[15], *s1; s1 = s;
  122. if (!x) *s1++ = '0'; if (x < 0) out('-'), x = -x;
  123. while (x) *s1++ = x % 10 + '0', x /= 10;
  124. while (s1-- != s) out(*s1);
  125. }
  126. void println(int x)
  127. {
  128. static char s[15], *s1; s1 = s;
  129. if (!x) *s1++ = '0'; if (x < 0) out('-'), x = -x;
  130. while (x) *s1++ = x % 10 + '0', x /= 10;
  131. while (s1-- != s) out(*s1); out('\n');
  132. }
  133. void print(ll x)
  134. {
  135. static char s[25], *s1; s1 = s;
  136. if (!x) *s1++ = '0'; if (x < 0) out('-'), x = -x;
  137. while (x) *s1++ = x % 10 + '0', x /= 10;
  138. while (s1-- != s) out(*s1);
  139. }
  140. void println(ll x)
  141. {
  142. static char s[25], *s1; s1 = s;
  143. if (!x) *s1++ = '0'; if (x < 0) out('-'), x = -x;
  144. while (x) *s1++ = x % 10 + '0', x /= 10;
  145. while (s1-- != s) out(*s1); out('\n');
  146. }
  147. void print(double x, int y)
  148. {
  149. static ll mul[] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000, 1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL, 100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL };
  150. if (x < -1e-12) out('-'), x = -x; x *= mul[y];
  151. ll x1 = (ll)floor(x); if (x - floor(x) >= 0.5) ++x1;
  152. ll x2 = x1 / mul[y], x3 = x1 - x2 * mul[y]; print(x2);
  153. if (y > 0) { out('.'); for (size_t i = 1; i < y&&x3*mul[i] < mul[y]; out('0'), ++i); print(x3); }
  154. }
  155. void println(double x, int y) { print(x, y); out('\n'); }
  156. void print(char *s) { while (*s) out(*s++); }
  157. void println(char *s) { while (*s) out(*s++); out('\n'); }
  158. void flush() { if (p1 != buf) { fwrite(buf, 1, p1 - buf, stdout); p1 = buf; } }
  159. ~Ostream_fwrite() { flush(); }
  160. } Ostream;
  161. inline void print(int x) { Ostream.print(x); }
  162. inline void println(int x) { Ostream.println(x); }
  163. inline void print(char x) { Ostream.out(x); }
  164. inline void println(char x) { Ostream.out(x); Ostream.out('\n'); }
  165. inline void print(ll x) { Ostream.print(x); }
  166. inline void println(ll x) { Ostream.println(x); }
  167. inline void print(double x, int y) { Ostream.print(x, y); }
  168. inline void println(double x, int y) { Ostream.println(x, y); }
  169. inline void print(char *s) { Ostream.print(s); }
  170. inline void println(char *s) { Ostream.println(s); }
  171. inline void println() { Ostream.out('\n'); }
  172. inline void flush() { Ostream.flush(); }
  173. #undef ll
  174. #undef OUT_SIZE
  175. #undef BUF_SIZE
  176. };
  177. //使用
  178. using namespace fastIO;
  179. int n;
  180. read(n);
  181. print(n);
  182. println(n);

参考

ASCII表

这里

ASCII表


常用数表

类型 数据
char -128 ~ 127
short -32768 ~ 32767
int -2147483648 ~ 2147483647(±2e9)
unsigned int -0 ~ 4294967295(4e9)
long long -9223372036854775808 ~ 9223372036854775807(±9e18)
unsigned long long 0 ~ 18446744073709551615(1e19)
double ± (1.7e-308 ~ 1.7e308)
long double ± (1.2e-4932 ~ 1.2e4932)
INF = 0x3f3f3f3f 1061109567
LINF = 0x3f3f3f3f3f3f3f3f 4557430888798830399

时间复杂度与数据规模

评测机每秒约

1MB内存约25万()个int(4个字节)


数学

常用网站


数学理论

负数求余

负数的求余数仍为负数,有正负时使用if (abs(x%2))或者if (x&1)判断是否为奇数


组合数

通项公式:

递推公式:

性质:











奇偶性: 对于 ,若 为奇数,否则为偶数。


错位排列数

将数字1~n排成一列,且数字i不在第i位的方案数:


威尔逊定理

当且仅当p为质数时,有


费马小定理

若p是质数,则对于任意整数a,有


费马大定理

当整数 时,方程

无正整数解


哥德巴赫猜想

任一大于2的偶数都可写成两个素数之和

任一大于5的奇数都可写成三个素数之和


勾股数

:


抽屉原理

原理一:把n+1个咕咕咕放到n个巢里,那么至少有两个咕咕咕在同一个巢里

原理二:把m*n-1个物体放入n个抽屉中,其中必定有一个抽屉中最多有m-1个物体 (例如:将3×5-1=14个物体放入5个抽屉中,则必定有一个抽屉中的物体数少于等于3-1=2)


欧拉公式

对于简单多面体(或者投射),点-边+面=2


欧几里德算法

最大公约数 GCD

  1. //欧几里德算法 gcd(a,b) == gcd(b,a%b)
  2. int gcd(int x, int y) { return y ? gcd(y, x%y) : x; }

扩展欧几里德算法 EXGCD

  1. //x,y为引用,返回值为gcd(a,b)
  2. int exgcd(int a, int b, int &x, int &y)
  3. {
  4. if (b == 0)
  5. {
  6. x = 1;
  7. y = 0;
  8. return a;
  9. }
  10. int r = exgcd(b, a%b, x, y);
  11. int t = y;
  12. y = x - (a / b) * y;
  13. x = t;
  14. return r;
  15. }

欧拉

欧拉函数

定义

对于一个正整数x,小于x且和x互质的正整数(包括1)的个数,记作


性质

对于质数p, ,且

对于质数p,有 ,则

对于奇数p,

对于一个正整数n,与其互质的数之和为

对于一个正整数n,对于所有n的正整数因子d (即 ),即

对于一个正整数n,且a为n的质因数,则:

,则

,则

积性函数:若m,n互质(即 ),则


求法
直接求
  1. //O(sqrt())
  2. int phi(int x)
  3. {
  4. int res = x, a = x;
  5. for (int i = 2; i*i <= a; i++)
  6. if (a%i == 0)
  7. {
  8. res = res / i * (i - 1);
  9. while (a%i == 0) a /= i;
  10. }
  11. if (a > 1) res = res / a * (a - 1);
  12. return res;
  13. }

线性筛法
  1. //较快,O(n)
  2. //更快的请参考杜教筛
  3. const static int MAXN = 50000 + 100;
  4. bool check[MAXN];
  5. int phi[MAXN] = { 0 }, prime[MAXN] = { 0 };
  6. void get_phi()
  7. {
  8. memset(check, false, sizeof(check));
  9. int tot = 0;
  10. phi[1] = 1;
  11. for (int i = 2; i <= MAXN - 100; ++i)
  12. {
  13. if (!check[i])
  14. {
  15. prime[tot++] = i;
  16. phi[i] = i - 1;
  17. }
  18. for (int j = 0; j < tot; ++j)
  19. {
  20. if (i * prime[j] > MAXN - 100) break;
  21. check[i * prime[j]] = true;
  22. if (i % prime[j] == 0)
  23. {
  24. phi[i * prime[j]] = phi[i] * prime[j];
  25. break;
  26. }
  27. else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
  28. }
  29. }
  30. }

递推法
  1. //较慢
  2. const static int MAXN = 50000 + 100;
  3. int phi[MAXN] = { 0 };
  4. void get_phi()
  5. {
  6. phi[1] = 1;
  7. for (int i = 2; i <= MAXN - 100; i++)
  8. if (!phi[i])
  9. for (int j = i; j <= MAXN - 100; j += i)
  10. {
  11. if (!phi[j]) phi[j] = j;
  12. phi[j] = phi[j] / i * (i - 1);
  13. }
  14. }

欧拉定理

若正整数a, n互质(),则


欧拉降幂

对于 ,有

对于 ,无需降幂。


欧拉路径

欧拉回路

每条边只经过一次,且回到起点


欧拉路径

每条边只经过一次,不要求回到起点。
- 无向图:连通(不考虑度为0的点),每个顶点度数都为偶数或者仅有两个点的度数为奇数。
- 有向图:基图连通(把边当成无向边,同样不考虑度为0的点),每个顶点出度等于入度或者有且仅有一个点的出度比入度多1,有且仅有一个点的出度比入度少1,其余的出度等于入度。
- 混合图:如果存在欧拉回路,一定存在欧拉路径,否则如果有且仅有两个点的(出度-入度)是奇数,那么给这两个点加边,判断是否存在欧拉回路,如果存在就一定存在欧拉路径。


杜教筛

  1. //积性函数,欧拉函数和莫比乌斯函数
  2. //复杂度O(n^2/3)~O(n^3/4)
  3. const int MAXN = 2000100;
  4. long long prime[MAXN];
  5. long long mu[MAXN];
  6. map<int, long long> ans_mu;
  7. void init()
  8. {
  9. fill(prime, prime + MAXN, 1);
  10. mu[1] = 1;
  11. int tot = 0;
  12. for (int i = 2; i < MAXN; i++)
  13. {
  14. if (prime[i])
  15. {
  16. prime[++tot] = i;
  17. mu[i] = -1;
  18. }
  19. for (int j = 1; j <= tot && i * prime[j] < MAXN; j++)
  20. {
  21. prime[i * prime[j]] = 0;
  22. if (i % prime[j] == 0)
  23. {
  24. mu[i * prime[j]] = 0;
  25. break;
  26. }
  27. else mu[i * prime[j]] = -mu[i];
  28. }
  29. }
  30. for (int i = 2; i < MAXN; i++) mu[i] += mu[i - 1];
  31. }
  32. long long calc_mu(int x)
  33. {
  34. if (x < MAXN) return mu[x];
  35. if (ans_mu.count(x)) return ans_mu[x];
  36. long long ans = 1;
  37. for (long long i = 2, j; i <= x; i = j + 1)
  38. {
  39. j = x / (x / i);
  40. ans -= (j - i + 1) * calc_mu(x / i);
  41. }
  42. return ans_mu[x] = ans;
  43. }
  44. long long calc_phi(int x)
  45. {
  46. long long ans = 0;
  47. for (long long i = 1, j; i <= x; i = j + 1)
  48. {
  49. j = x / (x / i);
  50. ans += (x / i) * (x / i) * (calc_mu(j) - calc_mu(i - 1));
  51. }
  52. return ((ans - 1) >> 1) + 1;
  53. }

扩展大步小步 Baby Steps Giant Steps

用于求解高次同余方程,即求解

普通版要求m为质数(或者a与m互质),如果x有解,则 ;扩展版无要求

下列代码数据范围

  1. //北上广深算法
  2. const long long MOD = 1313131;
  3. const long long MAXN = 500000 + 5; // sqrt(p)
  4. long long gcd(long long x, long long y) { return y ? gcd(y, x%y) : x; }
  5. void Exgcd(long long a, long long b, long long &d, long long &x, long long &y)
  6. {
  7. if (!b)
  8. {
  9. d = a;
  10. x = 1;
  11. y = 0;
  12. }
  13. else
  14. {
  15. Exgcd(b, a % b, d, y, x);
  16. y -= x * (a / b);
  17. }
  18. }
  19. long long qkpow(long long a, long long b, long long m)//O(logN) a^b%m
  20. {
  21. long long ans = 1;
  22. a %= m;
  23. while (b)
  24. {
  25. if (b & 1) ans = (ans*a) % m;
  26. a = (a*a) % m;
  27. b >>= 1;
  28. }
  29. return ans % m;
  30. }
  31. struct Hashset
  32. {
  33. long long head[MOD], Next[MAXN], f[MAXN], v[MAXN], ind;
  34. void reset()
  35. {
  36. ind = 0;
  37. memset(head, -1, sizeof head);
  38. }
  39. void Insert(long long x, long long _v)
  40. {
  41. long long ins = x % MOD;
  42. for (long long j = head[ins]; j != -1; j = Next[j])
  43. if (f[j] == x)
  44. {
  45. v[j] = min(v[j], _v);
  46. return;
  47. }
  48. f[ind] = x, v[ind] = _v;
  49. Next[ind] = head[ins], head[ins] = ind++;
  50. }
  51. long long operator [] (const long long &x) const
  52. {
  53. long long ins = x % MOD;
  54. for (long long j = head[ins]; j != -1; j = Next[j])
  55. if (f[j] == x) return v[j];
  56. return -1;
  57. }
  58. } S;
  59. long long Solve(long long a, long long b, long long c)
  60. {
  61. long long d, x, y;
  62. Exgcd(a, c, d, x, y);
  63. x = (x + c) % c;
  64. return x * b % c;
  65. }
  66. long long BSGS(long long C, long long A, long long B, long long p) // A^x%p=B S.T.(A,p)=1
  67. {
  68. if (p <= 100)
  69. {
  70. long long d = 1;
  71. for (int i = 0; i < p; ++i)
  72. {
  73. if (d == B) return i;
  74. d = d * A % p;
  75. }
  76. return -1;
  77. }
  78. else
  79. {
  80. long long m = (int)sqrt(p);
  81. S.reset();
  82. long long d = 1, Search;
  83. for (int i = 0; i < m; ++i)
  84. {
  85. S.Insert(d, i);
  86. d = d * A % p;
  87. }
  88. for (int i = 0; i * m < p; i++)
  89. {
  90. d = qkpow(A, i * m, p) * C % p;
  91. Search = S[Solve(d, B, p)];
  92. if (Search != -1) return i * m + Search;
  93. }
  94. return -1;
  95. }
  96. }
  97. int main()
  98. {
  99. long long a, b, m;
  100. int T;
  101. cin >> T;
  102. while (T--)
  103. {
  104. cin >> a >> b >> m;
  105. long long d = 1;
  106. bool find = 0;
  107. for (long long i = 0; i < 100; i++)
  108. {
  109. if (d == b)
  110. {
  111. cout << i << endl;
  112. find = 1;
  113. break;
  114. }
  115. d = d * a % m;
  116. }
  117. if (find) continue;
  118. long long t, C = 1, num = 0;
  119. while ((t = gcd(a, m)) != 1)
  120. {
  121. m /= t;
  122. b /= t;
  123. C = C * a / t % m;
  124. num++;
  125. }
  126. long long res = BSGS(C, a, b, m);
  127. if (res == -1) cout << "No Solution" << endl;
  128. else cout << res + num << endl;
  129. }
  130. return 0;
  131. }

二次剩余

求二次同余方程的解 ,其中 为奇质数:

  1. long long quick_mod(long long a, long long b, long long m)
  2. {
  3. long long ans = 1;
  4. a %= m;
  5. while (b)
  6. {
  7. if (b & 1)
  8. {
  9. ans = ans * a % m;
  10. b--;
  11. }
  12. b >>= 1;
  13. a = a * a % m;
  14. }
  15. return ans;
  16. }
  17. struct T
  18. {
  19. long long p, d;
  20. };
  21. long long w;
  22. //二次域乘法
  23. T multi_er(T a, T b, long long m)
  24. {
  25. T ans;
  26. ans.p = (a.p * b.p % m + a.d * b.d % m * w % m) % m;
  27. ans.d = (a.p * b.d % m + a.d * b.p % m) % m;
  28. return ans;
  29. }
  30. //二次域上快速幂
  31. T power(T a, long long b, long long m)
  32. {
  33. T ans;
  34. ans.p = 1;
  35. ans.d = 0;
  36. while (b)
  37. {
  38. if (b & 1)
  39. {
  40. ans = multi_er(ans, a, m);
  41. b--;
  42. }
  43. b >>= 1;
  44. a = multi_er(a, a, m);
  45. }
  46. return ans;
  47. }
  48. //求勒让德符号
  49. long long Legendre(long long a, long long p) { return quick_mod(a, (p - 1) >> 1, p); }
  50. long long mod(long long a, long long m)
  51. {
  52. a %= m;
  53. if (a < 0) a += m;
  54. return a;
  55. }
  56. long long Solve(long long n, long long p)
  57. {
  58. if (p == 2) return 1;
  59. if (Legendre(n, p) + 1 == p) return -1;
  60. long long a = -1, t;
  61. srand(time(nullptr));
  62. while (true)
  63. {
  64. a = rand() % p;
  65. t = a * a - n;
  66. w = mod(t, p);
  67. if (Legendre(w, p) + 1 == p) break;
  68. }
  69. T tmp;
  70. tmp.p = a;
  71. tmp.d = 1;
  72. T ans = power(tmp, (p + 1) >> 1, p);
  73. return ans.p;
  74. }
  75. int main()
  76. {
  77. // x*x = a (mod n)
  78. long long a, n;
  79. cin >> a >> n;
  80. a %= n;
  81. auto ans1 = Solve(a, n);
  82. auto ans2 = n - ans1;
  83. if (ans1 == -1) cout << "No root" << endl;
  84. else if (ans1 == ans2) cout << ans1 << endl;
  85. else cout << ans1 << " " << ans2 << endl;
  86. return 0;
  87. }

快速傅里叶变换 FFT

多项式乘法

  1. //计算多项式乘法F(x)*G(x)
  2. /*
  3. 输入
  4. 第一行2个正整数n, m
  5. 第二行n + 1个数字,从低到高表示F(x)的系数
  6. 第三行m + 1个数字,从低到高表示G(x)的系数
  7. 例子:
  8. 1 2
  9. 1 2
  10. 1 2 1
  11. 输出
  12. 一行n+m+1个数字,从低到高表示F(x)∗G(x)的系数
  13. 例子:
  14. 1 4 5 2
  15. F(x) = 1 + 2*x
  16. G(x) = 1 + 2*x + x^2
  17. F(x)*G(x) = 1 + 4*x + 5*x^2 + 2*x^3
  18. */
  19. #define rg register int
  20. const int MAXN = 10000001;
  21. const double pi = acos(-1);
  22. struct Complex
  23. {
  24. double r, i;
  25. Complex() {}
  26. Complex(double a, double b) :r(a), i(b) {}
  27. Complex operator + (const Complex B) const { return Complex(r + B.r, i + B.i); }
  28. Complex operator - (const Complex B) const { return Complex(r - B.r, i - B.i); }
  29. Complex operator * (const Complex B) const { return Complex(r*B.r - i * B.i, r*B.i + i * B.r); }
  30. };
  31. Complex X, Y, a[MAXN], b[MAXN];
  32. int r[MAXN], n, m, l;
  33. inline void FFT(Complex *a, int x)
  34. {
  35. for (rg i = 0; i < n; i++)
  36. if (i < r[i]) swap(a[i], a[r[i]]);
  37. for (rg i = 1; i < n; i <<= 1)
  38. {
  39. Complex wn(cos(pi / i), x*sin(pi / i));
  40. for (rg j = 0; j < n; j += (i << 1))
  41. {
  42. Complex w(1, 0);
  43. for (rg k = 0; k < i; ++k, w = w * wn)
  44. {
  45. X = a[j + k], Y = a[i + j + k] * w;
  46. a[j + k] = X + Y, a[i + j + k] = X - Y;
  47. }
  48. }
  49. }
  50. if (x == -1)
  51. for (rg i = 0; i < n; i++) a[i].r = a[i].r / n;
  52. }
  53. int main()
  54. {
  55. scanf("%d%d", &n, &m);
  56. for (rg i = 0; i <= n; i++) scanf("%lf", &a[i].r);
  57. for (rg i = 0; i <= m; i++) scanf("%lf", &b[i].r);
  58. m += n;
  59. for (n = 1; n <= m; n <<= 1) l++;
  60. for (rg i = 0; i < n; i++)
  61. r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  62. FFT(a, 1);
  63. FFT(b, 1);
  64. for (rg i = 0; i <= n; i++) a[i] = a[i] * b[i];
  65. FFT(a, -1);
  66. for (rg i = 0; i <= m; i++)
  67. printf("%d ", (int)(a[i].r + 0.5));
  68. return 0;
  69. }

相同位数整数乘法

  1. /*
  2. 输入
  3. 位数
  4. 整数1
  5. 整数2
  6. */
  7. #define rg register int
  8. const int MAXN = 1000001;
  9. const long double pi = acos(-1);
  10. struct Complex
  11. {
  12. double r, i;
  13. Complex() {}
  14. Complex(double a, double b) :r(a), i(b) {}
  15. Complex operator + (const Complex B) const { return Complex(r + B.r, i + B.i); }
  16. Complex operator - (const Complex B) const { return Complex(r - B.r, i - B.i); }
  17. Complex operator * (const Complex B) const { return Complex(r*B.r - i * B.i, r*B.i + i * B.r); }
  18. };
  19. Complex X, Y, a[MAXN], b[MAXN];
  20. int n, m, l, r[MAXN];
  21. inline void FFT(Complex *a, int x)
  22. {
  23. for (rg i = 0; i < n; i++)
  24. if (i < r[i]) swap(a[i], a[r[i]]);
  25. for (rg i = 1; i < n; i <<= 1)
  26. {
  27. Complex wn(cos(pi / i), x*sin(pi / i));
  28. for (rg j = 0; j < n; j += (i << 1))
  29. {
  30. Complex w(1, 0);
  31. for (rg k = 0; k < i; ++k, w = w * wn)
  32. {
  33. X = a[j + k], Y = a[i + j + k] * w;
  34. a[j + k] = X + Y, a[i + j + k] = X - Y;
  35. }
  36. }
  37. }
  38. if (x == -1) for (rg i = 0; i < n; i++) a[i].r = a[i].r / n;
  39. }
  40. char ch1[MAXN], ch2[MAXN];
  41. int res[MAXN];
  42. int main()
  43. {
  44. scanf("%d", &n);
  45. cin >> ch1;
  46. cin >> ch2;
  47. for (rg i = 0; i < n; i++)
  48. {
  49. a[i].r = ch1[n - i - 1] - '0';
  50. b[i].r = ch2[n - i - 1] - '0';
  51. }
  52. m = n + n - 2;
  53. for (n = 1; n <= m; n <<= 1) l++;
  54. for (rg i = 0; i < n; i++)
  55. r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
  56. FFT(a, 1);
  57. FFT(b, 1);
  58. for (rg i = 0; i <= n; i++) a[i] = a[i] * b[i];
  59. FFT(a, -1);
  60. for (rg i = 0; i <= m; i++) res[i] = (int)(a[i].r + 0.5);
  61. for (rg i = 0; i <= m; i++) res[i + 1] += res[i] / 10, res[i] %= 10;
  62. rg top = m + 1;
  63. while (res[top] > 9)
  64. {
  65. res[top + 1] = res[top] / 10;
  66. res[top] %= 10;
  67. top++;
  68. }
  69. while (!res[top]) top--;
  70. for (rg i = top; i >= 0; i--)
  71. printf("%d", res[i]);
  72. return 0;
  73. }

任意整数乘法

  1. //较复杂
  2. //时间较慢
  3. const int maxn = 500100; //至少是数据长度的4倍
  4. const double PI = acos(-1.0);
  5. struct Complex
  6. {
  7. double r, i;
  8. Complex(double _r = 0.0, double _i = 0.0) { r = _r; i = _i; }
  9. Complex operator + (const Complex &b) { return Complex(r + b.r, i + b.i); }
  10. Complex operator - (const Complex &b) { return Complex(r - b.r, i - b.i); }
  11. Complex operator * (const Complex &b) { return Complex(r*b.r - i * b.i, r*b.i + i * b.r); }
  12. };
  13. void change(Complex y[], int len)
  14. {
  15. int k;
  16. for (int i = 1, j = len / 2; i < len - 1; i++)
  17. {
  18. if (i < j) swap(y[i], y[j]);
  19. k = len / 2;
  20. while (j >= k)
  21. {
  22. j -= k;
  23. k /= 2;
  24. }
  25. if (j < k) j += k;
  26. }
  27. }
  28. //做FFT,len必须为2^k形式,on==1时是DFT,on==-1时是IDFT
  29. void fft(Complex y[], int len, int on)
  30. {
  31. change(y, len);
  32. for (int h = 2; h <= len; h <<= 1)
  33. {
  34. Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h));
  35. for (int j = 0; j < len; j += h)
  36. {
  37. Complex w(1, 0);
  38. for (int k = j; k < j + h / 2; k++)
  39. {
  40. Complex u = y[k];
  41. Complex t = w * y[k + h / 2];
  42. y[k] = u + t;
  43. y[k + h / 2] = u - t;
  44. w = w * wn;
  45. }
  46. }
  47. }
  48. if (on == -1)
  49. for (int i = 0; i < len; i++) y[i].r /= len;
  50. }
  51. char num1[maxn], num2[maxn];
  52. Complex x1[maxn], x2[maxn];
  53. int ans[maxn];
  54. int main()
  55. {
  56. while (cin >> num1 >> num2)
  57. {
  58. memset(ans, 0, sizeof(ans));
  59. int len = 1, len1 = strlen(num1), len2 = strlen(num2);
  60. while (len < len1 + len2 + 1) len <<= 1;
  61. for (int i = 0; i < len1; i++) x1[len1 - 1 - i] = Complex((double)(num1[i] - '0'), 0);
  62. for (int i = len1; i < len; i++) x1[i] = Complex(0, 0);
  63. fft(x1, len, 1);
  64. for (int i = 0; i < len2; i++) x2[len2 - 1 - i] = Complex((double)(num2[i] - '0'), 0);
  65. for (int i = len2; i < len; i++) x2[i] = Complex(0, 0);
  66. fft(x2, len, 1);
  67. for (int i = 0; i < len; i++) x1[i] = x1[i] * x2[i];
  68. fft(x1, len, -1);
  69. for (int i = 0; i < len; i++) ans[i] = (int)(x1[i].r + 0.5);
  70. // 进位
  71. for (int i = 1; i < len; i++)
  72. {
  73. ans[i] += ans[i - 1] / 10;
  74. ans[i - 1] %= 10;
  75. }
  76. while (len > 0 && !ans[len]) len--;
  77. for (int i = len; i >= 0; i--) printf("%c", ans[i] + '0');
  78. printf("\n");
  79. }
  80. return 0;
  81. }

快速幂

  1. //O(logN) a^b%m
  2. long long qkpow(long long a, long long b, const long long m)
  3. {
  4. long long ans = 1;
  5. a %= m;
  6. while (b)
  7. {
  8. if (b & 1) ans = (ans*a) % m;
  9. a = (a*a) % m;
  10. b >>= 1;
  11. }
  12. return ans % m;
  13. }

斐波那契数列

通项:

  1. // 求第n项,模mod
  2. #define mod(a, m) ((a) % (m) + (m)) % (m)
  3. const int MOD = 1e9 + 9;
  4. struct MATRIX
  5. {
  6. long long a[2][2];
  7. };
  8. MATRIX a;
  9. long long f[2];
  10. void ANS_Cf(MATRIX a)
  11. {
  12. f[0] = mod(a.a[0][0] + a.a[1][0], MOD);
  13. f[1] = mod(a.a[0][1] + a.a[1][1], MOD);
  14. }
  15. MATRIX MATRIX_Cf(MATRIX a, MATRIX b)
  16. {
  17. MATRIX ans;
  18. int k;
  19. for (int i = 0; i < 2; i++)
  20. {
  21. for (int j = 0; j < 2; j++)
  22. {
  23. ans.a[i][j] = 0;
  24. k = 0;
  25. while (k < 2)
  26. {
  27. ans.a[i][j] += a.a[k][i] * b.a[j][k];
  28. ans.a[i][j] = mod(ans.a[i][j], MOD);
  29. ++k;
  30. }
  31. }
  32. }
  33. return ans;
  34. }
  35. MATRIX MATRIX_Pow(MATRIX a, long long n)
  36. {
  37. MATRIX ans;
  38. ans.a[0][0] = 1;
  39. ans.a[1][1] = 1;
  40. ans.a[0][1] = 0;
  41. ans.a[1][0] = 0;
  42. while (n)
  43. {
  44. if (n & 1) ans = MATRIX_Cf(ans, a);
  45. n = n >> 1;
  46. a = MATRIX_Cf(a, a);
  47. }
  48. return ans;
  49. }
  50. int fib(long long n)
  51. {
  52. if (n == 1) return 1;
  53. a.a[0][0] = a.a[0][1] = a.a[1][0] = 1;
  54. a.a[1][1] = 0;
  55. a = MATRIX_Pow(a, n - 2);
  56. ANS_Cf(a);
  57. return f[0];
  58. }

素数

试商法

  1. //试商法
  2. bool isPrime(const int x)
  3. {
  4. if (x < 2) return false;
  5. for (auto i = 2; i * i <= x; i++)
  6. if (x % i == 0) return false;
  7. return true;
  8. }

打表法

  1. //O(n*loglogn)
  2. const auto n = 1000;
  3. int a[n + 5] = {1, 1};
  4. vector<int> v;
  5. for (auto i = 2; i <= n; i++)
  6. for (auto j = i * 2; j <= n; j += i) a[j] = 1;
  7. for (auto i = 1; i <= n; i++)
  8. if (a[i] == 0) v.emplace_back(i); // 素数 a[i]==0

素因子

直接求

  1. // 查询数的所有不重复素因子
  2. // 暴力 O(sqrt(n))
  3. void getf(vector<int> &v, int x)
  4. {
  5. for (int i = 2; i * i <= x; i++)
  6. {
  7. if (x % i == 0)
  8. {
  9. v.push_back(i);
  10. while (x % i == 0) x /= i;
  11. }
  12. if (x == 1) break;
  13. }
  14. if (x != 1) v.push_back(x);
  15. }
  16. // 对数进行分解质因数
  17. void getf(vector<int> &v, int x)
  18. {
  19. for (int i = 2; i * i <= x; i++)
  20. {
  21. while (x % i == 0)
  22. {
  23. v.push_back(i);
  24. x /= i;
  25. }
  26. if (x == 1) break;
  27. }
  28. if (x != 1) v.push_back(x);
  29. }

打表法

  1. // 筛每个数的最小素因子
  2. // 预处理 O(nloglogn)
  3. const int MAXN = 100000 + 50;
  4. int spf[MAXN];
  5. void init_spf()
  6. {
  7. for (int i = 2; i < MAXN - 5; i++)
  8. {
  9. if (!spf[i])
  10. {
  11. for (int j = i; j < MAXN - 5; j += i)
  12. {
  13. if (!spf[j]) spf[j] = i;
  14. }
  15. }
  16. }
  17. }
  18. // O(logn)
  19. // 查询数的所有不重复素因子
  20. void getf(vector<int> &v, int x)
  21. {
  22. while (x > 1)
  23. {
  24. int p = spf[x];
  25. v.push_back(p);
  26. while (x % p == 0) x /= p;
  27. }
  28. }
  29. // 对数进行分解质因数
  30. void getf(vector<int> &v, int x)
  31. {
  32. while (x > 1)
  33. {
  34. int p = spf[x];
  35. while (x % p == 0)
  36. {
  37. v.push_back(p);
  38. x /= p;
  39. }
  40. }
  41. }

逆元

定义

如果有 (a与p互质),则称b是模p意义下a的乘法逆元,记

(定义了模意义下的除法运算:除以一个数取模等于乘以这个数的逆元取模)


求法

费马小定理

由费马小定理得

当模数p为质数时, 即为a在模p意义下的逆元,快速幂求解即可,时间复杂度O(logn)

  1. //模数MOD为质数
  2. const long long MOD = 1e9 + 7;
  3. long long powMod(long long a, long long b)
  4. {
  5. long long ans = 1;
  6. for (a %= MOD; b; b >>= 1)
  7. {
  8. if (b & 1) ans = ans * a % MOD;
  9. a = a * a % MOD;
  10. }
  11. return ans;
  12. }
  13. long long inv(long long x) { return powMod(x, MOD - 2); }

扩展欧几里得法
  1. //扩展欧几里得法,gcd(a, MOD) = 1时有逆元
  2. //O(logn)
  3. const long long MOD = 1e9 + 7;
  4. long long exgcd(long long a, long long b, long long &x, long long &y)
  5. {
  6. if (b == 0)
  7. {
  8. x = 1;
  9. y = 0;
  10. return a;
  11. }
  12. long long d = exgcd(b, a % b, y, x);
  13. y -= a / b * x;
  14. return d;
  15. }
  16. long long inv(long long a)
  17. {
  18. long long x, y;
  19. long long d = exgcd(a, MOD, x, y);
  20. if (d == 1) return (x % MOD + MOD) % MOD;
  21. else return -1;
  22. }

打表法
  1. const long long MOD = 1e9 + 7;
  2. long long inv[10000];
  3. void initInv()
  4. {
  5. inv[1] = 1;
  6. for (int i = 2; i < 10000; i++)
  7. {
  8. inv[i] = 1LL * (MOD - MOD / i) * inv[MOD % i] % MOD;
  9. }
  10. }

中国剩余定理

孙子定理:有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

求解同余方程组

其中 为两两互质的整数

的最小非负整数解

解:
,即 是所有 的最小公倍数

的逆元,即 的最小非负整数解

则有一个解为

通解为

特别的,最小非负整数解为

  1. int china()
  2. {
  3. int k; // 方程组数
  4. vector<int> m; //方程中的m
  5. vector<int> a; //方程中的a
  6. int ans = 0, lcm = 1, x, y;
  7. for (int i = 1; i <= k; ++i) lcm *= m[i];
  8. for (int i = 1; i <= k; ++i)
  9. {
  10. int tp = lcm / m[i];
  11. exgcd(tp, m[i], x, y);
  12. x = (x % m[i] + m[i]) % m[i]; //x要为最小非负整数解
  13. ans = (ans + tp * x * a[i]) % lcm;
  14. }
  15. return (ans + lcm) % lcm;
  16. }

整数运算

大整数

  1. //2的n次方可以用pow直接算
  2. //UTF-8 使用限定
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <cstdlib>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <list>
  9. #include <map>
  10. #include <cstring>
  11. #include <string>
  12. #include <iostream>
  13. #include <fstream>
  14. #include <cmath>
  15. using namespace std;
  16. #define BIGNUM_DEBUG 2333
  17. class Bignum
  18. {
  19. void mknum(const char *s, int len = -1)
  20. {
  21. sign = 0;
  22. if (*s == '-')
  23. {
  24. mknum(s + 1);
  25. sign = 1;
  26. return;
  27. }
  28. int l;
  29. if (len == -1) l = strlen(s);
  30. else l = len;
  31. l = strlen(s);
  32. bits.clear();
  33. bits.resize(l);
  34. for (int i = l - 1; i >= 0; i--) bits[l - i - 1] = s[i] - '0';
  35. maintain();
  36. }
  37. void mknum(string &s) { mknum(s.c_str(), s.length()); }
  38. ///////////////////////////////////////////////////////////////////
  39. void us_addto(Bignum &b) // unsigned add to
  40. {
  41. int mlen = max(b.bits.size(), bits.size());
  42. int slen = bits.size();
  43. int olen = b.bits.size();
  44. bits.resize(mlen);
  45. for (int i = 0; i < mlen; i++)
  46. {
  47. int s = 0;
  48. if (i < slen)s += bits[i];
  49. if (i < olen)s += b.bits[i];
  50. bits[i] = s;
  51. }
  52. maintain();
  53. }
  54. class FFTer
  55. {
  56. class Complex
  57. {
  58. public:
  59. double real, image;
  60. Complex(double a = 0, double b = 0)
  61. {
  62. real = a;
  63. image = b;
  64. }
  65. Complex operator + (const Complex &o) { return Complex(real + o.real, image + o.image); }
  66. Complex operator - (const Complex &o) { return Complex(real - o.real, image - o.image); }
  67. Complex operator * (const Complex &o) { return Complex(real*o.real - image * o.image, real*o.image + o.real*image); }
  68. Complex operator * (double k) { return Complex(real*k, image*k); }
  69. Complex operator / (double k) { return Complex(real / k, image / k); }
  70. };
  71. public:
  72. vector<Complex> a; //系数向量
  73. int n; //多项式次数上界
  74. FFTer(vector<int> &vec)
  75. {
  76. a.resize(vec.size());
  77. for (int i = 0; i < vec.size(); i++) a[i].real = vec[i];
  78. n = vec.size();
  79. }
  80. void transform()
  81. {
  82. int j = 0;
  83. int k;
  84. for (int i = 0; i < n; i++)
  85. {
  86. if (j > i) swap(a[i], a[j]);
  87. k = n;
  88. while (j & (k >>= 1)) j &= ~k;
  89. j |= k;
  90. }
  91. }
  92. void FFT(bool IDFT = false)
  93. {
  94. const double Pi = IDFT ? -acos(-1.0) : acos(-1.0);
  95. //IDFT与DFT选择方向相反(符号相反)
  96. transform();//交换元素(翻转二进制位,具体看下面注释,再具体看算导
  97. for (int s = 1; s < n; s <<= 1)
  98. //算法导论上是fot s = 1 to lgn,考虑到精度问题改为上面那个...
  99. for (int t = 0; t < n; t += s << 1)
  100. {
  101. //合并[t, t+s-1]与 [t+s, t+2*s-1] (算导上以指数形式给出,注意到他的s....)
  102. //合并为[t, t+2*s-1] (看起来像是废话) (有示例图在算导上,画得很形象的)
  103. double x = Pi / s;
  104. Complex omgn(cos(x), sin(x));
  105. Complex omg(1.0, 0.0); //单位向量
  106. for (int m = 0; m < s; m++)
  107. { //旋转
  108. int a1 = m + t;
  109. int a2 = m + t + s; //取两边系数向量的系数
  110. //算导上管这个叫公共子表达式消除
  111. //其实就是一个变量计算一次然后保存下来用多次
  112. Complex comm = omg * a[a2];
  113. a[a2] = a[a1] - comm;
  114. a[a1] = a[a1] + comm; //这两个顺序不要反了
  115. omg = omg * omgn;
  116. }
  117. }
  118. if (IDFT)
  119. for (int i = 0; i < n; i++) a[i] = a[i] / n;
  120. }
  121. void mul(FFTer &o)
  122. {
  123. int s = 1;
  124. while (s < n + o.n)s <<= 1;
  125. n = o.n = s;
  126. a.resize(s);
  127. o.a.resize(s);
  128. FFT(false);
  129. o.FFT(false);
  130. for (int i = 0; i < n; i++) a[i] = a[i] * o.a[i];
  131. FFT(true);
  132. }
  133. };
  134. void us_multo(Bignum &b)
  135. {
  136. FFTer x(bits);
  137. FFTer y(b.bits);
  138. x.mul(y);
  139. bits.clear();
  140. bits.resize(x.a.size());
  141. for (int i = 0; i < x.n; i++) bits[i] = (int)(x.a[i].real + 0.5);
  142. maintain();
  143. }
  144. void us_multo_simu(Bignum &b)
  145. {
  146. vector<int> r;
  147. r.resize(max(length(), b.length()) << 1);
  148. for (int i = 0; i < length(); i++)
  149. for (int j = 0; j < b.length(); j++) r[i + j] += bits[i] * b.bits[j];
  150. *(&(this->bits)) = r;
  151. maintain();
  152. }
  153. void us_subto(Bignum &b) // abs(self) >= abs(other)
  154. {
  155. int mlen = length();
  156. int olen = b.length();
  157. for (int i = 0; i < mlen; i++)
  158. {
  159. int s = bits[i];
  160. if (i < olen) s -= b.bits[i];
  161. bits[i] = s;
  162. if (bits[i] < 0)
  163. {
  164. bits[i] += 10;
  165. bits[i + 1] -= 1;
  166. }
  167. }
  168. for (int i = bits.size() - 1; !bits[i] && i >= 1; i--) bits.pop_back();
  169. if (bits.size() == 1 && bits[0] == 0) sign = 0;
  170. }
  171. void us_divto(Bignum &b)
  172. {
  173. if (length() == 1 && bits[0] == 0) return;
  174. Bignum L("0");
  175. L.sign = 0;
  176. Bignum R(*this);
  177. R.sign = 0;
  178. Bignum two("2");
  179. R *= two;
  180. Bignum one("1");
  181. one.sign = 0;
  182. while (L + one != R)
  183. {
  184. Bignum M = L + R;
  185. M.divto2();
  186. Bignum t = M * b;
  187. if (t > *this) R = M;
  188. else if (t < *this) L = M;
  189. else
  190. {
  191. *this = M;
  192. L = M;
  193. break;
  194. }
  195. }
  196. *this = L;
  197. }
  198. public:
  199. int sign;
  200. vector<int> bits;
  201. int length() { return bits.size(); }
  202. void maintain()
  203. {
  204. for (int i = 0; i < bits.size(); i++)
  205. {
  206. if (i + 1 < bits.size()) bits[i + 1] += bits[i] / 10;
  207. else if (bits[i] > 9) bits.push_back(bits[i] / 10);
  208. bits[i] %= 10;
  209. }
  210. if (bits.size() == 0)
  211. {
  212. bits.push_back(0);
  213. sign = 0;
  214. }
  215. for (int i = bits.size() - 1; !bits[i] && i >= 1; i--) bits.pop_back();
  216. }
  217. Bignum(string &s)
  218. {
  219. Bignum();
  220. mknum(s);
  221. }
  222. Bignum(const char *s)
  223. {
  224. Bignum();
  225. mknum(s);
  226. }
  227. Bignum(int n)
  228. {
  229. Bignum();
  230. char buf[15];
  231. sprintf(buf, "%d", n);
  232. mknum(buf);
  233. }
  234. Bignum()
  235. {
  236. sign = 0;
  237. bits.push_back(0);
  238. }
  239. Bignum(const Bignum& b)
  240. {
  241. copy(b);
  242. }
  243. void copy(const Bignum& b)
  244. {
  245. sign = b.sign;
  246. bits = b.bits;
  247. }
  248. ///////////////////////////////////////////////////
  249. bool us_cmp(Bignum &b) //无符号的比较
  250. {
  251. if (length() != b.length()) return false;
  252. int l = length();
  253. for (int i = 0; i < l; i++)
  254. if (bits[i] != b.bits[i]) return false;
  255. return true;
  256. }
  257. bool us_larger(Bignum &b)
  258. {
  259. if (length() > b.length()) return true;
  260. else if (length() < b.length()) return false;
  261. int l = length();
  262. for (int i = l - 1; i >= 0; i--)
  263. if (bits[i] > b.bits[i]) return true;
  264. else if (bits[i] < b.bits[i]) return false;
  265. return false;
  266. }
  267. bool operator == (Bignum &o)
  268. {
  269. if (sign != o.sign) return false;
  270. return us_cmp(o);
  271. }
  272. bool operator != (Bignum &o) { return !(*this == o); }
  273. bool operator > (Bignum &o)
  274. {
  275. if (sign == 0 && o.sign == 1) return true;
  276. if (sign == 1 && o.sign == 0) return false;
  277. if (sign == o.sign && sign) return !us_larger(o);
  278. return us_larger(o);
  279. }
  280. bool operator < (Bignum &o)
  281. {
  282. return !(*this == o || *this > o); //小于就是不等于也不大于
  283. }
  284. bool operator <= (Bignum &o)
  285. {
  286. return *this < o || *this == o;
  287. }
  288. bool operator >= (Bignum &o)
  289. {
  290. return *this > o || *this == o;
  291. }
  292. ////////////////////////////////////////////////////
  293. Bignum& operator += (Bignum &o)
  294. {
  295. if (!sign && !o.sign)
  296. {
  297. us_addto(o);
  298. sign = 0;
  299. }
  300. else if (sign && o.sign)
  301. {
  302. us_addto(o);
  303. sign = 1;
  304. }
  305. else if (sign && !o.sign)
  306. {
  307. if (o.us_larger(*this))
  308. {
  309. Bignum t(o);
  310. t.us_subto(*this);
  311. *this = t;
  312. sign = 0;
  313. }
  314. else
  315. {
  316. us_subto(o);
  317. sign = 1;
  318. if (bits.size() == 1 && bits[0] == 0) sign = 0;
  319. }
  320. }
  321. else if (!sign && o.sign)
  322. {
  323. if (us_larger(o))
  324. {
  325. us_subto(o);
  326. sign = 0;
  327. }
  328. else
  329. {
  330. Bignum t(o);
  331. t.us_subto(*this);
  332. *this = t;
  333. sign = 1;
  334. if (bits.size() == 1 && bits[0] == 0) sign = 0;
  335. }
  336. }
  337. return *this;
  338. }
  339. Bignum operator + (Bignum &o)
  340. {
  341. Bignum t(*this);
  342. t += o;
  343. return t;
  344. }
  345. /////////////////////////////////////////////////
  346. Bignum& operator*= (Bignum &o)
  347. {
  348. if (length() + o.length() > 800) us_multo(o); //FFT
  349. else us_multo_simu(o); //simulate
  350. if (sign == o.sign) sign = 0;
  351. else sign = 1;
  352. return *this;
  353. }
  354. Bignum operator* (Bignum &o)
  355. {
  356. Bignum t(*this);
  357. t *= o;
  358. return t;
  359. }
  360. ////////////////////////////////////////////////
  361. Bignum& operator-= (Bignum &o)
  362. {
  363. if (!sign && !o.sign)
  364. {
  365. if (us_larger(o))
  366. {
  367. us_subto(o);
  368. sign = 0;
  369. }
  370. else
  371. {
  372. Bignum t(o);
  373. t.us_subto(*this);
  374. *this = t;
  375. sign = 1;
  376. if (bits.size() == 1 && bits[0] == 0) sign = 0;
  377. }
  378. }
  379. else if (sign && o.sign)
  380. {
  381. if (us_larger(o))
  382. {
  383. us_subto(o);
  384. sign = 1;
  385. if (bits.size() == 1 && bits[0] == 0) sign = 0;
  386. }
  387. else
  388. {
  389. Bignum t(o);
  390. t.us_subto(*this);
  391. *this = t;
  392. sign = 0;
  393. }
  394. }
  395. else if (!sign && o.sign)
  396. {
  397. us_addto(o);
  398. sign = 0;
  399. }
  400. else if (sign && !o.sign)
  401. {
  402. us_addto(o);
  403. sign = 1;
  404. }
  405. return *this;
  406. }
  407. Bignum operator - (Bignum &o)
  408. {
  409. Bignum t(*this);
  410. t -= o;
  411. return t;
  412. }
  413. ///////////////////////////////////////////////
  414. Bignum& divto2()
  415. {
  416. if (!bits.size()) return *this;
  417. bits[0] >>= 1;
  418. int i;
  419. for (i = 1; i < bits.size(); i++)
  420. {
  421. if (bits[i] & 1) bits[i - 1] += 5;
  422. bits[i] >>= 1;
  423. }
  424. if (bits[i - 1] == 0) bits.pop_back();
  425. return *this;
  426. }
  427. Bignum& operator /= (Bignum &o)
  428. {
  429. us_divto(o);
  430. if (sign == o.sign) sign = 0;
  431. else sign = 1;
  432. return *this;
  433. }
  434. Bignum operator / (Bignum &o)
  435. {
  436. Bignum t(*this);
  437. t /= o;
  438. return t;
  439. }
  440. //////////////////////////////////////////
  441. Bignum abs()
  442. {
  443. Bignum t(*this);
  444. t.sign = 0;
  445. return t;
  446. }
  447. Bignum sqrt()
  448. {
  449. Bignum L("0"), R(*this);
  450. Bignum one("1");
  451. Bignum m, t;
  452. while (L + one != R)
  453. {
  454. m = L + R;
  455. m.divto2();
  456. Bignum t = m * m;
  457. if (t == *this) return m;
  458. else if (t > *this) R = m;
  459. else L = m;
  460. }
  461. return L;
  462. }
  463. //若e <= 0则会返回1
  464. //底数(也就是this)是负数的话会根据次数决定符号
  465. Bignum pow(Bignum &e) //a^b == a.pow(b)
  466. {
  467. if (e.sign)return 1;
  468. Bignum ans("1");
  469. Bignum base(*this);
  470. Bignum zero("0");
  471. Bignum exp(e);
  472. while (exp > zero)
  473. {
  474. if (exp.bits[0] & 1) ans *= base;
  475. base *= base;
  476. exp.divto2();
  477. }
  478. if (sign && e.bits[0] & 1) ans.sign = 1;
  479. return ans;
  480. }
  481. //注意,如果本数小于底数返回1...
  482. Bignum log(Bignum &base)
  483. {
  484. if (sign) return 0;
  485. if (length() == 1 && bits[0] == 1) return 0;
  486. if (*this <= base) return 1;
  487. Bignum one("1");
  488. Bignum r("1");
  489. Bignum c("0");
  490. while (r < *this)
  491. {
  492. r *= base;
  493. c += one;
  494. }
  495. if (r != *this) c -= one;
  496. return c;
  497. }
  498. Bignum lg()
  499. {
  500. Bignum ten("10");
  501. return log(ten);
  502. }
  503. Bignum factorial()
  504. {
  505. Bignum r("1");
  506. Bignum zero("0");
  507. Bignum one("1");
  508. Bignum t(*this);
  509. while (t > zero)
  510. {
  511. r *= t;
  512. t -= one;
  513. }
  514. return r;
  515. }
  516. /////////////////////////////////////////////////////////
  517. friend istream& operator >> (istream &is, Bignum &b)
  518. {
  519. string s;
  520. is >> s;
  521. b.mknum(s);
  522. return is;
  523. }
  524. friend ostream& operator << (ostream &os, Bignum b)
  525. {
  526. if (b.sign)os << '-';
  527. for (int i = b.bits.size() - 1; i >= 0; i--) os << b.bits[i];
  528. return os;
  529. }
  530. string to_string()
  531. {
  532. int sz = length();
  533. string s;
  534. if (sign) s.resize(sz + 1);
  535. else s.resize(sz);
  536. int i = 0;
  537. if (sign) s[i++] = '-';
  538. for (int j = sz - 1; i < sz + sign; i++, j--) s[i] = bits[j] + '0';
  539. return s;
  540. }
  541. };
  542. ////////////////////////////
  543. #ifdef BIGNUM_DEBUG
  544. #ifdef __GNUC__
  545. __attribute__((noinline)) //禁止内联
  546. #endif
  547. #ifdef __MINGW32__
  548. __attribute__((noinline))
  549. #endif
  550. char* printB(Bignum &b)
  551. {
  552. //仅仅是用于能在gdb中使用它来输出自己
  553. string s = b.to_string();
  554. char *buf = (char *)malloc(sizeof(char) * s.length());
  555. //这个函数仅用于调试,这里申请的内存不会释放
  556. //因此非调试时不要使用这个函数
  557. strcpy(buf, s.c_str());
  558. return buf; //然后gdb中就可以 print printB(一个Bignum )
  559. }
  560. #endif
  561. int main()
  562. {
  563. Bignum a;
  564. cin >> a;
  565. a = a * a;
  566. cout << a;
  567. return 0;
  568. }

自动取模

  1. template<long long MOD>
  2. class mod_number
  3. {
  4. public:
  5. mod_number() : x(0) {}
  6. mod_number(long long _) { x = (_ % MOD + MOD) % MOD; }
  7. private:
  8. long long x;
  9. mod_number pow(long long n)
  10. {
  11. mod_number a = *this, ans = 1;
  12. while (n)
  13. {
  14. if (n & 1) ans *= a;
  15. n >>= 1;
  16. a *= a;
  17. }
  18. return ans;
  19. }
  20. mod_number inv() { return pow(MOD - 2); }
  21. public:
  22. mod_number operator+(const mod_number &y) { return mod_number(x + y.x); }
  23. mod_number operator-(const mod_number &y) { return mod_number(x - y.x); }
  24. mod_number operator*(const mod_number &y) { return mod_number(x * y.x); }
  25. mod_number operator/(mod_number y) { return mod_number(mod_number(x) * y.inv()); }
  26. mod_number &operator+=(const mod_number &y) { return *this = *this + y; }
  27. mod_number &operator-=(const mod_number &y) { return *this = *this - y; }
  28. mod_number &operator*=(const mod_number &y) { return *this = *this * y; }
  29. mod_number &operator/=(mod_number y) { return *this = *this / y; }
  30. const mod_number operator++(int)
  31. {
  32. mod_number temp(x);
  33. *this += 1;
  34. return temp;
  35. }
  36. const mod_number operator--(int)
  37. {
  38. mod_number temp(x);
  39. *this -= 1;
  40. return temp;
  41. }
  42. mod_number operator++() { return *this += 1; }
  43. mod_number operator--() { return *this -= 1; }
  44. bool operator<(const mod_number &y) { return x < y.x; }
  45. bool operator>(const mod_number &y) { return x > y.x; }
  46. bool operator<=(const mod_number &y) { return x <= y.x; }
  47. bool operator>=(const mod_number &y) { return x >= y.x; }
  48. bool operator==(const mod_number &y) { return x == y.x; }
  49. bool operator!=(const mod_number &y) { return x != y.x; }
  50. mod_number operator[](int) { return inv(); }
  51. friend std::ostream &operator<<(std::ostream &os, const mod_number &y) { return os << y.x; }
  52. friend std::istream &operator>>(std::istream &is, mod_number &y)
  53. {
  54. is >> y.x;
  55. if (!is) y = mod_number();
  56. else y = mod_number(y.x);
  57. return is;
  58. }
  59. };
  60. //声明
  61. const long long IntMaxn = 19260817; //此处为质数
  62. using Int = ModInt<IntMaxn>;
  63. //使用
  64. //for循环请不要用Int做循环变量
  65. Int a, b[10]; //声明数与数组
  66. cin>>a; //输入
  67. cout<<a; //输出
  68. Int x=Int(1); //类型转换
  69. Int(a).pow(b.x); //快速幂,a的b次方
  70. q.inv(); //q的乘法逆元

求N!的最后一位的非0数

  1. const int ff[] = {1, 1, 2, 6, 4, 4, 4, 8, 4, 6};
  2. int fact(int n)
  3. {
  4. int i, x;
  5. if (n < 5) return ff[n];
  6. x = (ff[n % 10] * 6) % 10;
  7. for (i = 1; i <= (n / 5) % 4; i++)
  8. if (x == 6 || x == 2) x = (x + 10) / 2;
  9. else x /= 2;
  10. return (fact(n / 5) * x) % 10;
  11. }

星期问题

基姆拉尔森公式

  1. // 已知1752年9月3日是Sunday,并且日期控制在1700年2月28日后
  2. char name[][15] = {
  3. "monday", "tuesday", "wednesday", "thursday", "friday", "saturday",
  4. "sunday"
  5. };
  6. int main()
  7. {
  8. int d, m, y, a;
  9. printf("Day: ");
  10. scanf("%d", &d);
  11. printf("Month: ");
  12. scanf("%d", &m);
  13. printf("Year: ");
  14. scanf("%d", &y);
  15. // 一二月当做前一年的十三十四月
  16. if (m == 1 || m == 2)
  17. {
  18. m += 12;
  19. y--;
  20. }
  21. // 判断是否在1752年9月3日之前
  22. if ((y < 1752) || (y == 1752 && m < 9) || (y == 1752 && m == 9 && d < 3))
  23. {
  24. // 因为日期控制在1700年2月28日后,所以不用考虑整百年是否是闰年
  25. a = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 + 5) % 7;
  26. }
  27. else
  28. {
  29. // 这里需要考虑整百年是否是闰年
  30. a = (d + 2 * m + 3 * (m + 1) / 5 + y + y / 4 - y / 100 + y / 400) % 7;
  31. }
  32. printf("it's a %s\n", name[a]);
  33. return 0;
  34. }

计算几何

Pick 公式

顶点坐标均是整点的简单多边形:

面积 = 内部格点数 + 边上格点数 / 2 - 1

S = n + s / 2 - 1

(其中n表示多边形内部的点数,s表示多边形边界上的点数,S表示多边形的面积)


已知圆锥表面积S求最大体积V


常用

  1. struct Point
  2. {
  3. double x, y;
  4. Point(double x = 0, double y = 0) : x(x), y(y) {}
  5. Point operator + (Point p) { return Point(x + p.x, y + p.y); }
  6. Point operator - (Point p) { return Point(x - p.x, y - p.y); }
  7. };
  8. typedef Point Vector;
  9. double getDot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; } // 点积
  10. double getCross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; } // 叉积
  11. double getLength(Vector a) { return sqrt(getDot(a, a)); } // 模
  12. // 绕原点逆时针旋转角度B(弧度值)
  13. void transXY(Point &p, double B)
  14. {
  15. double x = p.x, y = p.y;
  16. p.x = x * cos(B) - y * sin(B);
  17. p.y = x * sin(B) + y * cos(B);
  18. }
  19. // 判断三点共线(整数值)
  20. bool isCollinear(const Point &d1, const Point &d2, const Point &d)
  21. {
  22. long long f = 1LL * (d.x - d2.x) * (d1.y - d2.y);
  23. long long g = 1LL * (d.y - d2.y) * (d1.x - d2.x);
  24. return f == g;
  25. }

凸多边形宽度

  1. //平行切线间的最小距离
  2. //多边形的最小的长度
  3. const int MAXN = 115; //点的数量
  4. struct P
  5. {
  6. int x, y;
  7. P() {}
  8. P (int _x, int _y) { x = _x, y = _y; }
  9. P operator - (P b) { return P(x - b.x, y - b.y); }
  10. double len() { return hypot(x, y); }
  11. } a[MAXN];
  12. double cross(P a, P b) { return a.x*b.y - a.y*b.x; }
  13. double dist(P p, P a, P b) { return cross(p - a, b - a) / (b - a).len(); }
  14. double min_len(int n)
  15. {
  16. double ans = 1e100;
  17. for (int i = 1; i <= n; i++)
  18. for (int j = 1; j < i; j++)
  19. {
  20. double l = 1e100, r = -1e100;
  21. for (int k = 1; k <= n; k++)
  22. {
  23. l = min(l, dist(a[k], a[i], a[j]));
  24. r = max(r, dist(a[k], a[i], a[j]));
  25. }
  26. r -= l;
  27. ans = min(ans, r);
  28. }
  29. return ans;
  30. }
  31. int main()
  32. {
  33. int n;
  34. cin >> n;
  35. for (int i = 1; i <= n; i++) cin>>a[i].x>>a[i].y;
  36. printf("%.10f\n", min_len(n));
  37. return 0;
  38. }

凸包,图形,交点,交线,数学,半平面交

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cmath>
  4. #include <vector>
  5. #include <complex>
  6. #include <algorithm>
  7. using namespace std;
  8. typedef pair<int,int> pii;
  9. const double pi = 4 * atan(1);
  10. const double eps = 1e-10;
  11. inline int dcmp (double x) { if (fabs(x) < eps) return 0; else return x < 0 ? -1 : 1; }
  12. inline double getDistance (double x, double y) { return sqrt(x * x + y * y); }
  13. inline double torad(double deg) { return deg / 180 * pi; }
  14. struct Point {
  15. double x, y;
  16. Point (double x = 0, double y = 0): x(x), y(y) {}
  17. void read () { scanf("%lf%lf", &x, &y); }
  18. void write () { printf("%f %f", x, y); }
  19. bool operator == (const Point& u) const { return dcmp(x - u.x) == 0 && dcmp(y - u.y) == 0; }
  20. bool operator != (const Point& u) const { return !(*this == u); }
  21. bool operator < (const Point& u) const { return dcmp(x - u.x) < 0 || (dcmp(x-u.x)==0 && dcmp(y-u.y) < 0); }
  22. bool operator > (const Point& u) const { return u < *this; }
  23. bool operator <= (const Point& u) const { return *this < u || *this == u; }
  24. bool operator >= (const Point& u) const { return *this > u || *this == u; }
  25. Point operator + (const Point& u) { return Point(x + u.x, y + u.y); }
  26. Point operator - (const Point& u) { return Point(x - u.x, y - u.y); }
  27. Point operator * (const double u) { return Point(x * u, y * u); }
  28. Point operator / (const double u) { return Point(x / u, y / u); }
  29. double operator ^ (const Point& u) { return x*u.y - y*u.x; }
  30. };
  31. typedef Point Vector;
  32. typedef vector<Point> Polygon;
  33. struct Line {
  34. double a, b, c;
  35. Line (double a = 0, double b = 0, double c = 0): a(a), b(b), c(c) {}
  36. };
  37. struct DirLine {
  38. Point p;
  39. Vector v;
  40. double ang;
  41. DirLine () {}
  42. DirLine (Point p, Vector v): p(p), v(v) { ang = atan2(v.y, v.x); }
  43. bool operator < (const DirLine& u) const { return ang < u.ang; }
  44. };
  45. struct Circle {
  46. Point o;
  47. double r;
  48. Circle () {}
  49. Circle (Point o, double r = 0): o(o), r(r) {}
  50. void read () { o.read(), scanf("%lf", &r); }
  51. Point point(double rad) { return Point(o.x + cos(rad)*r, o.y + sin(rad)*r); }
  52. double getArea (double rad) { return rad * r * r / 2; }
  53. };
  54. namespace Punctual {
  55. double getDistance (Point a, Point b) { double x=a.x-b.x, y=a.y-b.y; return sqrt(x*x + y*y); }
  56. };
  57. namespace Vectorial {
  58. /* 点积: 两向量长度的乘积再乘上它们夹角的余弦, 夹角大于90度时点积为负 */
  59. double getDot (Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
  60. /* 叉积: 叉积等于两向量组成的三角形有向面积的两倍, cross(v, w) = -cross(w, v) */
  61. double getCross (Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
  62. double getLength (Vector a) { return sqrt(getDot(a, a)); }
  63. double getPLength (Vector a) { return getDot(a, a); }
  64. double getAngle (Vector u) { return atan2(u.y, u.x); }
  65. double getAngle (Vector a, Vector b) { return acos(getDot(a, b) / getLength(a) / getLength(b)); }
  66. Vector rotate (Vector a, double rad) { return Vector(a.x*cos(rad)-a.y*sin(rad), a.x*sin(rad)+a.y*cos(rad)); }
  67. /* 单位法线 */
  68. Vector getNormal (Vector a) { double l = getLength(a); return Vector(-a.y/l, a.x/l); }
  69. };
  70. namespace ComplexVector {
  71. typedef complex<double> Point;
  72. typedef Point Vector;
  73. double getDot(Vector a, Vector b) { return real(conj(a)*b); }
  74. double getCross(Vector a, Vector b) { return imag(conj(a)*b); }
  75. Vector rotate(Vector a, double rad) { return a*exp(Point(0, rad)); }
  76. };
  77. namespace Linear {
  78. using namespace Vectorial;
  79. Line getLine (double x1, double y1, double x2, double y2) { return Line(y2-y1, x1-x2, y1*x2-x1*y2); }
  80. Line getLine (double a, double b, Point u) { return Line(a, -b, u.y * b - u.x * a); }
  81. bool getIntersection (Line p, Line q, Point& o) {
  82. if (fabs(p.a * q.b - q.a * p.b) < eps)
  83. return false;
  84. o.x = (q.c * p.b - p.c * q.b) / (p.a * q.b - q.a * p.b);
  85. o.y = (q.c * p.a - p.c * q.a) / (p.b * q.a - q.b * p.a);
  86. return true;
  87. }
  88. /* 直线pv和直线qw的交点 */
  89. bool getIntersection (Point p, Vector v, Point q, Vector w, Point& o) {
  90. if (dcmp(getCross(v, w)) == 0) return false;
  91. Vector u = p - q;
  92. double k = getCross(w, u) / getCross(v, w);
  93. o = p + v * k;
  94. return true;
  95. }
  96. /* 点p到直线ab的距离 */
  97. double getDistanceToLine (Point p, Point a, Point b) { return fabs(getCross(b-a, p-a) / getLength(b-a)); }
  98. double getDistanceToSegment (Point p, Point a, Point b) {
  99. if (a == b) return getLength(p-a);
  100. Vector v1 = b - a, v2 = p - a, v3 = p - b;
  101. if (dcmp(getDot(v1, v2)) < 0) return getLength(v2);
  102. else if (dcmp(getDot(v1, v3)) > 0) return getLength(v3);
  103. else return fabs(getCross(v1, v2) / getLength(v1));
  104. }
  105. /* 点p在直线ab上的投影 */
  106. Point getPointToLine (Point p, Point a, Point b) { Vector v = b-a; return a+v*(getDot(v, p-a) / getDot(v,v)); }
  107. /* 判断线段是否存在交点 */
  108. bool haveIntersection (Point a1, Point a2, Point b1, Point b2) {
  109. double c1=getCross(a2-a1, b1-a1), c2=getCross(a2-a1, b2-a1), c3=getCross(b2-b1, a1-b1), c4=getCross(b2-b1,a2-b1);
  110. return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
  111. }
  112. /* 判断点是否在线段上 */
  113. bool onSegment (Point p, Point a, Point b) { return dcmp(getCross(a-p, b-p)) == 0 && dcmp(getDot(a-p, b-p)) < 0; }
  114. bool onLine (Point p, Point a, Point b) { return dcmp(getCross(a-p, b-p)) == 0}
  115. bool onLeft(DirLine l, Point p) { return dcmp(l.v ^ (p-l.p)) >= 0; }
  116. }
  117. namespace Triangular {
  118. using namespace Vectorial;
  119. double getAngle (double a, double b, double c) { return acos((a*a+b*b-c*c) / (2*a*b)); }
  120. double getArea (double a, double b, double c) { double s =(a+b+c)/2; return sqrt(s*(s-a)*(s-b)*(s-c)); }
  121. double getArea (double a, double h) { return a * h / 2; }
  122. double getArea (Point a, Point b, Point c) { return fabs(getCross(b - a, c - a)) / 2; }
  123. double getDirArea (Point a, Point b, Point c) { return getCross(b - a, c - a) / 2; }
  124. };
  125. namespace Polygonal {
  126. using namespace Vectorial;
  127. using namespace Linear;
  128. double getArea (Point* p, int n) {
  129. double ret = 0;
  130. for (int i = 0; i < n-1; i++)
  131. ret += (p[i]-p[0]) ^ (p[i+1]-p[0]);
  132. return ret/2;
  133. }
  134. /* 凸包 */
  135. int getConvexHull (Point* p, int n, Point* ch) {
  136. sort(p, p + n);
  137. int m = 0;
  138. for (int i = 0; i < n; i++) {
  139. /* 可共线 */
  140. //while (m > 1 && dcmp(getCross(ch[m-1]-ch[m-2], p[i]-ch[m-1])) < 0) m--;
  141. while (m > 1 && dcmp(getCross(ch[m-1]-ch[m-2], p[i]-ch[m-1])) <= 0) m--;
  142. ch[m++] = p[i];
  143. }
  144. int k = m;
  145. for (int i = n-2; i >= 0; i--) {
  146. /* 可共线 */
  147. //while (m > k && dcmp(getCross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) < 0) m--;
  148. while (m > k && dcmp(getCross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) m--;
  149. ch[m++] = p[i];
  150. }
  151. if (n > 1) m--;
  152. return m;
  153. }
  154. int isPointInPolygon (Point o, Point* p, int n) {
  155. int wn = 0;
  156. for (int i = 0; i < n; i++) {
  157. int j = (i + 1) % n;
  158. if (onSegment(o, p[i], p[j]) || o == p[i]) return 0; // 边界上
  159. int k = dcmp(getCross(p[j] - p[i], o-p[i]));
  160. int d1 = dcmp(p[i].y - o.y);
  161. int d2 = dcmp(p[j].y - o.y);
  162. if (k > 0 && d1 <= 0 && d2 > 0) wn++;
  163. if (k < 0 && d2 <= 0 && d1 > 0) wn--;
  164. }
  165. return wn ? -1 : 1;
  166. }
  167. /* 旋转卡壳 */
  168. void rotatingCalipers(Point *p, int n, vector<pii>& sol) {
  169. sol.clear();
  170. int j = 1; p[n] = p[0];
  171. for (int i = 0; i < n; i++) {
  172. while (getCross(p[j+1]-p[i+1], p[i]-p[i+1]) > getCross(p[j]-p[i+1], p[i]-p[i+1]))
  173. j = (j+1) % n;
  174. sol.push_back(make_pair(i, j));
  175. sol.push_back(make_pair(i + 1, j + 1));
  176. }
  177. }
  178. void rotatingCalipersGetRectangle (Point *p, int n, double& area, double& perimeter) {
  179. p[n] = p[0];
  180. int l = 1, r = 1, j = 1;
  181. area = perimeter = 1e20;
  182. for (int i = 0; i < n; i++) {
  183. Vector v = (p[i+1]-p[i]) / getLength(p[i+1]-p[i]);
  184. while (dcmp(getDot(v, p[r%n]-p[i]) - getDot(v, p[(r+1)%n]-p[i])) < 0) r++;
  185. while (j < r || dcmp(getCross(v, p[j%n]-p[i]) - getCross(v,p[(j+1)%n]-p[i])) < 0) j++;
  186. while (l < j || dcmp(getDot(v, p[l%n]-p[i]) - getDot(v, p[(l+1)%n]-p[i])) > 0) l++;
  187. double w = getDot(v, p[r%n]-p[i])-getDot(v, p[l%n]-p[i]);
  188. double h = getDistanceToLine (p[j%n], p[i], p[i+1]);
  189. area = min(area, w * h);
  190. perimeter = min(perimeter, 2 * w + 2 * h);
  191. }
  192. }
  193. /* 计算半平面相交可以用增量法,o(n^2),初始设置4条无穷大的半平面 */
  194. /* 用有向直线A->B切割多边形u,返回左侧。可能退化成单点或线段 */
  195. Polygon cutPolygon (Polygon u, Point a, Point b) {
  196. Polygon ret;
  197. int n = u.size();
  198. for (int i = 0; i < n; i++) {
  199. Point c = u[i], d = u[(i+1)%n];
  200. if (dcmp((b-a)^(c-a)) >= 0) ret.push_back(c);
  201. if (dcmp((b-a)^(c-d)) != 0) {
  202. Point t;
  203. getIntersection(a, b-a, c, d-c, t);
  204. if (onSegment(t, c, d))
  205. ret.push_back(t);
  206. }
  207. }
  208. return ret;
  209. }
  210. /* 半平面相交 */
  211. int halfPlaneIntersection(DirLine* li, int n, Point* poly) {
  212. sort(li, li + n);
  213. int first, last;
  214. Point* p = new Point[n];
  215. DirLine* q = new DirLine[n];
  216. q[first=last=0] = li[0];
  217. for (int i = 1; i < n; i++) {
  218. while (first < last && !onLeft(li[i], p[last-1])) last--;
  219. while (first < last && !onLeft(li[i], p[first])) first++;
  220. q[++last] = li[i];
  221. if (dcmp(q[last].v ^ q[last-1].v) == 0) {
  222. last--;
  223. if (onLeft(q[last], li[i].p)) q[last] = li[i];
  224. }
  225. if (first < last)
  226. getIntersection(q[last-1].p, q[last-1].v, q[last].p, q[last].v, p[last-1]);
  227. }
  228. while (first < last && !onLeft(q[first], p[last-1])) last--;
  229. if (last - first <= 1) { delete [] p; delete [] q; return 0; }
  230. getIntersection(q[last].p, q[last].v, q[first].p, q[first].v, p[last]);
  231. int m = 0;
  232. for (int i = first; i <= last; i++) poly[m++] = p[i];
  233. delete [] p; delete [] q;
  234. return m;
  235. }
  236. /* 去除多边形共线点 */
  237. Polygon simplify (const Polygon& poly) {
  238. Polygon ret;
  239. int n = poly.size();
  240. for (int i = 0; i < n; i++) {
  241. Point a = poly[i];
  242. Point b = poly[(i+1)%n];
  243. Point c = poly[(i+2)%n];
  244. if (dcmp((b-a)^(c-b)) != 0 && (ret.size() == 0 || b != ret[ret.size()-1]))
  245. ret.push_back(b);
  246. }
  247. return ret;
  248. }
  249. };
  250. namespace Circular {
  251. using namespace Linear;
  252. using namespace Vectorial;
  253. using namespace Triangular;
  254. /* 直线和圆的交点 */
  255. int getLineCircleIntersection (Point p, Point q, Circle O, double& t1, double& t2, vector<Point>& sol) {
  256. Vector v = q - p;
  257. /* 使用前需清空sol */
  258. //sol.clear();
  259. double a = v.x, b = p.x - O.o.x, c = v.y, d = p.y - O.o.y;
  260. double e = a*a+c*c, f = 2*(a*b+c*d), g = b*b+d*d-O.r*O.r;
  261. double delta = f*f - 4*e*g;
  262. if (dcmp(delta) < 0) return 0;
  263. if (dcmp(delta) == 0) {
  264. t1 = t2 = -f / (2 * e);
  265. sol.push_back(p + v * t1);
  266. return 1;
  267. }
  268. t1 = (-f - sqrt(delta)) / (2 * e); sol.push_back(p + v * t1);
  269. t2 = (-f + sqrt(delta)) / (2 * e); sol.push_back(p + v * t2);
  270. return 2;
  271. }
  272. /* 圆和圆的交点 */
  273. int getCircleCircleIntersection (Circle o1, Circle o2, vector<Point>& sol) {
  274. double d = getLength(o1.o - o2.o);
  275. if (dcmp(d) == 0) {
  276. if (dcmp(o1.r - o2.r) == 0) return -1;
  277. return 0;
  278. }
  279. if (dcmp(o1.r + o2.r - d) < 0) return 0;
  280. if (dcmp(fabs(o1.r-o2.r) - d) > 0) return 0;
  281. double a = getAngle(o2.o - o1.o);
  282. double da = acos((o1.r*o1.r + d*d - o2.r*o2.r) / (2*o1.r*d));
  283. Point p1 = o1.point(a-da), p2 = o1.point(a+da);
  284. sol.push_back(p1);
  285. if (p1 == p2) return 1;
  286. sol.push_back(p2);
  287. return 2;
  288. }
  289. /* 过定点作圆的切线 */
  290. int getTangents (Point p, Circle o, Vector* v) {
  291. Vector u = o.o - p;
  292. double d = getLength(u);
  293. if (d < o.r) return 0;
  294. else if (dcmp(d - o.r) == 0) {
  295. v[0] = rotate(u, pi / 2);
  296. return 1;
  297. } else {
  298. double ang = asin(o.r / d);
  299. v[0] = rotate(u, -ang);
  300. v[1] = rotate(u, ang);
  301. return 2;
  302. }
  303. }
  304. /* a[i] 和 b[i] 分别是第i条切线在O1和O2上的切点 */
  305. /* have some problems */
  306. int getTangents (Circle o1, Circle o2, Point* a, Point* b) {
  307. int cnt = 0;
  308. if (o1.r < o2.r) { swap(o1, o2); swap(a, b); }
  309. double d2 = getLength(o1.o - o2.o); d2 = d2 * d2;
  310. double rdif = o1.r - o2.r, rsum = o1.r + o2.r;
  311. if (d2 < rdif * rdif) return 0;
  312. if (dcmp(d2) == 0 && dcmp(o1.r - o2.r) == 0) return -1;
  313. double base = getAngle(o2.o - o1.o);
  314. if (dcmp(d2 - rdif * rdif) == 0) {
  315. a[cnt] = o1.point(base); b[cnt] = o2.point(base); cnt++;
  316. return cnt;
  317. }
  318. double ang = acos( rdif / sqrt(d2) );
  319. a[cnt] = o1.point(base+ang); b[cnt] = o2.point(base+ang); cnt++;
  320. a[cnt] = o1.point(base-ang); b[cnt] = o2.point(base-ang); cnt++;
  321. if (dcmp(d2 - rsum * rsum) == 0) {
  322. a[cnt] = o1.point(base); b[cnt] = o2.point(base); cnt++;
  323. } else if (d2 > rsum * rsum) {
  324. double ang = acos( rsum / sqrt(d2) );
  325. a[cnt] = o1.point(base+ang); b[cnt] = o2.point(pi+base+ang); cnt++;
  326. a[cnt] = o1.point(base-ang); b[cnt] = o2.point(pi+base-ang); cnt++;
  327. }
  328. return cnt;
  329. }
  330. /* 三点确定外切圆 */
  331. Circle CircumscribedCircle(Point p1, Point p2, Point p3) {
  332. double Bx = p2.x - p1.x, By = p2.y - p1.y;
  333. double Cx = p3.x - p1.x, Cy = p3.y - p1.y;
  334. double D = 2 * (Bx * Cy - By * Cx);
  335. double cx = (Cy * (Bx * Bx + By * By) - By * (Cx * Cx + Cy * Cy)) / D + p1.x;
  336. double cy = (Bx * (Cx * Cx + Cy * Cy) - Cx * (Bx * Bx + By * By)) / D + p1.y;
  337. Point p = Point(cx, cy);
  338. return Circle(p, getLength(p1 - p));
  339. }
  340. /* 三点确定内切圆 */
  341. Circle InscribedCircle(Point p1, Point p2, Point p3) {
  342. double a = getLength(p2 - p3);
  343. double b = getLength(p3 - p1);
  344. double c = getLength(p1 - p2);
  345. Point p = (p1 * a + p2 * b + p3 * c) / (a + b + c);
  346. return Circle(p, getDistanceToLine(p, p1, p2));
  347. }
  348. /* 三角形一顶点为圆心 */
  349. double getPublicAreaToTriangle (Circle O, Point a, Point b) {
  350. if (dcmp((a-O.o)^(b-O.o)) == 0) return 0;
  351. int sig = 1;
  352. double da = getPLength(O.o-a), db = getPLength(O.o-b);
  353. if (dcmp(da-db) > 0) {
  354. swap(da, db);
  355. swap(a, b);
  356. sig = -1;
  357. }
  358. double t1, t2;
  359. vector<Point> sol;
  360. int n = getLineCircleIntersection(a, b, O, t1, t2, sol);
  361. if (dcmp(da-O.r*O.r) <= 0) {
  362. if (dcmp(db-O.r*O.r) <= 0) return getDirArea(O.o, a, b) * sig;
  363. int k = 0;
  364. if (getPLength(sol[0]-b) > getPLength(sol[1]-b)) k = 1;
  365. double ret = getArea(O.o, a, sol[k]) + O.getArea(getAngle(sol[k]-O.o, b-O.o));
  366. double tmp = (a-O.o)^(b-O.o);
  367. return ret * sig * dcmp(tmp);
  368. }
  369. double d = getDistanceToSegment(O.o, a, b);
  370. if (dcmp(d-O.r) >= 0) {
  371. double ret = O.getArea(getAngle(a-O.o, b-O.o));
  372. double tmp = (a-O.o)^(b-O.o);
  373. return ret * sig * dcmp(tmp);
  374. }
  375. double k1 = O.r / getLength(a - O.o), k2 = O.r / getLength(b - O.o);
  376. Point p = O.o + (a - O.o) * k1, q = O.o + (b - O.o) * k2;
  377. double ret1 = O.getArea(getAngle(p-O.o, q-O.o));
  378. double ret2 = O.getArea(getAngle(sol[0]-O.o, sol[1]-O.o)) - getArea(O.o, sol[0], sol[1]);
  379. double ret = (ret1 - ret2), tmp = (a-O.o)^(b-O.o);
  380. return ret * sig * dcmp(tmp);
  381. }
  382. double getPublicAreaToPolygon (Circle O, Point* p, int n) {
  383. if (dcmp(O.r) == 0) return 0;
  384. double area = 0;
  385. for (int i = 0; i < n; i++) {
  386. int u = (i + 1) % n;
  387. area += getPublicAreaToTriangle(O, p[i], p[u]);
  388. }
  389. return fabs(area);
  390. }
  391. };
  392. using namespace Polygonal;
  393. const int maxn = 105;
  394. int N, M;
  395. double X[maxn], Y[maxn], PX[maxn], PY[maxn];
  396. void init () {
  397. double x, y;
  398. scanf("%d%d", &N, &M);
  399. for (int i = 1; i <= N; i++) {
  400. X[i] = Y[i] = PX[i] = PY[i] = 0;
  401. for (int j = 1; j <= M; j++) {
  402. scanf("%lf%lf", &x, &y);
  403. X[i] += x, Y[i] += y;
  404. PX[i] += x*x, PY[i] += y*y;
  405. }
  406. }
  407. }

二进制

状态压缩

最低位是第0位 操作
取第k位(非0则为1) (n >> k) & 1
取后k位(同上,0~k-1位) n & ((1 << k) – 1)
第k位取反 n ^= (1 << k)
第k位变为1 n |= (1 << k)
第k位变为0 n &= (~(1 << k))

lowbit函数

  1. //lowbit(x)是x的二进制表达式中最低位的1所对应的值
  2. //6的二进制是110,所以lowbit(6)的二进制为10,即lowbit(6)=2
  3. int lowbit(int x) { return x & (-x); }
  4. int lowbit(int x) { return x & (x ^ (x - 1)); }

动态规划 DP

  1. //二维
  2. for i= 1 to N
  3. for v=Ci to V
  4. F[i,v]=max{F[i1,v],F[i1,vCi]+Wi}
  5. //一维
  6. for i=1 to N
  7. for j= V to Ci
  8. F[j]=max{F[j],F[jCi]+Wi}
  1. for k=1 to K
  2. for v = V to 0
  3. for item i in group k
  4. f[v]=max{F[v],F[vCi]+Wi}
  1. F[i][j]=min{F[i][k]+F[k+1][j]}+Sum[i][j]
  2. for(int i=1;i<n;i++)//枚举区间长度
  3. for(int j=1;j+i<=n;j++)//枚举区间左端点
  4. for(int k=j;k<j+i;k++)//枚举中间值k
  5. DP[j][j+i]=max(DP[j][k]+DP[k+1][j+i]+Sum[i][j])

枚举中间值时枚举一个新数组,更新时更新该数组为新的中间值

  1. for (long long i=1; i<n; i++)
  2. for (long long j=2*n-i; j>0; j--)
  3. for (long long k=s[j][j+i-1]; k<=s[j+1][j+i]; k++)
  4. if (dp[j][k]+dp[k+1][j+i]+sum[j+i]-sum[j-1] <= dp[j][j+i])
  5. {
  6. dp[j][j+i]=dp[j][k]+dp[k+1][j+i]+sum[j+i]-sum[j-1];
  7. s[j][j+i]=k;
  8. }

二分

  1. //求在满足条件下最大或最小的值的题目,满足单调性和有序性
  2. //整数while(l<r),小数一般for500次,具体次数具体分析
  3. //时间复杂度 O(logn),最后得到的是可行域的闭区间[l,r]
  4. while (r>l)
  5. {
  6. mid=(l+r+1)/2; //注意是l+r+1
  7. if(check(mid)==true) l=mid;
  8. else r=mid-1;
  9. }

三分

  1. // 用于单峰函数求极值
  2. // 整数用while(l<=r),浮点数用for
  3. // 每次选择区间内的两个点,算完一次后去掉距离标准答案的值更远的那个点到原区间的端点的区间
  4. int f(int x)
  5. {
  6. // 求值
  7. int ans;
  8. // 适用于上凸型函数
  9. return ans;
  10. // 下凸型函数可以用INF减去f(x)
  11. // return INF - ans;
  12. }
  13. int threeDivideInt(int L, int R)
  14. {
  15. while (L < R - 1)
  16. {
  17. auto mid = (L + R) / 2;
  18. auto mmid = (mid + R) / 2;
  19. if (f(mid) > f(mmid)) R = mmid;
  20. else L = mid;
  21. }
  22. // 返回x
  23. return f(L) > f(R) ? L : R;
  24. // 上凸型返回f(x)
  25. // return f(f(L) > f(R) ? L : R);
  26. // 下凸型返回f(x)
  27. // return INF - f(f(L) > f(R) ? L : R);
  28. }
  29. double threeDivideDouble(double low, double up)
  30. {
  31. double m1, m2;
  32. while (up - low >= eps)
  33. {
  34. m1 = low + (up - low) / 3;
  35. m2 = up - (up - low) / 3;
  36. if (f(m1) <= f(m2)) low = m1;
  37. else up = m2;
  38. }
  39. return (m1 + m2) / 2;
  40. }

数据结构

并查集

  1. //均摊O(1)的查找、合并
  2. const int MAXN = 100000 + 50;
  3. // 1下标
  4. class union_set
  5. {
  6. private:
  7. int par[MAXN];
  8. //递归查询,可能会爆栈
  9. int find_res(int x) { return x == par[x] ? x : par[x] = find_res(par[x]); }
  10. //非递归查询
  11. int find(int x)
  12. {
  13. int root = x;
  14. while (root != par[root]) root = par[root];
  15. while (x != root)
  16. {
  17. int temp = par[x];
  18. par[x] = root;
  19. x = temp;
  20. }
  21. return root;
  22. }
  23. public:
  24. union_set() { for (int i = 1; i < MAXN; i++) par[i] = i; }
  25. //连接,par[a]=b,a的祖先指向b的祖先,b的祖先为共同的root
  26. void link(int x, int y) { par[find(x)] = find(y); }
  27. bool connected(int x, int y) { return find(x) == find(y); }
  28. };
  29. // 0下标
  30. class union_set
  31. {
  32. private:
  33. vector<int> par;
  34. int find_res(int x) { return x == par[x] ? x : par[x] = find_res(par[x]); }
  35. int find(int x)
  36. {
  37. int root = x;
  38. while (root != par[root]) root = par[root];
  39. while (x != root)
  40. {
  41. int temp = par[x];
  42. par[x] = root;
  43. x = temp;
  44. }
  45. return root;
  46. }
  47. public:
  48. union_set(const int size)
  49. {
  50. par = vector<int>(size);
  51. for (auto i = 0; i < size; i++) par[i] = i;
  52. }
  53. void link(int x, int y) { par[find(x)] = find(y); }
  54. bool connected(int x, int y) { return find(x) == find(y); }
  55. };

单调栈

  1. //用途:O(n),找到从左/右遍历第一个比它小/大的元素的位置
  2. //一个元素向左遍历的第一个比它小的数的位置就是将它插入单调栈时栈顶元素的值,若栈为空,则说明不存在这么一个数。然后将此元素的下标存入栈,就能类似迭代般地求解后面的元素
  3. //对于a[i],l[i]表示 第i个数向左遍历的第一个比它小的元素的位置,0表示无
  4. int a[10], l[10], n;
  5. stack <int> S;
  6. for (int i = 1; i <= n; i++)
  7. {
  8. while (S.size() && a[S.top()] >= a[i]) S.pop();
  9. if (S.empty()) l[i] = 0;
  10. else l[i] = S.top();
  11. S.push(i);
  12. }

区间最值查询 RMQ

  1. //用于离线区间查询最大值和最小值
  2. //ST表实现
  3. const static int MAXN = 50000 + 100;
  4. const static int LOGMAXN = (int)(log2(MAXN)) + 5;
  5. int n;
  6. int d[MAXN] = { 0 };
  7. int dlog[MAXN] = { 0 }; //log表
  8. int dmax[MAXN][LOGMAXN] = { 0 };
  9. int dmin[MAXN][LOGMAXN] = { 0 };
  10. //预处理,O(nlogn)
  11. void init()
  12. {
  13. for (int i = 1; i <= n; i++)
  14. {
  15. dmin[i][0] = d[i];
  16. dmax[i][0] = d[i];
  17. }
  18. for (int j = 1; (1 << j) <= n; j++)
  19. for (int i = 1; i + (1 << j) - 1 <= n; i++)
  20. {
  21. dmin[i][j] = min(dmin[i][j - 1], dmin[i + (1 << (j - 1))][j - 1]);
  22. dmax[i][j] = max(dmax[i][j - 1], dmax[i + (1 << (j - 1))][j - 1]);
  23. }
  24. for (int i = 2; i <= MAXN - 100; i++) dlog[i] = dlog[i >> 1] + 1;
  25. }
  26. // 数组0下标!!!
  27. // 注意题目是否是0下标,否则查询的时候应减一后传入函数
  28. const static int MAXN = 50000 + 100;
  29. int nums[MAXN] = { 0 };
  30. struct TStTable
  31. {
  32. const static int LOGMAXN = (int)(log2(MAXN)) + 5;
  33. int stmin[MAXN][LOGMAXN] = { 0 };
  34. int stmax[MAXN][LOGMAXN] = { 0 };
  35. int XLog[LOGMAXN] = { 0 }; //log表
  36. TStTable()
  37. {
  38. XLog[1] = 0;
  39. for (int i = 2; i < LOGMAXN; i++) XLog[i] = XLog[i >> 1] + 1;
  40. }
  41. //预处理,O(nlogn),传入数组和数字数量
  42. void InitSt(int *nums, int n)
  43. {
  44. for (int i = 0; i < n; i++)
  45. {
  46. stmin[i][0] = nums[i];
  47. stmax[i][0] = nums[i];
  48. }
  49. for (int j = 1; (1 << j) <= n; j++)
  50. {
  51. for (int i = 0; i + (1 << j) - 1 < n; i++)
  52. {
  53. stmin[i][j] = min(stmin[i][j - 1], stmin[i + (1 << (j - 1))][j - 1]);
  54. stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]);
  55. }
  56. }
  57. }
  58. //查询最大值,O(1),常数较小
  59. int getmax(int L, int R)
  60. {
  61. int x = XLog[R - L + 1];
  62. return max(stmax[L][x], stmax[R - (1 << x) + 1][x]);
  63. }
  64. //查询最小值,O(1),常数较小
  65. int getmin(int L, int R)
  66. {
  67. int x = XLog[R - L + 1];
  68. return min(stmin[L][x], stmin[R - (1 << x) + 1][x]);
  69. }
  70. //查询最大最小值之差,O(1),常数较小
  71. int getdelta(int L, int R)
  72. {
  73. int x = XLog[R