Scarlett‘s boy的板子 ```c++ #include "bits/stdc++.h" #define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr) #pragma GCC optimize(3) typedef long long ll; typedef unsigned long long ull; using namespace std; const int MOD[2] = {1000000007, 998244353}; inline ll powmod(ll a, ll b, ll Mod) { ll res = 1; a = (a % Mod + Mod) % Mod; while (b) { if (b & 1) res = 1ll * res * a % Mod; b >>= 1; a = 1ll * a * a % Mod; } return res; } #define debug(x...)\ do {\ cout << #x << " -> ";\ err(x);\ } while (0) void err() { cout << endl; } template<class T, class... Ts> void err(const T &arg, const Ts &... args) { cout << arg << ' '; err(args...); } void init(); const int inf = 0x3f3f3f3f; const int mod = MOD[1]; const int N = 3e5 + 10; void solve() { int n; cin >> n; vector<int> A(n); for (int i = 0; i < n; i++) cin >> A[i]; } signed main() { init(); IOS; int _ = 1; cin >> _; while (_--) solve(); return 0; } void init() { } /* */ ``` ## 一、杂乱的总结 ### 1.快速幂 说明：快速幂用于求a的b次模p的结果，但是局限于求单个底数的情况，求多个不同的a的b次可以尝试一下预处理。 ```c++ long long powmod(long long a,long long b,long long p){ long long re=1; while (b>0){ if(b%2==1) re=re*a%p; b/=2; a=a*a%p; } return re; } ``` ### 2.素数筛 说明：素数筛可以找到第几个素数是多少，同时可以询问一个数是否为素数。 ```c++ int pri[1000010]; int vis[1000010]; int cnt = 0; void init() { for (int i = 2; i <= 1000000; i++) { if (vis[i] == 0) pri[++cnt] = i; for (int j = 1; j <= cnt && i * pri[j] <= 1000000; j++) { vis[i * pri[j]] = 1; if (i % pri[j] == 0) break; } } } ``` ```c++ int v[1000010]; int prime[1000010]; int cnt=0; for (int i=2;i<=n;i++){ if(v[i]==0){ v[i]=i; prime[++cnt]=i; } for (int j=1;j<=cnt;j++){ if(prime[j]>v[i] || i*prime[j]>n) break; v[i*prime[j]] = prime[j]; } } ``` ### 3.前缀和（一阶，二阶） 一阶可以直接一边循环得到，对于二阶的前缀和，可以用f（i，j）=f（i-1，j）+f（i，j-1）-f（i-1，j-1）得到。 ### 4.贪心小技巧 1. 采用考虑局部的情况去贪心，仅考虑两个数之间的关系，再证明两个数之间的关系即为全部之间的关系，即可自定义comp来排序完成贪心。 2. 可以尝试寻找与二进制之间的关系。 ### 5.快读 ```c++ inline void read(int &x) { x = 0;int f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if (ch == '-')f = -1 ; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x<<1) + (x<<3) + (ch^48); ch = getchar(); } x*=f; } inline void read(ll &x) { x = 0;int f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if (ch == '-')f = -1 ; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = (x<<1) + (x<<3) + (ch^48); ch = getchar(); } x*=f; } ``` ### 6.快速乘（龟速乘） ```c++ ll powand(ll a,ll b,ll p) // a*b mod p { ll re=0; while(b) { if(b&1) re=(re+a)%p; a=(a<<1)%p; b>>=1; } return re; } ``` ### 7.__int128 ```c++ inline void print(__int128 x) { if(x<0){ putchar('-'); x=-x; } if(x>9) print(x/10); putchar(x%10+'0'); } inline void scan(__int128 &x)//输入 { x=0;int f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=x*10+ch-48;ch=getchar();} x*=f; } ``` ### 8.并查集 ```c++ struct DSU { vector<int> fa, siz; DSU(int M) : fa(M + 1), siz(M + 1, 1) { for (int i = 0; i <= M; i++) fa[i] = i; } inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } inline bool equal(int x, int y) { return find(x) == find(y); } inline void merge(int x, int y) { int fx = find(x), fy = find(y); if (fx != fy) { if (siz[fx] > siz[fy]) swap(fx, fy); fa[fx] = fy; siz[fy] += siz[fx]; siz[fx] = 0; } } }; ``` ### 9.快读 ```c++ char nc() { static char buf[1000000], *p = buf, *q = buf; return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q) ? EOF : *p++; } inline int read() { int x = 0,f = 1; char ch = nc(); while (!isdigit(ch)) { if (ch == '-')f = -1; ch = nc(); } while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = nc(); } return x * f; } ``` ```c++ namespace Fast_IO{ ///orz laofu const int MAXL((1 << 18) + 1);int iof, iotp; char ioif[MAXL], *ioiS, *ioiT, ioof[MAXL],*iooS=ioof,*iooT=ioof+MAXL-1,ioc,iost[55]; char Getchar(){ if (ioiS == ioiT){ ioiS=ioif;ioiT=ioiS+fread(ioif,1,MAXL,stdin);return (ioiS == ioiT ? EOF : *ioiS++); }else return (*ioiS++); } void Write(){fwrite(ioof,1,iooS-ioof,stdout);iooS=ioof;} void Putchar(char x){*iooS++ = x;if (iooS == iooT)Write();} inline int read(){ int x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar(); if(ioc==EOF)exit(0); for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof; } inline long long read_ll(){ long long x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar(); if(ioc==EOF)exit(0); for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof; } /** #define lll __int128 inline lll read_lll(){ lll x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar(); if(ioc==EOF)exit(0); for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof; }*/ template <class Int>void Print(Int x, char ch = '\0'){ if(!x)Putchar('0');if(x<0)Putchar('-'),x=-x;while(x)iost[++iotp]=x%10+'0',x/=10; while(iotp)Putchar(iost[iotp--]);if (ch)Putchar(ch); } void Getstr(char *s, int &l){ for(ioc=Getchar();ioc==' '||ioc=='\n'||ioc=='\t';)ioc=Getchar(); if(ioc==EOF)exit(0); for(l=0;!(ioc==' '||ioc=='\n'||ioc=='\t'||ioc==EOF);ioc=Getchar())s[l++]=ioc;s[l] = 0; } void Putstr(const char *s){for(int i=0,n=strlen(s);i<n;++i)Putchar(s[i]);} } // namespace Fast_IO using namespace Fast_IO; ``` ### 10.大数 ```c++ string build(ll x){ string ans=""; if(x==0){ ans="0";return ans; } while(x){ char c='0'+(x%10); x/=10; ans=c+ans; } return ans; } string add(string a,string b)//只限两个非负整数相加 { string ans; int na[L]={0},nb[L]={0}; int la=a.size(),lb=b.size(); for(int i=0;i<la;i++) na[la-1-i]=a[i]-'0'; for(int i=0;i<lb;i++) nb[lb-1-i]=b[i]-'0'; int lmax=la>lb?la:lb; for(int i=0;i<lmax;i++) na[i]+=nb[i],na[i+1]+=na[i]/10,na[i]%=10; if(na[lmax]) lmax++; for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0'; return ans; } string mul(string a,string b)//高精度乘法a,b,均为非负整数 { string s; int na[L],nb[L],nc[L],La=a.size(),Lb=b.size();//na存储被乘数，nb存储乘数，nc存储积 fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);//将na,nb,nc都置为0 for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0';//将字符串表示的大整形数转成i整形数组表示的大整形数 for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0'; for(int i=1;i<=La;i++) for(int j=1;j<=Lb;j++) nc[i+j-1]+=na[i]*nb[j];//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位） for(int i=1;i<=La+Lb;i++) nc[i+1]+=nc[i]/10,nc[i]%=10;//统一处理进位 if(nc[La+Lb]) s+=nc[La+Lb]+'0';//判断第i+j位上的数字是不是0 for(int i=La+Lb-1;i>=1;i--) s+=nc[i]+'0';//将整形数组转成字符串 return s; } ``` ### 11.取模优化卡常 ```c++ inline void add(int &a, int b) { a = (a + b) >= mod ? (a + b - mod) : (a + b); } inline void sub(int &a, int b) { a = (a - b) < 0 ? (a - b + mod) : (a - b); } ``` ### 12.自动取模 ```c++ int norm(int x) { if (x < 0) { x += mod; } if (x >= mod) { x -= mod; } return x; } template<class T> T power(T aa, long long bb) { T res = 1; for (; bb; bb /= 2, aa *= aa) if (bb % 2) res *= aa; return res; } struct Z { int x; Z(int x = 0) : x(norm(x)) {} // Z(long long x) : x(norm(x % mod)) {} int val() const { return x; } Z operator-() const { return Z(norm(mod - x)); } Z inv() const { assert(x != 0); return power(*this, mod - 2); } Z &operator*=(const Z &rhs) { x = 1ull * x * rhs.x % mod; return *this; } Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; } Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; } Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); } friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; } friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; } friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; } friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; } friend std::istream &operator>>(std::istream &is, Z &a) { int v; is >> v; a = Z(v); return is; } friend std::ostream &operator<<(std::ostream &os, const Z &a) { return os << a.val(); } }; ``` ## 二、排序 ### 1.快速排序 ```c++ int a[N],n; void quick_sort(int l, int r){ int i = l, j = r; int mid = (l + r) / 2; int x = a[mid] ; while (i <= j){ while (a[i] < x) i++; while (a[j] > x) j--; if( i <= j ){ swap (a[i],a[j]); i++; j--; } if (l < j) quick_sort(l,j); if (i < r) quick_sort(i,r); } } ``` ### 2.归并排序（求逆序数） ```c++ int a[N],n; int b[N],cnt=0; // cnt可用于计算逆序数 void hebin(int l,int r){ int mid = ( l + r ) / 2; int p = l , q = mid + 1; for (int i = l ; i <= r ; i++) { if ( (q > r ) || (p <= mid && a[p] <= a[q] )){ b[i] = a[p++]; } else{ b[i] = a[q++]; cnt += mid - p + 1; } } for (int i=l ; i<= r ; i++) { a[i] = b[i]; } } void merge_sort (int l , int r ){ if (l == r) return ; int mid = ( l + r ) / 2; merge_sort(l,mid); merge_sort(mid+1,r); hebin(l,r); } ``` ## 三、二分法 ### 1.二分 ```c++ int l = 1 , r = N; while (l <= r){ int mid = (l + r) / 2; if(deal(mid)) l = mid + 1; // deal（）用于判断是否可行 else r = mid - 1; } int ans = l + 1; ``` ### 2.尺取法 ```c++ int l = 1 , r = 1; while (l<=n){ if(deal() && l < r) r++; else l++; } ``` ## 四、数据结构 ### 1.树状数组 说明： ```c++ int d[N]; int lowbit(int x){//获取最后一位的1 return x&(-x); } int query(int x){ // 询问1-x的和。 int ans=0; while (x){ ans+=d[x]; x-=lowbit(x); } return ans; } void add(int i,int k ) {// 修改单点值 while (i<=n){ d[i]+=k; i+=lowbit(i); } } int main(){ return 0; } ``` ### 2.线段树 ```c++ struct Segment_Tree { vector<int> tag, sum, A; int Mi = 1, Ma = 1e9; Segment_Tree(int M) : tag((M + 1) * 4, 0), sum((M + 1) * 4, 0), A(M + 1, 0) { Ma = M; } inline void pushup(int &p) { sum[p] = sum[p << 1] + sum[p << 1 | 1]; } inline void pushdown(int &p, int &l, int &r, int &mid) { if (tag[p]) { int &W = tag[p]; sum[p << 1] += (mid - l + 1) * W, sum[p << 1 | 1] += (r - mid) * W; tag[p << 1] += W, tag[p << 1 | 1] += W; W = 0; } } inline void build(int p, int l, int r) { if (l == r) { sum[p] = A[l]; return; } int mid = l + r >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pushup(p); } inline void build() { build(1, Mi, Ma); } inline void add(int p, int l, int r, int x, int y, int w) { if (x <= l && r <= y) { sum[p] += w * (r - l + 1); tag[p] += w; return; } int mid = l + r >> 1; pushdown(p, l, r, mid); if (x <= mid) add(p << 1, l, mid, x, y, w); if (y > mid) add(p << 1 | 1, mid + 1, r, x, y, w); pushup(p); } inline void add(int x, int y, int w) { add(1, Mi, Ma, x, y, w); } inline int query(int p, int l, int r, int x, int y) { if (x <= l && r <= y) return sum[p]; int mid = l + r >> 1, Ans = 0; pushdown(p, l, r, mid); if (x <= mid) Ans += query(p << 1, l, mid, x, y); if (y > mid) Ans += query(p << 1 | 1, mid + 1, r, x, y); return Ans; } inline int query(int l, int r) { return query(1, Mi, Ma, l, r); } }; ``` ### 3.莫队 对区间分块 每组再按照右端点排序 ```c++ const int N = 1e6 + 10; int n,m;int a[N],beg[N]; int in[N]; struct ty{ int l,r,id; }s[N]; bool cmp(ty A, ty B) { return beg[A.l] == beg[B.l] ? A.r < B.r : beg[A.l] < beg[B.l]; } int qes[N]; int ans=0; int main(){ read(n); for(int i = 1; i <= ceil((double) n / sqrt(n)); ++ i) for(int j = (i - 1) * sqrt(n) + 1; j <= i * sqrt(n); ++ j) beg[j] = i;//这是分的块 for(int i=1;i<=n;i++) read(a[i]); read(m); for(int i=1;i<=m;i++){ read(s[i].l);read(s[i].r);s[i].id=i; } sort(s+1,s+1+m,cmp); for(int i=1,l=1,r=0;i<=m;i++){ while(r<s[i].r) if(++in[a[++r]]==1) ans++; while(r>s[i].r) if(--in[a[r--]]==0) ans--; while(l<s[i].l) if(--in[a[l++]]==0) ans--; while(l>s[i].l) if(++in[a[--l]]==1) ans++; qes[s[i].id]=ans; } for(int i=1;i<=m;i++) printf("%d\n",qes[i]); return 0; } ``` ### 4.主席树 维护区间第k大 ```c++ #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; struct ty{ int l,r,sum; }tree[N<<5]; int a[N],number[N],root[N],node_num; void build(int l,int r,int &node){ node=++node_num; if(l==r)return; int mid=(l+r)>>1; build(l,mid,tree[node].l); build(mid+1,r,tree[node].r); } void add(int l,int r,int &node,int pre,int pos){ node=++node_num; tree[node]=tree[pre]; tree[node].sum++; if(l==r)return; int mid=(l+r)>>1; if(pos<=mid) add(l,mid,tree[node].l,tree[pre].l,pos); else add(mid+1,r,tree[node].r,tree[pre].r,pos); } int query(int l,int r,int node,int pre,int k){ if(l==r)return l; int chal=tree[tree[node].l].sum-tree[tree[pre].l].sum; int mid=(l+r)>>1; if(k<=chal)return query(l,mid,tree[node].l,tree[pre].l,k); else return query(mid+1,r,tree[node].r,tree[pre].r,k-chal); } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); number[i]=a[i]; } sort(number+1,number+1+n); int num=unique(number+1,number+1+n)-number-1; node_num=0; build(1,num,root[0]); for(int i=1;i<=n;i++){ int pos=lower_bound(number+1,number+1+num,a[i])-number; add(1,num,root[i],root[i-1],pos); } int l,r,k; while(m--){ scanf("%d%d%d",&l,&r,&k); int pos=query(1,num,root[r],root[l-1],k); printf("%d\n",number[pos]); } return 0; } ``` ### 5.ST表 ```c++ const int N = 1e6 + 10; int A[N]; struct ST { vector<vector<int>> Mi, Ma; vector<int> Lg; int n; ST(int M) : Mi(M + 1, vector<int>(21)), Ma(M + 1, vector<int>(21)), Lg(M + 1) { n = M; for (int i = 1; i <= n; i++) Ma[i][0] = Mi[i][0] = A[i]; for (int j = 1; j <= 20; j++) { for (int i = 1; i <= n - (1 << j) + 1; i++) { Ma[i][j] = max(Ma[i][j - 1], Ma[i + (1 << (j - 1))][j - 1]); Mi[i][j] = min(Mi[i][j - 1], Mi[i + (1 << (j - 1))][j - 1]); } } Lg[0] = -1; for (int i = 1; i <= n; i++) { Lg[i] = Lg[i >> 1] + 1; } } inline int query_Min(int l, int r) { int k = Lg[r - l + 1]; return min(Mi[l][k], Mi[r - (1 << k) + 1][k]); } inline int query_Max(int l, int r) { int k = Lg[r - l + 1]; return max(Ma[l][k], Ma[r - (1 << k) + 1][k]); } }; ``` ### 6.可持久化线段树 ```c++ #include<bits/stdc++.h> using namespace std; const int maxn = 1e5; // 数据范围 int tot, n, m; int sum[(maxn << 5) + 10],rt[maxn + 10], ls[(maxn << 5) + 10],rs[(maxn << 5) + 10]; int a[maxn + 10], ind[maxn + 10], len; inline int getid(const int &val) { // 离散化 return lower_bound(ind + 1, ind + len + 1, val) - ind; } int build(int l, int r) { // 建树 int root = ++tot; if (l == r) return root; int mid = l + r >> 1; ls[root] = build(l, mid); rs[root] = build(mid + 1, r); return root; // 返回该子树的根节点 } int update(int k, int l, int r, int root) { // 插入操作 int dir = ++tot; ls[dir] = ls[root], rs[dir] = rs[root], sum[dir] = sum[root] + 1; if (l == r) return dir; int mid = l + r >> 1; if (k <= mid) ls[dir] = update(k, l, mid, ls[dir]); else rs[dir] = update(k, mid + 1, r, rs[dir]); return dir; } int query(int u, int v, int l, int r, int k) { // 查询操作 int mid = l + r >> 1, x = sum[ls[v]] - sum[ls[u]]; // 通过区间减法得到左儿子中所存储的数值个数 if (l == r) return l; if (k <= x) // 若 k 小于等于 x ，则说明第 k 小的数字存储在在左儿子中 return query(ls[u], ls[v], l, mid, k); else // 否则说明在右儿子中 return query(rs[u], rs[v], mid + 1, r, k - x); } inline void init() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", a + i); memcpy(ind, a, sizeof ind); sort(ind + 1, ind + n + 1); len = unique(ind + 1, ind + n + 1) - ind - 1; rt[0] = build(1, len); for (int i = 1; i <= n; ++i) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]); } int l, r, k; inline void work() { while (m--) { scanf("%d%d%d", &l, &r, &k); printf("%d\n", ind[query(rt[l - 1], rt[r], 1, len, k)]); // 回答询问 } } int main() { init(); work(); return 0; } ``` ### 7.分块算法 ```c++ int len; int fir[N],sec[N],sz[N],blo[N]; ll sum[N],lazy[N],a[N]; void pre(int n){ len=sqrt(n); for(int i=1;i<=len;i++){ fir[i]=n/len*(i-1)+1; sec[i]=n/len*i; } sec[len]=n; for(int i=1;i<=len;i++){ for(int j=fir[i];j<=sec[i];j++){ blo[j]=i; sum[i]+=a[j]; } } for(int i=1;i<=len;i++){ sz[i]=sec[i]-fir[i]+1; } } void update(int x,int y,ll k){ if(blo[x]==blo[y]){ for(int i=x;i<=y;i++){ a[i]+=k; sum[blo[i]]+=k; } return ; } for(int i=x;i<=sec[blo[x]];i++){ a[i]+=k;sum[blo[i]]+=k; } for(int i=y;i>=fir[blo[y]];i--){ a[i]+=k;sum[blo[i]]+=k; } for(int i=blo[x]+1;i<blo[y];i++){ lazy[i]+=k; } } ll query(int x,int y){ ll res=0; if(blo[x]==blo[y]){ for(int i=x;i<=y;i++){ res+=a[i]+lazy[blo[i]]; } }else{ for(int i=x;i<=sec[blo[x]];i++){ res+=a[i]+lazy[blo[i]]; } for(int i=y;i>=fir[blo[y]];i--){ res+=a[i]+lazy[blo[i]]; } for(int i=blo[x]+1;i<blo[y];i++){ res+=sum[i]+lazy[i]*sz[i]; } } return res; } ``` ### 8.笛卡尔树 ```c++ const int N = 1e7 + 10; int a[N]; stack<int>st; int ls[N],rs[N]; int main(){ int n=read(); for(int i=1;i<=n;i++) a[i]=read(); int root=0; for(int i=1;i<=n;i++){ while(!st.empty() && a[i]<a[st.top()]){ls[i]=st.top();st.pop();} if(st.empty()) root=i; else rs[st.top()]=i; st.push(i); } return 0; } ``` HDU 1506 最大子矩形 > 题目大意： 个位置，每个位置上的高度是 ，求最大子矩阵。举一个例子，如下图： > >  > > 阴影部分就是图中的最大子矩阵。 这道题你可 DP，可单调栈，但你万万没想到的是它也可以笛卡尔树！具体地，我们把下标作为键值 k， hi 作为键值 w满足小根堆性质，构建一棵(i,hi)的笛卡尔树。 这样我们枚举每个结点u ，把 Uw（即结点 u的高度键值 h）作为最大子矩阵的高度。由于我们建立的笛卡尔树满足小根堆性质，因此u 的子树内的结点的高度都大于等于u 。而我们又知道 u子树内的下标是一段连续的区间。于是我们只需要知道子树的大小，然后就可以算这个区间的最大子矩阵的面积了。用每一个点计算出来的值更新答案即可。显然这个可以一次 DFS 完成，因此复杂度仍是O(n)的。 ```c++ #include<bits/stdc++.h> #define ll long long using namespace std; const int N = 1e6 + 10; struct ty{ int ls,rs; }tr[N]; int a[N]; stack<int>st; ll ans=0; int siz[N]; void dfs(int x){ if(!x) return ; dfs(tr[x].ls); dfs(tr[x].rs); siz[x]=siz[tr[x].ls]+siz[tr[x].rs]+1; ans=max(ans,1ll*siz[x]*a[x]); } void solve(){ int n; while(scanf("%d",&n)!=EOF){ if(n==0) break; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) tr[i].ls=tr[i].rs=0; int root=0; while(!st.empty()) st.pop(); for(int i=1;i<=n;i++){ while(!st.empty() && a[i]<a[st.top()]){ tr[i].ls=st.top();st.pop(); } if(st.empty()) root=i; else{ tr[st.top()].rs=i; } st.push(i); } ans=0; dfs(root); printf("%lld\n",ans); } } int main(){ solve(); return 0; } ``` ### 9.珂朵莉树 ```c++ int n; struct Node_t { int l, r; mutable int v; Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {} inline bool operator<(const Node_t &o) const { return l < o.l; } }; set<Node_t> odt; set<Node_t>::iterator split(int x) { if (x > n) return odt.end(); auto it = --odt.upper_bound(Node_t {x, 0, 0}); if (it->l == x) return it; int l = it->l, r = it->r, v = it->v; odt.erase(it); odt.insert(Node_t(l, x - 1, v)); return odt.insert(Node_t(x, r, v)).first; } void assign(int l, int r, int v) { auto itr = split(r + 1), itl = split(l); odt.erase(itl, itr); odt.insert(Node_t(l, r, v)); } void performance(int l, int r) { auto itr = split(r + 1), itl = split(l); for (; itl != itr; ++itl) { // Perform Operations here } } ``` ### 10.线段树动态开点 ```c++ struct Tree { #define LOG 30 int root, cnt, Mi, Ma; vector<int> ls, rs, sum; Tree(int M = 0, int Min = 1, int Max = 1e9) : ls(M * LOG), rs(M * LOG), sum(M * LOG) { root = 0, cnt = 0; Mi = Min, Ma = Max; } inline void pushup(int p) { sum[p] = sum[ls[p]] + sum[rs[p]]; } inline void update(int &p, int l, int r, int x, int w) { if (!p) p = ++cnt; if (l == r) { sum[p] += w; return; } int mid = l + r >> 1; if (x <= mid) update(ls[p], l, mid, x, w); else update(rs[p], mid + 1, r, x, w); pushup(p); } inline void update(int x, int w) { update(root, Mi, Ma, x, w); } inline int query(int p, int l, int r, int x, int y) { if (!p) return 0; if (x <= l && r <= y) return sum[p]; int ans = 0; int mid = l + r >> 1; if (x <= mid) ans += query(ls[p], l, mid, x, y); if (y > mid) ans += query(rs[p], mid + 1, r, x, y); return ans; } inline int query(int l, int r) { return query(root, Mi, Ma, l, r); } }; ``` ### 11.吉老师线段树 ```c++ int a[N]; struct Tree { ll SUM[N << 2], MAX[N << 2], C_MAX[N << 2], CNT[N << 2]; ll lazy[N << 2]; void pushup(int p, int l, int r) { SUM[p] = SUM[p << 1] + SUM[p << 1 | 1]; if (MAX[p << 1] == MAX[p << 1 | 1]) { MAX[p] = MAX[p << 1]; CNT[p] = CNT[p << 1] + CNT[p << 1 | 1]; C_MAX[p] = max(C_MAX[p << 1], C_MAX[p << 1 | 1]); } else if (MAX[p << 1] > MAX[p << 1 | 1]) { MAX[p] = MAX[p << 1]; CNT[p] = CNT[p << 1]; C_MAX[p] = max(C_MAX[p << 1], MAX[p << 1 | 1]); } else { MAX[p] = MAX[p << 1 | 1]; CNT[p] = CNT[p << 1 | 1]; C_MAX[p] = max(C_MAX[p << 1 | 1], MAX[p << 1]); } } void build(int p, int l, int r) { lazy[p] = -1; if (l == r) { SUM[p] = MAX[p] = a[l]; CNT[p] = 1; C_MAX[p] = -INF; return; } int mid = l + r >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); pushup(p, l, r); } void modify(int p, int l, int r, ll w) { if (MAX[p] <= w) return; SUM[p] += (w - MAX[p]) * CNT[p]; MAX[p] = lazy[p] = w; } void pushdown(int p, int l, int r) { if (lazy[p] == -1)return; int mid = l + r >> 1; modify(p << 1, l, mid, lazy[p]); modify(p << 1 | 1, mid + 1, r, lazy[p]); lazy[p] = -1; } void update1(int p, int l, int r, int x, int y, ll w) {//区间取min操作 if (MAX[p] <= w) return; if (x <= l && r <= y && w > C_MAX[p]) { modify(p, l, r, w); return; } int mid = l + r >> 1; pushdown(p, l, r); if (x <= mid) update1(p << 1, l, mid, x, y, w); if (y > mid) update1(p << 1 | 1, mid + 1, r, x, y, w); pushup(p, l, r); } ll query_max(int p, int l, int r, int x, int y) {//区间最大值 if (x <= l && r <= y) return MAX[p]; ll ans = -INF; int mid = l + r >> 1; pushdown(p, l, r); if (x <= mid) ans = max(ans, query_max(p << 1, l, mid, x, y)); if (y > mid) ans = max(ans, query_max(p << 1 | 1, mid + 1, r, x, y)); return ans; } ll query(int p, int l, int r, int x, int y) {//求区间和 if (x <= l && r <= y) return SUM[p]; int mid = l + r >> 1; pushdown(p, l, r); ll ans = 0; if (x <= mid) ans += query(p << 1, l, mid, x, y); if (y > mid) ans += query(p << 1 | 1, mid + 1, r, x, y); return ans; } } tr; ``` ### 12.线段树二分 ```c++ struct Tree { int sum[N], lazy[N]; void pushup(int p, int l, int r) { sum[p] = sum[p << 1] + sum[p << 1 | 1]; } void pushdown(int p, int l, int r) { sum[p << 1] = sum[p << 1 | 1] = 0; lazy[p << 1] = lazy[p << 1 | 1] = 1; lazy[p] = 0; } void modify(int p, int l, int r, int x, int y) { if (l == r) { sum[p] = 0; lazy[p] = 1; return; } if (lazy[p])pushdown(p, l, r); int mid = l + r >> 1; if (x <= mid) modify(p << 1, l, mid, x, y); if (y > mid) modify(p << 1 | 1, mid + 1, r, x, y); pushup(p, l, r); } int query(int p, int l, int r, int x, int y) { if (l == r) return sum[p]; if (lazy[p])pushdown(p, l, r); int mid = l + r >> 1; int ans = 0; if (x <= mid)ans += query(p << 1, l, mid, x, y); if (y > mid)ans += query(p << 1 | 1, mid + 1, r, x, y); return ans; } void update(int p, int l, int r, int f) { if (l == r) { return; } pushdown(p, l, r); int mid = l + r >> 1; int now = mid - l + 1 - sum[p << 1]; if (now >= f) { update(p << 1, l, mid, f); } else { update(p << 1 | 1, mid + 1, r, f - now); } } } tr; ``` ### 13.左偏树 ```c++ const int N = 1e5 + 10; /* * 左偏树 * dis[x] 表示 x 到离他最近的叶子结点的距离 , 由于左偏性质 dis[x.lc] >= dis[x.rc] * 具有堆性质(例如小根堆) 对于每一个结点 x , 有 v[x] <= v[x.lc] && v[x] <= v[x.rc] * * 基本结论： * dis[x] = dis[x.rc] + 1; * 距离为 n 的左偏树 至少有 2^(n+1)-1 个结点 * 有 n 个结点的左偏树的距离是 log2(n) 的 * * 例题: 洛谷 P3377 * 维护小根堆合并与删除。 */ int A[N]; bool vis[N]; int lc[N], rc[N], dis[N], fa[N]; int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } int merge(int x, int y) { if (!x || !y) return x + y; if (A[y] < A[x]) swap(x, y); rc[x] = merge(rc[x], y); if (dis[lc[x]] < dis[rc[x]]) swap(lc[x], rc[x]); dis[x] = dis[rc[x]] + 1; return x; } void solve() { int n = read(), m = read(); for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1; i <= n; i++) A[i] = read(); while (m--) { int op = read(); if (op == 1) { int x = read(), y = read(); if (vis[x] || vis[y]) continue; int fx = find(x), fy = find(y); if (fx != fy) fa[fx] = fa[fy] = merge(fx, fy); } else { int x = read(); if (vis[x]) { printf("-1\n"); continue; } x = find(x); printf("%d\n", A[x]); vis[x] = 1; fa[lc[x]] = fa[rc[x]] = fa[x] = merge(lc[x], rc[x]); lc[x] = rc[x] = dis[x] = 0; } } ``` ### 14.平衡树 ```c++ const int N = 1e6 + 10; /* 普通平衡树 * 利用BST性质查询和修改，利用随机和堆优先级来保持平衡，把树的深度控制在log N，保证了操作效率 * 操作： * 1.插入 x * 2.删除 x * 3.查询 x 的排名 * 4.查询排名为 x 的数是什么 * 5.求 x 的前驱 (小于x 最大的数) * 6.求 x 的后继 (大于x 最小的数) * * ch[i][0] 表示 i 的左儿子 ， ch[i][1] 表示 i 的右儿子 * val[i] 表示节点 i 的价值 , dat[i] 是随机生成的优先级 * siz[i] 表示子树的大小 ， cnt[i] 表示节点包含的副本数 * 通过增加属性，结合BST的性质可以达到一些效果，如size(子树大小，查询排名)，cnt(每个节点包含的副本数) * */ int ch[N][2]; int val[N], dat[N], siz[N], cnt[N]; int Root, tot; int New(int v) { val[++tot] = v; dat[tot] = rand(); siz[tot] = cnt[tot] = 1; return tot; } void pushup(int p) { siz[p] = siz[ch[p][0]] + siz[ch[p][1]] + cnt[p]; } void build() { Root = New(-inf), ch[Root][1] = New(inf); pushup(Root); } // 看图理解一下Rotate void Rotate(int &p, int d) {// d表示旋转方向 ， 0 为左旋, 1 为右旋 int tmp = ch[p][d ^ 1]; ch[p][d ^ 1] = ch[tmp][d]; ch[tmp][d] = p; p = tmp; pushup(ch[p][d]), pushup(p); } void insert(int &p, int v) { if (!p) { p = New(v); return; } if (v == val[p]) cnt[p]++; else { int d = v < val[p] ? 0 : 1; insert(ch[p][d], v); if (dat[p] < dat[ch[p][d]]) Rotate(p, d ^ 1); } pushup(p); } void Remove(int &p, int v) { if (!p) return; if (v == val[p]) {// 找到了该值 if (cnt[p] > 1) { return cnt[p]--, pushup(p); } if (ch[p][0] || ch[p][1]) {// 只发现了一个值 if (!ch[p][1] || dat[ch[p][0]] > dat[ch[p][1]]) Rotate(p, 1), Remove(ch[p][1], v); else Rotate(p, 0), Remove(ch[p][0], v); pushup(p); } else p = 0; return; } v < val[p] ? Remove(ch[p][0], v) : Remove(ch[p][1], v); pushup(p); } int Get_rank(int p, int v) { if (!p) return inf; if (v == val[p]) return siz[ch[p][0]] + 1; else if (v < val[p]) return Get_rank(ch[p][0], v); else return siz[ch[p][0]] + cnt[p] + Get_rank(ch[p][1], v); } int Get_val(int p, int rank) { if (!p) return inf; if (rank <= siz[ch[p][0]]) return Get_val(ch[p][0], rank); else if (rank <= siz[ch[p][0]] + cnt[p]) return val[p]; else return Get_val(ch[p][1], rank - siz[ch[p][0]] - cnt[p]); } int Get_pre(int v) { int p = Root, pre; while (p) { if (val[p] < v) pre = val[p], p = ch[p][1]; else p = ch[p][0]; } return pre; } int Get_suf(int v) { int p = Root, suf; while (p) { if (val[p] > v)suf = val[p], p = ch[p][0]; else p = ch[p][1]; } return suf; } void solve() { build(); int n = read(); for (int i = 1; i <= n; i++) { int op = read(), x = read(); if (op == 1) insert(Root, x); if (op == 2) Remove(Root, x); if (op == 3) printf("%d\n", Get_rank(Root, x) - 1); if (op == 4) printf("%d\n", Get_val(Root, x + 1)); if (op == 5) printf("%d\n", Get_pre(x)); if (op == 6) printf("%d\n", Get_suf(x)); } } ``` ### 15.扫描线 ```c++ const int N = 1e5 + 10; int X[N << 1]; struct Line { ll l, r, H; int op; bool operator<(const Line &thi) const { return H < thi.H; } } Line[N << 1]; struct SegTree { int Left[N << 4], Right[N << 4], lazy[N << 4]; ll len[N << 4]; void build(int p, int l, int r) { Left[p] = l, Right[p] = r; if (l == r) return; int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); } void pushup(int p) { int l = Left[p], r = Right[p]; if (lazy[p]) len[p] = X[r + 1] - X[l]; else len[p] = len[p << 1] + len[p << 1 | 1]; } void update(int p, int l, int r, int c) { int L = Left[p], R = Right[p]; if (X[R + 1] <= l || r <= X[L]) return; if (l <= X[L] && X[R + 1] <= r) { lazy[p] += c; pushup(p); return; } update(p << 1, l, r, c); update(p << 1 | 1, l, r, c); pushup(p); } } tr; void solve() { int n = read(); for (int i = 1; i <= n; i++) { int X1 = read(), Y1 = read(), X2 = read(), Y2 = read(); X[2 * i - 1] = X1, X[2 * i] = X2; Line[2 * i - 1] = {X1, X2, Y1, 1}; Line[2 * i] = {X1, X2, Y2, -1}; } n <<= 1; sort(Line + 1, Line + 1 + n); sort(X + 1, X + 1 + n); int tot = unique(X + 1, X + 1 + n) - X - 1; tr.build(1, 1, tot - 1); ll Ans = 0; for (int i = 1; i < n; i++) { tr.update(1, Line[i].l, Line[i].r, Line[i].op); Ans += 1ll * tr.len[1] * (Line[i + 1].H - Line[i].H); } printf("%lld\n", Ans); } ``` ## 五、动态规划 ### 1.求最大子段（子矩阵）的和 #### I.最大字段和 ```c++ ll a[N],dp[N]; ll ans=-inf; int main(){ int n=read(); for(int i=1;i<=n;i++) a[i]=read(),ans=max(ans,a[i]); dp[1]=max(0,a[1]); for(int i=2;i<=n;i++) dp[i]=max(a[i],dp[i-1]+a[i]),ans=max(dp[i],ans); return 0; } ``` #### II.最大子矩阵 ```c++ #include<bits/stdc++.h> using namespace std; const int N = 500+10; int a[N][N],b[N][N],dp[N];//b[j][k]表示从i行加到j行 第k列值的大小，将二维转为一维 int ans,n; void solve(int j){ memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { dp[i]=max(b[j][i],b[j][i]+dp[i-1]); ans=max(ans,dp[i]); } } int main(){ n=read(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=read(); } } for(int i=1;i<=n;i++){//从第i行开始加 memset(b,0,sizeof(b)); for(int j=i;j<=n;j++){//加到第j行 for(int k=1;k<=n;k++){//第k列 b[j][k]=a[j][k]+b[j-1][k]; } solve(j); } } printf("%d\n",ans); return 0; } ``` ### 2.求最长上升（下降）子序列 ```c++ int a[N],dp[N];//dp[i]长度为i的子序列的末端最小值 int len=0; int find(int x){ int l=1,r=len,mid; while(l<=r){ mid=(l+r)>>1; if(x>dp[mid]) l=mid+1; //记忆方法:求上升序列，就表示x更大，那么就是大于 else r=mid-1; } return l; } int work(int x){ int l=1,r=len,mid; while(l<=r){ mid=(l+r)>>1; if(x<=dp[mid]) l=mid+1; //记忆方法:求不增序列 else r=mid-1; } return l; } int main(){ int n=0; while(scanf("%d",&a[++n])!=EOF); n--; len=0; for (int i=1;i<=n;i++) { int k=work(a[i]); dp[k]=a[i]; len=max(len,k); } printf("%d\n",len); len=0; for (int i =1;i<=n;i++) { int k=find(a[i]); dp[k]=a[i]; len=max(len,k); } printf("%d",len); return 0; } ``` ### 3.最长公共子序列 ```c++ char a[5010],b[5010]; int dp[5010][5010]; int dpp[5010][5010]; //dp[i][j]表示字符串A的前i个字符和字符串b的前j个字符的LCS(最长公共子序列的长度) //dpp[i][j]表示字符串A的前i个字符和字符串b的前j个字符最长公共子序列个数 int main() { int cnt1=0; while (scanf("%c",&a[++cnt1])) { if(a[cnt1]=='.') break; } getchar(); int cnt2=0; while (scanf("%c",&b[++cnt2])) { if(b[cnt2]=='.') break; } cnt1--;cnt2--; for (int i=0;i<=cnt1;i++) dpp[i][0]=1; for (int i=0;i<=cnt2;i++) dpp[0][i]=1; for (int i=1;i<=cnt1;i++) for (int j=1;j<=cnt2;j++) { if(a[i]==b[j]) { dp[i][j]=dp[i-1][j-1]+1; dpp[i][j]=dpp[i-1][j-1]; } else { dp[i][j]=max(dp[i-1][j],dp[i][j-1]); if(dp[i][j]==dp[i-1][j-1]) dpp[i][j]=(dpp[i][j]-dpp[i-1][j-1]+mod)%mod; } if(dp[i][j]==dp[i-1][j]) dpp[i][j]=(dpp[i][j]+dpp[i-1][j])%mod; if(dp[i][j]==dp[i][j-1]) dpp[i][j]=(dpp[i][j]+dpp[i][j-1])%mod; } printf("%d\n%lld",dp[cnt1][cnt2],dpp[cnt1][cnt2]); return 0; } ``` ### 4.背包问题 #### I. #### II. ### 5.换根dp ```c++ vector<int>G[N]; int siz[N],dep[N],n; ll dp[N],ans; void dfs1(int x,int fa){ for(int i=0;i<G[x].size();i++){ int u=G[x][i]; if(u==fa) continue; dep[u]=dep[x]+1; ans+=dep[u]; dfs1(u,x); siz[x]+=siz[u]; } siz[x]+=1; } void dfs2(int x,int fa){ ans=min(ans,dp[x]); for(int i=0;i<G[x].size();i++){ int u=G[x][i]; if(u==fa) continue; dp[u]=dp[x]+n-2*siz[u]; dfs2(u,x); } } int main(){ scanf("%d",&n); for(int i=1;i<n;i++){ int x,y;scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } dfs1(1,-1); // 先求出以1为根 dp[1]=ans; dfs2(1,-1);//进行转移 printf("%lld\n",ans); return 0; } ``` ## 六、数学 ### 1.拓展欧几里得算法 ```c++ ll ext_gcd(ll a,ll b,ll& x,ll& y){ ll d =a; if(!b){ x=1;y=0; }else{ d=ext_gcd(b,a%b,y,x); y-=a/b*x; } return d; } ``` ### 2.中国剩余定理（孙子定理） ```c++ ll sunzi(ll *m,ll *a,int len){ ll lcm=1; ll ans=0; for (int i=0;i<len;i++){ ll k0,ki; ll d=ext_gcd(lcm,m[i],k0,ki); if((a[i]-ans)%d!=0) return -1; else{ ll t =m[i]/d; k0 = ( k0*(a[i]-ans)/d%t + t)%t; ans = k0*lcm + ans; lcm = lcm/d*m[i]; } } return ans; } ``` ### 3.组合数 ```c++ struct Combinatorial_mathematics { vector<int> fac, inv; inline int add(int &x, int y) { return x + y >= mod ? x + y - mod : x + y; } inline int sub(int &x, int y) { return x - y < 0 ? x - y + mod : x - y; } inline int mul(int &x, int y) { return 1ull * x * y % mod; } inline int powmod(int a, int b) { int res = 1; while (b) { if (b & 1) res = mul(res, a); b >>= 1; a = mul(a, a); } return res; } inline int Inv(int x) { return powmod(x, mod - 2); } Combinatorial_mathematics(int m = 0) : fac(m + 1), inv(m + 1) { fac[0] = 1; for (int i = 1; i <= m; i++) fac[i] = mul(fac[i - 1], i); inv[m] = Inv(fac[m]); for (int i = m; i >= 1; i--) inv[i - 1] = mul(inv[i], i); } inline int C(int n, int m) { if (n < m || n < 0 || m < 0) return 0; return mul(fac[n], mul(inv[m], inv[n - m])); } }; ``` ### 4.BSGS 用来求a的x次方与b同余mod p 的最小根 ```c++ ll bsgs(ll a, ll b, ll Mod) { map<ll, ll> mp; ll cur = 1, t = sqrt(Mod) + 1; for (int B = 1; B <= t; B++) { cur = cur * a % Mod; mp[b * cur % Mod] = B; } ll now = cur; for (int A = 1; A <= t; A++) { if (mp[now]) return 1ll * A * t - mp[now]; else now = now * cur % Mod; } return -1; } ``` ### 5.矩阵快速幂 求斐波那契数列 ```c++ #include<bits/stdc++.h> #define ll long long using namespace std; const int mod = 1e9 + 7; const int MAX=5; int n=2; struct Mat{ ll a[MAX][MAX]; Mat(){ memset(a,0,sizeof(a)); } inline void clear(){ memset(a,0,sizeof(a)); } inline void build_E(){ //构造单位矩阵 for (int i=1;i<=n;i++) a[i][i]=1; } inline void init(){ //构造变化矩阵 a[1][1]=1;a[1][2]=1;a[2][1]=1; } }base; Mat operator *(const Mat &x,const Mat &y){// 重载 * 运算符 Mat res; for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod; } } } return res; } inline Mat powmod_Mat(int b){ // 矩阵快速幂 Mat ans;ans.build_E(); while(b){ if(b&1) ans=ans*base; base=base*base; b>>=1; } return ans; } int main(){ int k; while(scanf("%d",&k)!=EOF){ base.clear(); base.init(); Mat ans=powmod_Mat(k); printf("%lld\n",ans.a[2][1]); } return 0; } ``` ``` f[n]=a*f[n-1]+b*f[n-2]+c |a b 1| |f[n-1]| | f[n] | |1 0 1| * |f[n-2]| = | f[n-1]| |0 0 1| | c | | c | f[n]=c^n -f[n-1] |-1 c| * |f[n-1]| = |f[n]| |0 c| | n-1 | | n | ``` ### 6.多项式 #### I.FFT 快速傅里叶变换 ##### 1.复数运算，重载运算符 对于多项式f(x) 与 g(x) 求 f(x)*g(x) 的各项系数 ```c++ const double Pi=acos(-1.0); struct Complex{ double x,y; Complex (double xx=0,double yy=0){x=xx,y=yy;} inline Complex operator + (const Complex a) const { return Complex(x + a.x , y + a.y);} inline Complex operator - (const Complex a) const { return Complex(x - a.x , y - a.y);} inline Complex operator * (const Complex a) const { return Complex(x * a.x - y * a.y , x * a.y + y * a.x);} }a[N],b[N]; int l,r[N],n,m; int limit=1; void FFT(Complex *A,int type){ for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]);//求出要迭代的序列 for(int mid=1;mid<limit;mid<<=1){//待合并区间的中点 Complex Wn( cos(Pi/mid) , type*sin(Pi/mid) ); //单位根 for(int R=mid<<1,j=0;j<limit;j+=R){//R是区间的右端点，j表示前已经到哪个位置了 Complex w(1,0);//幂 for(int k=0;k<mid;k++,w=w*Wn){//枚举左半部分 Complex x=A[j+k],y=w*A[j+mid+k];//蝴蝶效应 A[j+k]=x+y; A[j+mid+k]=x-y; } } } } void pre_FFT(){ while(limit<=n+m) limit<<=1,l++; for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); } void mul(){ FFT(a,1);FFT(b,1); for(int i=0;i<=limit;i++) a[i]=a[i]*b[i]; FFT(a,-1); } ``` #### II.NTT 快速数论变换 对于多项式f(x) 与 g(x) 求 f(x)*g(x) 的各项系数 // 优化大数乘法 ```c++ #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+10; const int mod = 998244353, G = 3, Gi = 332748118; int limit=1,l,r[N]; ll a[N],b[N];int n,m; ll powmod(ll a,ll b){ ll res=1; while(b){ if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } inline void NTT(ll *A,int type){ for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]); for(int mid=1;mid<limit;mid<<=1){ ll Wn=powmod(type == 1 ? G : Gi , (mod - 1 ) / ( mid << 1)); for(int j=0;j<limit;j+=(mid<<1)){ ll w=1; for(int k=0;k<mid;k++,w=(w*Wn)%mod){ int x=A[j+k] ,y=w*A[j+k+mid]%mod; A[j+k] = ( x + y ) % mod; A[j+k+mid] = ( x - y + mod ) % mod; } } } } void pre_NTT(){ while(limit<=n+m) limit<<=1,l++; for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); } void mul(){ NTT(a,1);NTT(b,1); for(int i=0;i<limit;i++) a[i]=(a[i]*b[i])%mod; NTT(a,-1); ll inv=powmod(limit,mod-2); for(int i=0;i<=n+m;i++) a[i]=a[i]*inv%mod; } int main(){ string x,y;cin>>x>>y;n=x.length()-1;m=y.length()-1; for(int i=n;i>=0;i--) a[n-i]=x[i]-'0'; for(int i=m;i>=0;i--) b[m-i]=y[i]-'0'; pre_NTT(); mul(); return 0; } ``` ```c++ #include<bits/stdc++.h> #define Poly vector<int> #define ll long long using namespace std; template<const int Mod> struct ntt{ inline void add(int &a, int b) { a += b; if(a >= Mod) a -= Mod; } inline void sub(int &a, int b) { a -= b; if(a < 0) a += Mod; } inline int add2(int a, int b) { a += b; if(a >= Mod) a -= Mod; return a;} inline int sub2(int a, int b) { a -= b; if(a < 0) a += Mod; return a;} inline int mul(int a, int b) { return (1ll*a*b%Mod); } inline int powmod(int a, long long b) { int res = 1; while (b > 0) { if (b & 1) res = mul(res, a); a = mul(a, a); b >>= 1; } return res; } inline int inv(int a) { a %= Mod; if (a < 0) a += Mod; int b = Mod, u = 0, v = 1; while (a) { int t = b / a; b -= t * a; swap(a, b); u -= t * v; swap(u, v); } assert(b == 1); if (u < 0) u += Mod; return u; } int limit, root; vector<int> A, B; ntt() { int tmp = Mod - 1; limit = 0; while (tmp % 2 == 0) { tmp /= 2; limit++; } root = 2; while (powmod(root, (Mod-1)>>1) == 1) root++; A.resize(limit); B.resize(limit); for (int i = 0; i < limit; ++i){ sub(A[i], powmod(root, (Mod-1) >> (i+2))); B[i] = inv(A[i]); } } void fft(vector<int> &a, bool inv) { const int n = a.size(); assert((n & (n - 1)) == 0); assert(__builtin_ctz(n) <= limit); if(!inv){ for(int m=n;m>>=1;){ int w = 1; for(int s=0,k=0; s<n; s += 2*m){ for(int i=s, j=s+m ; i < s+m; ++i, ++j) { int x = a[i], y = mul(a[j], w); a[j] = (x>=y?x-y:x+Mod-y); a[i] = (x+y>=Mod?x+y-Mod:x+y); } w = mul(w, A[__builtin_ctz(++k)]); } } } else{ for(int m=1;m<n;m*=2){ int w = 1; for(int s=0,k=0; s<n; s += 2*m){ for(int i=s, j=s+m ; i < s+m; ++i, ++j) { int x = a[i], y = a[j]; a[j] = (x>=y?x-y:x+Mod-y); a[j] = mul(a[j], w); a[i] = (x+y>=Mod?x+y-Mod:x+y); } w = mul(w, B[__builtin_ctz(++k)]); } } } } vector<int> multiply(vector<int> a, vector<int> b, int eq = 0) { int need = a.size() + b.size() - 1; int nbase = 0; while ((1 << nbase) < need) nbase++; int sz = 1 << nbase; a.resize(sz); b.resize(sz); fft(a, 0); if (eq) b = a; else fft(b, 0); int inv_sz = inv(sz); for (int i = 0; i < sz; i++) { a[i] = mul(mul(a[i], b[i]), inv_sz); } fft(a, 1); a.resize(need); return a; } vector<int> square(vector<int> a) { return multiply(a, a, 1); } }; const int mod=998244353; char s[1100000]; int main(){ ntt<mod> t;// mod为对应的模数 Poly a,b; /* 构造 a,b */ Poly ans=t.multiply(a,b); // 输出答案 return 0; } ``` #### III.NTT维护01背包 ```c++ const int N = 1e6 + 10; const int inf = 0x3f3f3f3f; inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if (ch == '-')f = -1 ;ch = getchar();}while(ch >= '0' && ch <= '9'){ x = (x<<1) + (x<<3) + (ch^48);ch = getchar();}return x * f;} int k[N],n,limit,l,r[N],m; /* 求(1+x^a1)*(1+x^a2)*...*(1+x^an) 的展开式的各项系数 其中 a1 + a2 + ... + an <= 1e6 , ai >= 1 */ const int mod = 998244353, G = 3, Gi = 332748118; ll powmod(ll a,ll b){ ll res=1; while(b){ if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } inline void NTT(vector<ll>&A,int type){ for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]); for(int mid=1;mid<limit;mid<<=1){ ll Wn=powmod(type == 1 ? G : Gi , (mod - 1 ) / ( mid << 1)); for(int j=0;j<limit;j+=(mid<<1)){ ll w=1; for(int k=0;k<mid;k++,w=(w*Wn)%mod){ int x=A[j+k],y=w*A[j+k+mid]%mod; A[j+k] = ( x + y ) % mod; A[j+k+mid] = ( x - y + mod ) % mod; } } } } vector<ll> Ntt(int L,int R){ // cout<<' '<<L << ' '<< R << endl; if(L==R){ vector<ll>now(k[L]+1,0); now[0]=1;now[k[L]]=1; return now; } int mid=L+R>>1; vector<ll>a,b; a=Ntt(L,mid);b=Ntt(mid+1,R); limit=1,l=0;n=a.size();m=b.size(); while(limit<=n+m) limit<<=1,l++; a.resize(limit);b.resize(limit); for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1)); NTT(a,1);NTT(b,1); for(int i=0;i<limit;i++) a[i]=(a[i]*b[i])%mod; NTT(a,-1); ll inv=powmod(limit,mod-2); for(int i=0;i<=n+m;i++) a[i]=a[i]*inv%mod; a.resize(m+n-1); return a; } void solve(){ int _=read(); for(int i=1;i<=_;i++) k[i]=read(); vector<ll>ans = Ntt(1,_); for(auto to:ans){ printf("%lld ",to); } } ``` #### IV. ```c++ const int P = 1e9 + 7; struct FWT { void add(int &x, int y) {(x += y) >= P && (x -= P);} void sub(int &x, int y) {(x -= y) < 0 && (x += P);} int extend(int n) { int N = 1; for (; N < n; N <<= 1); return N; } void FWTor(std::vector<int> &a, bool rev) { int n = a.size(); for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) { for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) { if (!rev) add(a[i + j + m], a[i + j]); else sub(a[i + j + m], a[i + j]); } } } void FWTand(std::vector<int> &a, bool rev) { int n = a.size(); for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) { for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) { if (!rev) add(a[i + j], a[i + j + m]); else sub(a[i + j], a[i + j + m]); } } } void FWTxor(std::vector<int> &a, bool rev) { int n = a.size(), inv2 = (P + 1) >> 1; for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) { for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) { int x = a[i + j], y = a[i + j + m]; if (!rev) { a[i + j] = (x + y) % P; a[i + j + m] = (x - y + P) % P; } else { a[i + j] = 1LL * (x + y) * inv2 % P; a[i + j + m] = 1LL * (x - y + P) * inv2 % P; } } } } std::vector<int> Or(std::vector<int> a1, std::vector<int> a2) { int n = std::max(a1.size(), a2.size()), N = extend(n); a1.resize(N), FWTor(a1, false); a2.resize(N), FWTor(a2, false); std::vector<int> A(N); for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P; FWTor(A, true); return A; } std::vector<int> And(std::vector<int> a1, std::vector<int> a2) { int n = std::max(a1.size(), a2.size()), N = extend(n); a1.resize(N), FWTand(a1, false); a2.resize(N), FWTand(a2, false); std::vector<int> A(N); for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P; FWTand(A, true); return A; } std::vector<int> Xor(std::vector<int> a1, std::vector<int> a2) { int n = std::max(a1.size(), a2.size()), N = extend(n); a1.resize(N), FWTxor(a1, false); a2.resize(N), FWTxor(a2, false); std::vector<int> A(N); for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P; FWTxor(A, true); return A; } } fwt; ``` ```c++ #define inc(a, b) (((a) += (b)) >= P ? (a) -= P : 0) #define dec(a, b) (((a) -= (b)) < 0 ? (a) += P : 0) #define mul(a, b) (ll(a) * (b) % P) int fpow(ll a, int b = P - 2, ll x = 1) { for (; b; b >>= 1, a = a * a % P) if (b & 1) x = x * a % P; return x; } int inv[N], fac[N], ifac[N], W[N], _ = [] { fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1; for (ll i = 2; i < N; ++i) { fac[i] = fac[i - 1] * i % P; inv[i] = (P - P / i) * inv[P % i] % P; ifac[i] = (ll) ifac[i - 1] * inv[i] % P; } W[N / 2] = 1; for (int i = N / 2 + 1, wn = fpow(pG, P / N); i < N; ++i) W[i] = mul(W[i - 1], wn); for (int i = N / 2 - 1; ~i; --i) W[i] = W[i << 1]; return 0; }(); namespace NTT { void dft(int *a, int n) { for (int k = n >> 1; k; k >>= 1) for (int i = 0; i < n; i += k << 1) for (int j = 0; j < k; ++j) { int &x = a[i + j], y = a[i + j + k]; a[i + j + k] = mul(x - y + P, W[k + j]); inc(x, y); } } void idft(int *a, int n) { for (int k = 1; k < n; k <<= 1) for (int i = 0; i < n; i += k << 1) for (int j = 0; j < k; ++j) { int &x = a[i + j], y = mul(a[i + j + k], W[k + j]); a[i + j + k] = x < y ? x - y + P : x - y; inc(x, y); } for (int i = 0, in = P - (P - 1) / n; i < n; ++i) a[i] = mul(a[i], in); reverse(a + 1, a + n); } } // namespace NTT int norm(int n) { return 1 << (__lg(n - 1) + 1); } struct Poly : public vector<int> { #define T (*this) using vector<int>::vector; int deg() const { return size(); } Poly rev() const { return Poly(rbegin(), rend()); } void append(const Poly &a) { insert(end(), a.begin(), a.end()); } Poly operator-() const { Poly a(T); for (auto &x: a) x = x ? P - x : 0; return a; } Poly &operator+=(const Poly &a) { if (a.deg() > deg()) resize(a.deg()); for (int i = 0; i < a.deg(); ++i) inc(T[i], a[i]); return T; } Poly &operator-=(const Poly &a) { if (a.deg() > deg()) resize(a.deg()); for (int i = 0; i < a.deg(); ++i) dec(T[i], a[i]); return T; } Poly &operator^=(const Poly &a) { if (a.deg() < deg()) resize(a.deg()); for (int i = 0; i < deg(); ++i) T[i] = mul(T[i], a[i]); return T; } Poly &operator*=(int a) { for (auto &x: T) x = mul(x, a); return T; } Poly operator+(const Poly &a) const { return Poly(T) += a; } Poly operator-(const Poly &a) const { return Poly(T) -= a; } Poly operator^(const Poly &a) const { return Poly(T) ^= a; } Poly operator*(int a) const { return Poly(T) *= a; } Poly &operator<<=(int k) { return insert(begin(), k, 0), T; } Poly operator<<(int r) const { return Poly(T) <<= r; } Poly operator>>(int r) const { return r >= deg() ? Poly() : Poly(begin() + r, end()); } Poly &operator>>=(int r) { return T = T >> r; } Poly pre(int k) const { return k < deg() ? Poly(begin(), begin() + k) : T; } friend void dft(Poly &a) { NTT::dft(a.data(), a.size()); } friend void idft(Poly &a) { NTT::idft(a.data(), a.size()); } friend Poly conv(Poly a, Poly b, int n) { a.resize(n), dft(a); b.resize(n), dft(b); return idft(a ^= b), a; } Poly operator*(const Poly &a) const { int n = deg() + a.deg() - 1; return conv(T, a, norm(n)).pre(n); } // Description: f_i = sum T_{i + j} * a_j Poly mulT(const Poly &a) const { return T * a.rev() >> (a.deg() - 1); } /* * Description: Calculate f_1, ..., f_{n - 1} with a_i = sum_{j > 0} f_{i - j} g_j * and f_i = F(a_i, i),where g and f_0 is known, notice T_i = g_{i + 1}. * Time: O(n log^2 n) */ template<typename func> Poly semiConv(Poly f, int n, func calc) { f.resize(n); vector<Poly> va(n); // storage dft result, faster for (int m = 1; m < n; m++) { int k = m & -m, l = m - k, r = min(m + k, n); Poly &p = va[k], q(f.begin() + l, f.begin() + m); if (p.empty()) p = pre(r - l - 1), p.resize(k * 2), dft(p); q.resize(k << 1), dft(q), idft(q ^= p); // Poly q = conv(Poly(f.begin() + l, f.begin() + m), pre(r - l - 1), k << 1); for (int i = m; i < r; i++) inc(f[i], q[i - l - 1]); calc(f, m); } return f; } Poly inv2(int n) const { int i0 = fpow(T[0]); return (T >> 1).semiConv({i0}, n, [&](Poly &f, int m) { f[m] = mul(f[m], P - i0); }); } Poly exp2(int n) const { return deriv().semiConv({1}, n, [&](Poly &f, int m) { f[m] = mul(f[m], ::inv[m]); }); } Poly inv(int n) const { Poly x{fpow(T[0])}; for (int k = 1; k < n; k <<= 1) x.append(-((conv(pre(k << 1), x, k << 1) >> k) * x).pre(k)); return x.pre(n); } Poly deriv() const { if (empty()) return {}; Poly a(deg() - 1); for (ll i = 1; i < deg(); ++i) a[i - 1] = i * T[i] % P; return a; } Poly integ() const { if (empty()) return {}; Poly a(deg() + 1); for (int i = 1; i <= deg(); ++i) a[i] = mul(::inv[i], T[i - 1]); return a; } Poly log(int n) const { return (deriv() * inv(n)).integ().pre(n); } Poly exp(int n) const { Poly x{1}; for (int k = 1; k < n; k <<= 1) x.append((x * ((pre(k << 1) - x.log(k << 1)) >> k)).pre(k)); return x.pre(n); } Poly pow(int k, int n) const { return (log(n) * k).exp(n); } // T[0] = 1 Poly pow(int k, int kp, int n) const { // k = K % P, kp = K % phi(P) int i = 0; while (i < deg() && !T[i]) i++; if (1ll * i * k >= n) return Poly(n); int v = T[i], m = n - i * k; return ((((T >> i) * fpow(v)).log(m) * k).exp(m) << (i * k)) * fpow(v, kp); } Poly sqrt(int n) const { Poly x{1}, y{1}; // x[0] = sqrt(T[0]), default T[0] = 1 for (int k = 1; k < n; k <<= 1) { x.append((((pre(k << 1) - x * x) >> k) * y).pre(k) * ((P + 1) >> 1)); k << 1 < n ? y.append(-((conv(x.pre(k << 1), y, k << 1) >> k) * y).pre(k)) : void(); } return x.pre(n); } vector<Poly> operator/(const Poly &a) const { int k = deg() - a.deg() + 1; if (k < 0) return {{0}, T}; Poly q = (rev().pre(k) * (a.rev().inv(k))).pre(k).rev(), r = T - a * q; return {q, r.pre(a.deg() - 1)}; } /* * Description: calculate [x ^ k](f / g) * Time: O(n log n log k) */ int divAt(Poly f, Poly g, ll k) { int n = max(f.deg(), g.deg()), m = norm(n); for (; k; k >>= 1) { f.resize(m * 2), dft(f); g.resize(m * 2), dft(g); for (int i = 0; i < 2 * m; ++i) f[i] = mul(f[i], g[i ^ 1]); for (int i = 0; i < m; ++i) g[i] = mul(g[2 * i], g[2 * i + 1]); g.resize(m), idft(f), idft(g); for (int i = 0, j = k & 1; i < n; i++, j += 2) f[i] = f[j]; f.resize(n), g.resize(n); } return f[0]; } /* * Description: calculate T[k], where T[n] = sum c[i] * T[n - i] * Time: O(n log n log k) */ int recur(Poly c, ll k) { return c[0] = P - 1, divAt((T * c).pre(c.deg() - 1), c, k); } /* * Description: polynomial multipoint fast evaluation * Time: O(n log^2 n) */ Poly eval(Poly x) const { if (empty()) return Poly(x.deg()); const int m = x.deg(), n = norm(m); vector<Poly> q(2 * n, {1}); Poly ans(m), temp, d(2 * n); for (int i = n; i < n + m; ++i) q[i] = Poly{1, P - x[i - n]}; for (int i = n - 1; i; --i) q[i] = q[i << 1] * q[i << 1 | 1]; q[1] = mulT(q[1].inv(n)); for (int i = 1, l = 2, r = 3; i < n; ++i, l += 2, r += 2) { temp = q[l], d[l] = d[r] = d[i] + 1; q[l] = q[i].mulT(q[r]).pre(n >> d[l]); q[r] = q[i].mulT(temp).pre(n >> d[r]); } for (int i = n; i < n + m; ++i) ans[i - n] = q[i][0]; return ans; } #undef T }; // useless algorithm /* * Description: G(F(x)) * Time: O(n sqrt n log n + n ^ 2) */ Poly compound(Poly f, Poly g) { int n = f.size(), k = norm(2 * n), L = sqrt(n) + 1; vector<Poly> G(L + 1); Poly H, h(k), t; // H = g ^ (iL) auto dft = [&](Poly &a) { a.resize(k), NTT::dft(a.data(), k); }; auto idft = [&](Poly &a) { NTT::idft(a.data(), k), a.resize(n); }; G[0] = H = {1}, dft(g); for (int i = 1; i <= L; ++i) dft(G[i] = G[i - 1]), idft(G[i] ^= g); dft(g = G[L]); for (int i = 0; i < L; ++i, t = {}, idft(H)) { for (int j = 0; j < min(L, n - i * L); ++j) t += G[j] * f[i * L + j]; dft(t), dft(H); for (int j = 0; j < k; ++j) h[j] = (h[j] + (ll) t[j] * H[j]) % P, H[j] = mul(H[j], g[j]); } return idft(h), h; } /* * Description: get F(x) for F(G(x)) = x * Time: O(n sqrt n log n + n ^ 2) */ Poly compoundInv(Poly g) { // int n = g.size(), k = norm(2 * n), L = sqrt(n) + 1; vector<Poly> G(L + 1); Poly H, f(n); auto dft = [&](Poly &a) { a.resize(k), NTT::dft(a.data(), k); }; auto idft = [&](Poly &a) { NTT::idft(a.data(), k), a.resize(n); }; G[0] = H = {1}, H.resize(n), dft(g = (g >> 1).inv(n)); for (int i = 1; i <= L; ++i) dft(G[i] = G[i - 1]), idft(G[i] ^= g); dft(g = G[L]); for (int i = 0, t = 1; i < L; ++i) { for (int j = 1; j <= L && t < n; ++j, ++t) for (int r = 0; r < t; ++r) f[t] = (f[t] + (ll) G[j][r] * H[t - 1 - r]) % P; dft(H), idft(H ^= g); } return f ^ Poly(inv, inv + N); } ``` ### 7.扩展卢卡斯 ```c++ ll n, m, p;// C(n,m) mod p (p为任意数) ll exgcd(ll a, ll b, ll &x, ll &y){ if(!b){ x = 1, y = 0; return a; } ll res = exgcd(b, a%b, x, y); ll t = x; x = y; y = t-a/b*y; return res; } ll qpow(ll a, ll n, ll mod){ ll res = 1; while(n){ if(n&1) res = (res*a) % mod; a = (a*a) % mod; n >>= 1; } return res; } ll inv(ll a, ll p){ ll x, y; exgcd(a, p, x, y); if(x+p > p) return x; return x+p; } ll crt(ll n, ll mod){ return n*(p/mod)%p*inv(p/mod, mod)%p; } ll fac(ll n, ll p, ll k){ //k = p^x if(!n) return 1; ll ans = 1; for(int i = 2; i <= k; i++){ if(i%p) ans = ans*i % k; } ans = qpow(ans, n/k, k); for(int i = 2; i <= n%k; i++){ if(i%p) ans = ans*i % k; } return ans*fac(n/p, p, k)%k; } ll C(ll n, ll m, ll p, ll k){ //k = p^x if(n < m) return 0; ll a = fac(n,p,k), b = fac(m,p,k), c = fac(n-m,p,k); ll cnt = 0; for(ll i = p; i <= n; i *= p) cnt += n/i; for(ll i = p; i <= m; i *= p) cnt -= m/i; for(ll i = p; i <= n-m; i *= p) cnt -= (n-m)/i; return a*inv(b, k)%k * inv(c, k)%k * qpow(p, cnt, k)%k; } ll exlucas(){ ll t = p, ans = 0; for(ll i = 2; i*i <= t; i++){ if(t%i) continue; ll tmp = 1; while(t%i == 0){ tmp *= i; t /= i; } ans = (ans+crt(C(n, m, i, tmp), tmp))%p; } if(t > 1) ans = (ans+crt(C(n, m, t, t), t))%p; return ans%p; } ``` ### 8.莫比乌斯反演 #### I.求莫比乌斯函数前缀和与欧拉函数前缀和 ``` mu[x]=1 如果x=1 mu[x]=0 如果存在素数p使得 x%(p*p)=0 mu[x]=(-1)^k ,k为n的本质不同质因子个数 ``` ```c++ struct Math_Product_functions/*积性函数*/{ #define M 2000005 #define mod 1000000007 int pri[M],p[M],tot=0,cnt=0; bool v[M],f[M]; ll mu[M],Mu[M];// 莫比乌斯函数 ll phi[M],Phi[M],Phi_2[M];// 欧拉函数 map<ll,ll>MU;// 莫比乌斯函数(大数) map<ll,ll>PHI; map<ll,ll>PHI_2;// 欧拉函数phi[x^2]的和 /* mu[x]=1 if x=1 mu[x]=0 if x%(p*p)=0 mu[x]=(-1)^k ,k为n的本质不同质因子个数 */ int powmod(int a,int b){ int res=1; while(b){ if(b&1) res=1ll*res*a%mod; b>>=1; a=1ll*a*a%mod; } return res; } int G2=powmod(2,mod-2),G6=powmod(6,mod-2); void get_Mu_and_Phi(){ mu[1]=1,phi[1]=1;// 线性筛 for(int i=2;i<M;i++){ if(!f[i]) p[++tot]=i,mu[i]=-1,phi[i]=i-1; for(int j=1;j<=tot&&i*p[j]<M;j++){ f[i*p[j]]=1; if(i%p[j]==0){ mu[i*p[j]]=0;phi[i*p[j]]=phi[i]*p[j]; break; } mu[i*p[j]]=-mu[i];phi[i*p[j]]=phi[i]*(p[j]-1); } } // 求前缀和 for(int i=1;i<M;i++) Mu[i]=mu[i]+Mu[i-1];// 莫比乌斯函数前缀和 for(int i=1;i<M;i++) Phi[i]=phi[i]+Phi[i-1];// 欧拉函数前缀和 for(int i=1;i<M;i++) Phi_2[i]=(i*phi[i]%mod+Phi_2[i-1])%mod;// 欧拉函数[x^2]的前缀和 } ll sum_mu(ll x){// 莫比乌斯函数前缀和 if(x<M) return Mu[x]; if(MU.count(x)) return MU[x]; ll res=1; for(ll i=2,j;i<=x;i=j+1){ j=x/(x/i); res-=sum_mu(x/i)*(j-i+1); } return MU[x]=res; } ll sum_phi(ll x){ //欧拉函数前缀和 if(x<M) return Phi[x]; if(PHI.count(x)) return PHI[x]; ll res=1; for(ll i=1,j;i<=x;i=j+1){ j=x/(x/i); res+=(sum_mu(j)-sum_mu(i-1))*((x/i)*(x/i)); } return PHI[x]=((res+1)>>1); } ll sum_phi_2(ll x){//欧拉函数phi[x^2]前缀和 if(x<M) return Phi_2[x]; if(PHI_2.count(x)) return PHI_2[x]; ll res=(x+1)*x%mod*(2*x+1)%mod*G6%mod; for(ll i=2,j;i<=x;i=j+1){ j=x/(x/i); res=(res-(i+j)*(j-i+1)/2%mod*sum_phi_2(x/i)%mod); if(res<0) res+=mod; } return PHI_2[x]=res; } }Math; ``` ### 9.矩阵行列式 ```c++ struct Mat { double a[MAX][MAX]; #define EPS (1e-6) double Det() { double det = 1; for (int i = 0; i < n; ++i) { int k = i; for (int j = i + 1; j < n; ++j) if (fabs(a[j][i]) > fabs(a[k][i])) k = j; if (fabs(a[k][i]) < EPS) { det = 0; break; } swap(a[i], a[k]); if (i != k) det = -det; det *= a[i][i]; for (int j = i + 1; j < n; ++j) a[i][j] /= a[i][i]; for (int j = 0; j < n; ++j) if (j != i && fabs(a[j][i]) > EPS) for (int k = i + 1; k < n; ++k) a[j][k] -= a[i][k] * a[j][i]; } return det; } }; ``` ### 10.高斯消元 ```c++ struct Mat { double a[MAX][MAX]; #define EPS (1e-6) bool Gauss() { int r; double f; for (int i = 0; i < n; ++i) { r = i; for (int j = i + 1; j < n; ++j) if (fabs(a[j][i]) > fabs(a[r][i])) r = j; if (fabs(a[r][i]) < EPS) return false; if (r != i) for (int j = 0; j <= n; ++j) swap(a[r][j], a[i][j]); for (int k = i + 1; k < n; ++k) { f = a[k][i] / a[i][i]; for (int j = i; j <= n; ++j) a[k][j] -= f * a[i][j]; } } for (int i = n - 1; i >= 0; --i) { for (int j = i + 1; j < n; ++j) a[i][n] -= a[j][n] * a[i][j]; a[i][n] /= a[i][i]; } return true; } }; ``` ### 11.BM ```C++ namespace Linear_seq { typedef long long LL; LL mod; #define SZ(x) ((int)(x).size()) #define rep(i, a, n) for (int i = a; i < n; i++) #define pb push_back typedef vector<int> VI; typedef pair<int, int> PII; // const int N = 10010; LL res[N], base[N], _c[N], _md[N]; vector<int> Md; LL powmod(LL a, LL b) { LL res = 1; a %= mod; for (; b; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; } void mul(LL *a, LL *b, int k) { rep(i, 0, k + k) _c[i] = 0; rep(i, 0, k) if (a[i]) rep(j, 0, k) _c[i + j] = (_c[i + j] + a[i] * b[j]) % mod; for (int i = k + k - 1; i >= k; i--) if (_c[i]) rep(j, 0, SZ(Md)) _c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod; rep(i, 0, k) a[i] = _c[i]; } int solve(LL n, VI a, VI b) { LL ans = 0, pnt = 0; int k = SZ(a); rep(i, 0, k) _md[k - 1 - i] = -a[i]; _md[k] = 1; Md.clear(); rep(i, 0, k) if (_md[i] != 0) Md.push_back(i); rep(i, 0, k) res[i] = base[i] = 0; res[0] = 1; while ((1LL << pnt) <= n) pnt++; for (int p = pnt; p >= 0; p--) { mul(res, res, k); if ((n >> p) & 1) { for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i]; res[0] = 0; rep(j, 0, SZ(Md)) res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod; } } rep(i, 0, k) ans = (ans + res[i] * b[i]) % mod; if (ans < 0) ans += mod; return ans; } VI BM(VI s) { VI C(1, 1), B(1, 1); int L = 0, m = 1, b = 1; rep(n, 0, SZ(s)) { LL d = 0; rep(i, 0, L + 1) d = (d + (LL) C[i] * s[n - i]) % mod; if (d == 0) ++m; else if (2 * L <= n) { VI T = C; LL c = mod - d * powmod(b, mod - 2) % mod; while (SZ(C) < SZ(B) + m) C.pb(0); rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod; L = n + 1 - L; B = T; b = d; m = 1; } else { LL c = mod - d * powmod(b, mod - 2) % mod; while (SZ(C) < SZ(B) + m) C.pb(0); rep(i, 0, SZ(B)) C[i + m] = (C[i + m] + c * B[i]) % mod; ++m; } } return C; } int gao(VI a, LL n) { VI c = BM(a); c.erase(c.begin()); rep(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod; return solve(n, c, VI(a.begin(), a.begin() + SZ(c))); } }; //using namespace Linear_seq; ``` ## 八、图论 ### 1.读入图 #### Ⅰ.邻接矩阵 二维数组 #### Ⅱ.vector #### Ⅲ.邻接表 #### Ⅳ.伪邻接表（链式前向星） ### 2.最短路算法： #### Ⅰ.dijkstra算法 ```c++ struct dijkstra { vector<vector<pair<int, int>>> G; vector<int> dis, vis; int n; #define INF 2000000000 struct ty { int x, dis; bool operator<(const ty &A) const { return dis > A.dis; } }; dijkstra(int N, int M) : G(N + 1), dis(N + 1), vis(N + 1) { n = N; for (int i = 1, u, v, w; i <= M; i++) { cin >> u >> v >> w; G[u].emplace_back(v, w); G[v].emplace_back(u, w); } } inline void dij(int s) { for (int i = 1; i <= n; i++) { vis[i] = 0; dis[i] = INF; } dis[s] = 0; priority_queue<ty> q; q.push({s, 0}); while (!q.empty()) { auto [x, d] = q.top(); q.pop(); if (vis[x]) continue; vis[x] = 1; for (auto [to, w]: G[x]) { if (vis[to]) continue; if (dis[to] > d + w) { dis[to] = d + w; q.push({to, dis[to]}); } } } } }; ``` #### Ⅱ.**b**ellman-ford算法 （权值允许是负数，但不能出现负环，且一次只求一对距离） ```c++ ``` #### Ⅲ.SPFA算法 （权值允许是负数，但不能出现负环，且一次只求一对距离） ```c++ int n,m,s,t,cnt=0; struct ty { int to,len,next; }edge[N]; int head[N]; void add(int x,int y,int z) { edge[++cnt].to=y; edge[cnt].len=z; edge[cnt].next=head[x]; head[x]=cnt; } queue<int>q; int dis[N]; bool vis[N]; int spfa(int s,int t) { memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for (int i=head[x];i!=-1;i=edge[i].next) { int y=edge[i].to; if(dis[y]>dis[x]+edge[i].len) { dis[y]=dis[x]+edge[i].len; if(!vis[y]) { q.push(y);vis[y]=1; } } } } if(dis[t]>=inf) return -1; return dis[t]; } int main() { n=read(),m=read(),s=read(),t=read();//n为总点数，m为边数，s为起点，t为终点 memset(head,-1,sizeof head); for (int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); add(x,y,z);add(y,x,z); } printf("%d",spfa(s,t)); return 0; } ``` #### Ⅳ.floyd算法 （可以求多源点路最短路） ```c++ int f[N][N],n,m; void floyd() { for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { if((i!=j)&&(j!=k)&&(k!=i)) { if(f[i][k]+f[k][j]<=f[i][j]) f[i][j]=f[i][k]+f[k][j]; } } } int main() { memset(f,0x3f,sizeof f); n=read(),m=read();//n为点数，m为边数 for (int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); f[x][y]=f[y][x]=z; } void floyd(); return 0; } ``` ### 3.最小生成树 #### Ⅰ.prim算法 （对于每一个点，都取一条边让它进去最小生成树，贪心一下就是取与这个点相连的最小边） ```c++ struct ty { int to,len,next; }edge[N]; int head[N],dis[N]; int cnt=0,n,m,cntt=0; void add(int a,int b,int v){ edge[++cnt].to=b; edge[cnt].len=v; edge[cnt].next=head[a]; head[a]=cnt; } bool vis[N]; struct ty2{ int x,len; bool operator < (const ty2 &a) const { return len >a.len; } }; priority_queue< ty2 > q; void prim(){ memset(dis,0x7f,sizeof dis); vis[1]=1;cntt++; ty2 tmp; for (int i=head[1];i!=-1;i=edge[i].next){ tmp.x=edge[i].to; tmp.len=edge[i].len; dis[tmp.x]=tmp.len; q.push(tmp); } int ans=0; while(!q.empty()){ ty2 tmp=q.top(); q.pop(); int x=tmp.x; if (vis[x]) continue; vis[x]=1;cntt++; ans+=tmp.len; if(cntt>=n) break; for (int i=head[x];i!=-1;i=edge[i].next){ if(vis[edge[i].to]) continue; if(dis[edge[i].to]>edge[i].len){ tmp.x = edge[i].to; tmp.len = edge[i].len; dis[edge[i].to] = edge[i].len; q.push(tmp); } } } printf("%d",ans); } int main(){ n=read(),m=read(); memset(head,-1,sizeof(head)); for (int i=1;i<=m;i++){ int a=read(),b=read(),v=read(); add(a,b,v);add(b,a,v); } prim(); return 0; } ``` #### Ⅱ.Kruskal算法 ```c++ struct ty{ int x,y,z; }edge[N]; int fa[N]; inline bool cmp(ty a,ty b){ return a.z<b.z; } inline int find(int x){ return fa[x] == x ? x : fa[x]=find(fa[x]); } int main(){ int n=read(),m=read(); for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=m;i++) edge[i].x=read(),edge[i].y=read(),edge[i].z=read(); sort(edge+1,edge+m+1,cmp); int ans = 0; for (int i=1;i<=m;i++){ int fx = find(edge[i].x); int fy = find(edge[i].y); if(fx==fy) continue; ans += edge[i].z; fa[fx]=fy; } printf("%d",ans); return 0; } ``` #### III.Kruskal重构树 ```c++ struct ty{ int x,y,z; }edge[N]; int fa[N]; inline bool cmp(ty a,ty b){ return a.z<b.z; } inline int find(int x){ return fa[x] == x ? x : fa[x]=find(fa[x]); } // kruskal重构树 // 重构树点权就是当前边的边权 // 可以用数剖维护 重构树，以快速求lca vector<int>v[N]; int val[N],f[N];// val就是点权 int cnt=0; void rebuild(int i,int fx,int fy){ val[++cnt]=edge[i].z; f[fx]=f[fy]=f[cnt]=cnt; v[cnt].push_back(fx); v[cnt].push_back(fy); v[fx].push_back(cnt); v[fy].push_back(cnt); } int main(){ int n=read(),m=read(); cnt=n; for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=m;i++) edge[i].x=read(),edge[i].y=read(),edge[i].z=read(); sort(edge+1,edge+m+1,cmp); int ans = 0; for (int i=1;i<=m;i++){ int fx = find(edge[i].x); int fy = find(edge[i].y); if(fx==fy) continue; rebuild(i,fx,fy); ans += edge[i].z; fa[fx]=fy; } printf("%d",ans); return 0; } ``` #### IV.Boruvka 算法 ```c++ ``` ### 4.LCA #### I.树上倍增 ```c++ int f[N][30],lg[N];//f[i][j]表示点i向上2^j层的祖先是哪个点 //f[i][0]=fa[i] //f[i][j]=f[f[i][j-1][j-1] int dep[N];//表示每一个点的深度 vector<int>G[N]; inline void dfs(int x,int fa){ dep[x]=dep[fa]+1; f[x][0]=fa; for(int i=1;(1<<i)<=dep[x];i++){ f[x][i]=f[f[x][i-1]][i-1]; } for (int i=0;i<G[x].size();i++){ int v=G[x][i]; if(v==fa) continue; dfs(v,x); } } inline int LCA(int a,int b){ if(dep[a]<dep[b]) swap(a,b); while(dep[a]!=dep[b]) a=f[a][lg[dep[a]-dep[b]]-1]; if(a==b) return a; for(int k=lg[dep[a]];k>=0;k--){ if(f[a][k]!=f[b][k]) a=f[a][k],b=f[b][k]; } return f[a][0]; } int n,m,s;//n为点数 m为询问数 s为根节点 inline void Init(){ for(int i=1;i<=n;i++){ lg[i]=lg[i-1]; if(i==(1<<lg[i-1])) lg[i]++; } } ``` #### II RMQ+ST表 （DFS序+RMQ+ST表） ```c++ vector<int>G[N]; int f[N],fir[N]; int dp[N][40]; int num=0,cnt=0; int b[N<<1]; inline void dfs(int x,int fa){ int tmp=++num; b[++cnt]=tmp; f[tmp]=x; fir[x]=cnt; for (int i=0;i<G[x].size();i++){ int v=G[x][i];if(v==fa) continue; dfs(v,x); b[++cnt]=tmp; } } inline void rmq_st(int x){ for (int i=1;i<=x;i++) dp[i][0]=b[i]; for (int j=1;j<=30;j++){ int t=x-(1<<j)+1; for (int i=1;i<=t;i++){ dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]); } } } inline int rmq_find(int l,int r){ int k=log2(r-l+1); return min(dp[l][k],dp[r-(1<<k)+1][k]); } inline int LCA(int a,int b){ if(fir[a]>fir[b]) swap(a,b); int k=rmq_find(fir[a],fir[b]); return f[k]; } ``` #### Ⅲ.树链剖分 ```c++ // 第一遍dfs维护每个点的重儿子,父亲，深度 // 第二遍dfs对每个点重新编号 并且记录 // 记录每个点所在重链的最上面一个点是哪一个 top[x] int fa[N],siz[N],dep[N],top[N],son[N]; int n,m,s;//n为点数 m为询问次数 s为根节点 vector<int>G[N]; inline void dfs1(int x){ dep[x]=dep[fa[x]]+1; siz[x]=1; for(int i=0;i<G[x].size();i++){ int v=G[x][i]; if(v==fa[x]) continue; fa[v]=x;dfs1(v); siz[x]+=siz[v]; if(!son[x]||siz[son[x]]<siz[v]) son[x]=v; } } inline void dfs2(int x,int topf){ top[x]=topf; if(son[x]) dfs2(son[x],topf); for (int i=0;i<G[x].size();i++){ int v=G[x][i]; if(v==fa[x]||v==son[x]) continue; dfs2(v,v); } } inline int LCA(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]>=dep[top[y]]){ x=fa[top[x]]; }else{ y=fa[top[y]]; } } if(dep[x]<dep[y]) return x; return y; } ``` #### Ⅳ.trajan ```c++ int n,m,s,dep[N],fa[N]; bool vis[N]; struct query{ int id,x,y,lca; }q[N]; struct ty{ int id,num; }; int a[N]; vector<int>G[N]; vector<ty>qes[N]; inline int find(int i){ return i==fa[i]?i:fa[i]=find(fa[i]); } inline void merge(int u,int v){ int a=find(u),b=find(v); if(dep[a]>dep[b]) fa[a]=b; else fa[b]=a; } inline void tarjan(int x){ fa[x]=x; vis[x]=true; for(int i=0;i<G[x].size();i++){ int p=G[x][i]; if(!vis[p]){ dep[p]=dep[x]+1; tarjan(p); merge(p,x); } } for(int i=0;i<qes[x].size();i++){ if(vis[qes[x][i].num]){ q[qes[x][i].id].lca=find(qes[x][i].num); } } } int main(){ scanf("%d%d%d",&n,&m,&s);//n为点数，m为询问的所有可能，s为起点 for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x); for (int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); q[i].x=u,q[i].y=v; q[i].id=i; qes[q[i].x].push_back((ty){i,q[i].y}); qes[q[i].y].push_back((ty){i,q[i].x}); } tarjan(s); for (int i=1;i<=m;i++){ printf("%d\n",q[i].lca); } } ``` ### 5.网络流 #### I.最大流 ##### 1.Dinic 算法 ```c++ #include <bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int N = 5e5 + 10; int n,m,s,t,u,v; int w,ans,dis[N]; int cnt=1,now[N],head[N]; struct node { int to,nxt; int val; }egde[N]; void add(int u,int v,int w) { egde[++cnt].to=v; egde[cnt].val=w; egde[cnt].nxt=head[u]; head[u]=cnt; } int bfs(){ //在惨量网络中构造分层图 for(int i=1;i<=n;i++) dis[i]=inf; queue<int> q; q.push(s); dis[s]=0; now[s]=head[s]; while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=egde[i].nxt){ int v=egde[i].to; if(egde[i].val>0 && dis[v]==inf) { q.push(v); now[v]=head[v]; dis[v]=dis[x]+1; if(v==t) return 1; } } } return 0; } int dfs(int x,int sum) { //sum是整条增广路对最大流的贡献 if(x==t) return sum; int k,res=0; //k是当前最小的剩余容量 for(int i=now[x];i && sum;i=egde[i].nxt) { now[x]=i; //当前弧优化 int v=egde[i].to; if(egde[i].val>0 && (dis[v]==dis[x]+1)) { k=dfs(v,min(sum,egde[i].val)); if(k==0) dis[v]=inf; //剪枝，去掉增广完毕的点 egde[i].val-=k; egde[i^1].val+=k; res+=k; //res表示经过该点的所有流量和（相当于流出的总量） sum-=k; //sum表示经过该点的剩余流量 } } return res; } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,0); } while(bfs()) ans+=dfs(s,inf); //流量守恒（流入=流出） printf("%d",ans); return 0; } ``` ### 6.强连通分量 #### I.tarjan ```c++ const int N = 1e6 + 10; vector<int>G[N]; int dfn[N],low[N],dfncnt,s[N],in_stack[N],tp; int scc[N],sc;// 结点 i 所在 SCC 的编号 int sz[N];bool flag=0; void tarjan(int x){ low[x] = dfn[x] = ++ dfncnt;s[++tp]=x;in_stack[x]=1; for(auto to:G[x]){ if(!dfn[to]){ tarjan(to); low[x]=min(low[to],low[x]); }else if(in_stack[x]){ low[x]=min(low[x],dfn[to]); } } if(dfn[x]==low[x]){ sc++; while(s[tp]!=x){ scc[s[tp]] = sc;sz[sc]++; in_stack[s[tp--]]=0; } scc[s[tp]]=sc;sz[sc]++; in_stack[s[tp--]]=0; } } ``` #### II.Kosaraju 算法 ```c++ ``` ### 7.斯坦纳树 ```c++ #define mp make_pair typedef pair<int, int> P; typedef pair<P, int> PP; const int INF = 0x3f3f3f3f; const int dx[] = {0, 0, -1, 1}; const int dy[] = {1, -1, 0, 0}; int n, m, K, root; int f[101][1111], a[101], ans[11][11]; bool inq[101]; PP pre[101][1111]; queue<P> q; bool legal(P u) { if (u.first >= 0 && u.second >= 0 && u.first < n && u.second < m) { return true; } return false; } int num(P u) { return u.first * m + u.second; } void spfa(int s) { memset(inq, 0, sizeof(inq)); while (!q.empty()) { P u = q.front(); q.pop(); inq[num(u)] = 0; for (int d = 0; d < 4; d++) { P v = mp(u.first + dx[d], u.second + dy[d]); int du = num(u), dv = num(v); if (legal(v) && f[dv][s] > f[du][s] + a[dv]) { f[dv][s] = f[du][s] + a[dv]; if (!inq[dv]) { inq[dv] = 1; q.push(v); } pre[dv][s] = mp(u, s); } } } } void dfs(P u, int s) { if (!pre[num(u)][s].second) return; ans[u.first][u.second] = 1; int nu = num(u); if (pre[nu][s].first == u) dfs(u, s ^ pre[nu][s].second); // 通过 dfs 来找到答案 dfs(pre[nu][s].first, pre[nu][s].second); } int main() { memset(f, INF, sizeof(f)); scanf("%d %d", &n, &m); int tot = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &a[tot]); if (!a[tot]) { f[tot][1 << (K++)] = 0; root = tot; } tot++; } } for (int s = 1; s < (1 << K); s++) { for (int i = 0; i < n * m; i++) { for (int subs = s & (s - 1); subs; subs = s & (subs - 1)) { if (f[i][s] > f[i][subs] + f[i][s ^ subs] - a[i]) { f[i][s] = f[i][subs] + f[i][s ^ subs] - a[i]; // 状态转移 pre[i][s] = mp(mp(i / m, i % m), subs); } } if (f[i][s] < INF) q.push(mp(i / m, i % m)); } spfa(s); } printf("%d\n", f[root][(1 << K) - 1]); dfs(mp(root / m, root % m), (1 << K) - 1); for (int i = 0, tot = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!a[tot++]) putchar('x'); else putchar(ans[i][j] ? 'o' : '_'); } if (i != n - 1) printf("\n"); } return 0; } ``` ### 8.二分图匹配，匈牙利算法 ```c++ bool f[N][N], used[N];//f 表示图，used 表示右边的某个数是否用过 int match[N];// match 表示右边的数连接到左边哪一个 int n, m, e; bool dfs(int p) { for (int i = 1; i <= m; i++) { if (f[p][i] && !used[i]) { used[i] = 1; if (!match[i] || dfs(match[i])) { match[i] = p; return 1; } } } return 0; } int Hungarian_Algorithm() { int Ans = 0; for (int i = 1; i <= n; i++) { memset(used, 0, sizeof used); Ans += dfs(i); } return Ans; } ``` ### 9.树分治 ```c++ vector<int> G[N]; int A[N]; int siz[N], dep[N], Max[N], vis[N], bel[N]; int root, ans, m, allsize; void Get_Root(int x, int fa) { siz[x] = 1; Max[x] = 0; for (int to: G[x]) { if (to == fa || vis[to]) continue; Get_Root(to, x); siz[x] += siz[to]; Max[x] = max(Max[x], siz[to]); } Max[x] = max(Max[x], allsize - siz[x]); if (Max[x] < Max[root]) root = x; } int seq[N]; void dfs(int x, int fa, int dis) { seq[++m] = x; dep[x] = dis; bel[x] = bel[fa]; for (int to: G[x]) { if (to == fa || vis[to]) continue; dfs(to, x, dis + 1); } } bool cmp(int i, int j) { return A[i] < A[j]; } void calc(int x) { // 处理 } void Solve(int x) { vis[x] = 1; seq[m = 1] = bel[x] = x; dep[x] = 0; for (int to: G[x]) { if (vis[to]) continue; bel[to] = to; dfs(to, to, 1); } calc(x); for (int to: G[x]) { if (vis[to]) continue; allsize = siz[to]; root = 0; Get_Root(to, x); Solve(root); } } void solve() { int n = read(); for (int i = 1; i < n; i++) { int u = read(), v = read(); G[u].push_back(v); G[v].push_back(u); } for (int i = 1; i <= n; i++) A[i] = read(); allsize = n; Max[0] = n + 1; Get_Root(1, 0); Solve(root); } ``` ## 九、线性基 ### 1.线性基含义 线性基是向量空间的一组基，通常可以解决有关异或( ^ )的一些题目。 通俗一点的讲法就是由一个集合构造出来的另一个集合，它有以下几个性质： - 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。 - 线性基是满足性质 1 的最小的集合。 - 线性基没有异或和为 0 的子集。 - 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。 - 线性基中每个元素的二进制最高位互不相同。 ### 2.构造线性基 ```c++ void build(ll x) { for(int i = 62; i >= 0; i--) { if(!(x >> (ll)i)) continue; if(!p[i]) { p[i] = x; break; } x ^= p[i]; } } ``` ### 3.查询一个元素是否可以被异或出来 从高到低，如果这一位为1就异或上这一位的线性基，把11消去，根据性质一，如果最后得到了0，那这个数就可以表示出来。 ```c++ bool ask(ll x) { for(int i=62;i>=0;i--) if(x&(1LL<<i)) x^=p[i]; return x==0; } ``` ### 4.查询异或最大值 按位贪心 ```c++ ll ask_max() { ll ans=0; for(int i=62;i>=0;i--) if((ans^p[i])>ans) ans^=p[i]; return ans; } ``` ### 5.查询异或最小值 其实异或的最小值一般来说就是线性基里的最小元素，因为插入这个元素的时候我们总是尽量让它的高位为0才来插入这一位。但是为什么是“一般”呢？因为有可能会有出现0，得要在插入的时候记下个标记来特判才行。 ```c++ ll ask_min() { ll ans=0; for(int i=0;i<=62;i++) if(p[i]) return p[i]; } ``` ### 6.查询异或第k小 首先考虑，要是每一位的选择都不会影响下一位的话，那就可以直接从高到低按位去选择就行了，就类似于二叉树求rank的玩法。 重构一个数组 d[i] 来解决问题 ```c++ void rebuild() { cnt=0;top=0; for(int i=MB;i>=0;i--) for(int j=i-1;j>=0;j--) if(p[i]&(1LL<<j)) p[i]^=p[j]; for(int i=0;i<=MB;i++) if(p[i]) d[cnt++]=p[i]; } ``` 查询第k小的值 ```c++ ll aks_kth(int k) { if(k>=(1ll<<cnt)) return -1; ll ans=0; for (int i=MB;i>=0;i--) if(k&(1ll<<i)) ans^=d[i]; return ans; } ``` ### 7.查询排名 ```c++ int rank(ll x) { int ans=0; for (int i=cnt-1;i>=0;i--) { if(x>=d[i]) { ans+=(1<<i); x^=d[i]; } } return ans; } ``` ## 十、字符串 ```c++ S= " 字符串 " Border：表示 前缀字符串 和 后缀字符串 相同 Preffix[i] 前缀 周期： 表示 字符串以 T 为周期 若 T1 T2 均为 S 的周期 ，则 gcd(p,q)也是 S 的周期 循环节 p | |S| Think: 则 |S| - T = Border (S) S Border 的 Border 也是 S 的 Border -->求 S的所有 Border 等价于求所有前缀的最大前缀 nxt[i] 表示的是 Preffix[i] 的非平凡的最大 Border for(int i=2;i<=len;i++){ nxt[i]=nxt[i-1]; while(nxt[i]&&s[i]!=s[nxt[i]+1]) nxt[i]=nxt[nxt[i]]; nxt[i] += (s[i]==s[nxt[i]+1]); } Border 树: 0是这棵有向树的根，对于其他每个点 1 <= i <= n , 父节点为nxt[i] 性质： 1.每一个前缀 Prefix[i] 的所有 Border ：节点i到根的链 2.哪些前缀有长度为x的 Border ： x的子树 3.求两个前缀的公共 Border 等价于求 LCA ``` ### 1.KMP —— NEW #### I.next数组 nxt[i] 表示的是 Preffix[i] 的非平凡的最大 Border ```c++ for(int i=2;i<=len;i++){ nxt[i]=nxt[i-1]; while(nxt[i]&&s[i]!=s[nxt[i]+1]) nxt[i]=nxt[nxt[i]]; nxt[i] += (s[i]==s[nxt[i]+1]); } ``` #### II.计算 S2 串在 S1 串 出现的位置和次数 ```c++ // cnt 表示个数 for(int i=1,j=0;i<=len1;i++){ while( j && s1[i]!=s2[j+1]) j=nxt[j]; j+=(s1[i]==s2[j+1]); if(j==len2){ ans[++cnt]=i-j+1; j=nxt[j]; } } ``` ### 3.Manacher ```c++ const int MAX = 2e5+10000; char s[MAX],ch[MAX]; int lc[MAX];// 每个点的回文半径 int N; void init(char *s){ int n = strlen(s+1); ch[n*2 +1] = '#'; ch[0] = '@'; ch[n*2 +2] = '\0'; for (int i=n;i>=1;i--){ ch[i*2] = s[i];ch[i*2 -1] = '#'; } N = 2*n + 1; } void manacher(){ lc[1]=1; int k=1; for (int i=2;i<=N;i++){ int p = k+lc[k]-1; if (i<=p){ lc[i]=min(lc[2*k-i],p-i+1); }else{ lc[i]=1; } while (ch[i+lc[i]]==ch[i-lc[i]])lc[i]++; if (i+lc[i]>k+lc[k])k=i; } } ``` ### 4.SA 后缀数组 关于清空，需要清空两倍数组。 LCP 最长公共前缀 #### I.倍增 ```c++ // 后缀排序：将所有的后缀s[i]看作独立的串，放在一起按照字典序进行升序排序 // 后缀排名：rk[i]: 表示后缀s[i]在后缀排序中的排名，即他第几小的后缀 // 后缀数组: sa[i]: 表示排名第i小的后缀 // rk[sa[i]]=i // Height[i]: 为后缀i与排名在他前面一个后缀 LCP，即：Height[i]=LCP(s[i,n],s[sa[rk[i]-1],n]) // H[i]=Height[sa[i]]:表示排名为i与i-1的串的LCP const int N = 1e6 + 10; char s[N]; struct Suffix_Array{ int h[N],rk[N],sa[N],y[N],c[N],Log[N]; int m=122,n,len; Suffix_Array(){ Log[0] = -1; for (int i = 1; i <= 100000; i++) Log[i] = Log[i >> 1] + 1; } void Get_Suffix_Array(){ for(int i=0;i<=m;i++) c[i]=0; for(int i=1;i<=n;i++) c[rk[i] = s[i]]++; for(int i=1;i<=m;i++) c[i]+=c[i-1]; for(int i=n;i>=1;i--) sa[c[rk[i]]--]=i; for(int k=1;k<=n;k<<=1){ int p=0; for(int i=n-k+1;i<=n;i++) y[++p]=i; for(int i=1;i<=n;i++){ if(sa[i]>k){ y[++p]=sa[i]-k; } } for(int i=0;i<=m;i++) c[i]=0; for(int i=1;i<=n;i++) c[rk[i]]++; for(int i=1;i<=m;i++) c[i]+=c[i-1]; for(int i=n;i>=1;i--) sa[c[rk[y[i]]]--]=y[i]; for(int i=0;i<=n;i++) swap(rk[i],y[i]); rk[sa[1]]=p=1; for(int i=2;i<=n;i++){ rk[sa[i]]=(y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] ? p : ++p); } if(p>=n) break; m=p; } } void Get_H(){ for(int i=1,k=0;i<=n;i++){ if(k)k--; int j=sa[rk[i]-1]; while(s[i+k] == s[j+k] )k++; h[rk[i]] = k; } } int st[N][25]; void init(){ for(int i=1;i<=n;i++){ st[i][0]=h[i]; } for(int j=1;j<=20;j++){ for(int i=1;i+(1<<j)-1<=n;i++){ st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]); } } } int query(int l, int r) { //l = rk[l], r = rk[r];(查第l个后缀 和 第r个后缀 的LCP) if (l > r) swap(l, r);l++; int len = Log[r - l + 1]; return min(st[l][len], st[r - (1 << len) + 1][len]); } void Read(){ /* write your code here */ } void work(){ /* write your code here */ } }; ``` ### 5.Trie树 ```c++ #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; struct Trie { int nxt[N][30], cnt; bool tag[N]; // 该结点结尾的字符串是否存在 void insert(char *s) { // 插入字符串 int p = 0; for (int i = 0; s[i] ; i++) { int c = s[i] - 'a'; if (!nxt[p][c]) nxt[p][c] = ++cnt; // 如果没有，就添加结点 p = nxt[p][c]; } tag[p] = 1; } bool find(char *s) { // 查找字符串 int p = 0; for (int i = 0; s[i] ; i++) { int c = s[i] - 'a'; if (!nxt[p][c]) return 0; p = nxt[p][c]; } return tag[p]; } }; Trie tr; int main(){ return 0; } ``` ### 6.ACAM ```c++ const int N = 1e6 + 10; struct ACAM { int tr[N][26],tag[N],fail[N],tot; queue<int> q; void build() { for (int i = 0; i < 26; i++) if (tr[0][i]) q.push(tr[0][i]); while (q.size()) { int u = q.front(); q.pop(); for (int i = 0; i < 26; i++) { if (tr[u][i]) fail[tr[u][i]] = tr[fail[u]][i], q.push(tr[u][i]); else tr[u][i] = tr[fail[u]][i]; } } } void insert(char *s) { int u = 0; for (int i = 1; s[i]; i++) { if (!tr[u][s[i] - 'a']) tr[u][s[i] - 'a'] = ++tot; // 如果没有则插入新节点 u = tr[u][s[i] - 'a']; // 搜索下一个节点 } tag[u]++; // 尾为节点 u 的串的个数 } int query(char *t) { int u = 0, res = 0; for (int i = 1; t[i]; i++) { u = tr[u][t[i] - 'a']; // 转移 for (int j = u; j && tag[j] != -1; j = fail[j]) { res += tag[j], tag[j] = -1; } } return res; } }; ACAM Tr; ``` ### 7.SAM 后缀自动机 ```c++ const int N = 1e6 + 10; char s[N];int n,m; struct Suffix_Auto_Maton{ // ch[i][j] 表示后缀链接 ------ 即第i个字符为j的编号为多少 // l[i]表示最大长度 fa[i]表示当前节点的后缀的节点 int last,cnt,n;int ch[N<<1][26],fa[N<<1],l[N<<1]; void init(){last=cnt=1;memset(ch[1],0,sizeof ch[1]);} int Tr(char c){return c-'a';} int val(int c){return l[c]-l[fa[c]];}// 匹配长度与失配位置的匹配长度之差就是他们之间的子串数量 void insert(int c){ int p = last ,np = ++cnt; last = np ; l[np] = l[p] + 1; memset(ch[cnt],0,sizeof ch[cnt]); for( ; p && !ch[p][c] ; p = fa[p] ) ch[p][c] = np; if(!p) fa[np] = 1; else{ int q = ch[p][c]; if(l[p] + 1 == l[q]) fa[np] = q; else{ int nq = ++cnt ; l[nq] = l[p] + 1; memcpy(ch[nq] , ch[q] , sizeof ch[q]); fa[nq] = fa[q] ;fa[q] = fa[np] = nq; for( ; ch[p][c] == q ; p = fa[p]) ch[p][c] = nq; } } siz[np] = 1; } int siz[N<<1],k[N<<1],c[N<<1]; // c[i] 用于桶排序 // k[i] 表示节点编号为 i 的排名 // siz[i] 表示i状态的串的个数有多少个 当前节点的所有字符串出现的次数 void calc(){ // 基数排序 for(int i=1;i<=cnt;i++) c[l[i]]++; for(int i=1;i<=cnt;i++) c[i]+=c[i-1]; for(int i=1;i<=cnt;i++) k[c[l[i]]--]=i; for(int i=cnt;i>=1;i--){ int id=k[i]; siz[fa[id]]+=siz[id]; } } void build(){ init(); scanf("%d",&n); scanf("%s",s+1); for(int i=1;i<=n;i++) insert(Tr(s[i]));// 是 数字 or 字母 ？ calc(); } void work(){ /* write your code here */ } void de_BUG(){ for(int i=1;i<=cnt;i++){ for(int j=0;j<3;j++){ printf("ch[%d][%d]=%d ",i,j,ch[i][j]); } puts(""); } for(int i=1;i<=cnt;i++) printf("fa[%d]=%d ",i,fa[i]); puts(""); for(int i=1;i<=cnt;i++) printf("L[%d]=%d ",i,l[i]); puts(""); for(int i=1;i<=cnt;i++) printf("siz[%d]=%d ",i,siz[i]); puts(""); } }Sam; /* 5 abcbc ch[1][0]=2 ch[1][1]=6 ch[1][2]=8 ch[2][0]=0 ch[2][1]=3 ch[2][2]=0 ch[3][0]=0 ch[3][1]=0 ch[3][2]=4 ch[4][0]=0 ch[4][1]=5 ch[4][2]=0 ch[5][0]=0 ch[5][1]=0 ch[5][2]=7 ch[6][0]=0 ch[6][1]=0 ch[6][2]=8 ch[7][0]=0 ch[7][1]=0 ch[7][2]=0 ch[8][0]=0 ch[8][1]=5 ch[8][2]=0 fa[1]=0 fa[2]=1 fa[3]=6 fa[4]=8 fa[5]=6 fa[6]=1 fa[7]=8 fa[8]=1 L[1]=0 L[2]=1 L[3]=2 L[4]=3 L[5]=4 L[6]=1 L[7]=5 L[8]=2 siz[1]=5 siz[2]=1 siz[3]=1 siz[4]=1 siz[5]=1 siz[6]=2 siz[7]=1 siz[8]=2 */ ``` ## 十一、计算几何 ### 1.二维几何通用板子 ```c++ struct Point{ #define INF 1e18 #define eps 1e-11 #define PI 3.14159265358979323846 #define Equal(t1,t2) (fabs((t1)-(t2))<eps) #define Min(x,y) (((x)-(y)<=eps)?(y):(x)) double x , y; Point(double X = 0, double Y = 0) : x(X), y(Y) {} inline int SGN(double t) {return Equal(t,0)?0:(t>eps)?1:-1;} // 符号 bool operator == (const Point&a) const{ return Equal(x,a.x)&&Equal(y,a.y);}// 判断是否相等 bool operator < (const Point&a) const{ return x==a.x?y<a.y:x<a.x;}//凸包sort Point operator + (const Point&a) const{ return {x+a.x,y+a.y};} // 加法 Point operator - (const Point&a) const{ return {x-a.x,y-a.y};} // 减法 double operator* (const Point&a) const{ return x*a.y-y*a.x ;} // 叉积 double operator^ (const Point&a) const{ return x*a.x+y*a.y ;} // 点积 Point operator * (double val ) const{ return {x*val,y*val};} // 数乘 Point operator / (double val ) const{ return {x/val,y/val};} // 除法 double dot(Point&a) { return x*a.x + y*a.y; } // 点积 double r2() { return x*x + y*y; } // 长度的平方 double r () { return sqrt(r2());} // 长度 double dis2(Point&a){ return (*this-a).r2(); } // 两点距离的平方 double dis (Point&a){ return (*this-a).r (); } // 两点距离 int direction(Point&a,Point&b) { return SGN(x*(a.y-b.y)+a.x*(b.y-y)+b.x*(y-a.y));} bool onLine(Point&a,Point&b) { return direction(a,b) == 0;} // 判断点是否在直线上 bool inRect(Point&a,Point&b) { return SGN((*this-a)^(*this-b))<=0;} bool onLineSeg(Point&a,Point&b){ return onLine(a,b) && inRect(a,b) ;}// 判断点是否在线段上，P1 P2要求是端点 double disLine(Point&a,Point&b) { return fabs((a-*this)*(b-*this)/a.dis(b));}// 点到直线的距离 double disLineSeg(Point&a,Point&b){ return onLine(a,b)?disLine(a,b):Min(dis(a),dis(b));} // 点到线段的距离 Point Rotate(double angle){ Point f={sin(angle),cos(angle)};return {*this*f,dot(f)};}//逆时针旋转 Point Rotate90(){ return {-y,x};} }; double S(const Point&a,const Point&b,const Point&c){// 三角形面积 return 0.5*((a-b)*(a-c)); } inline Point lineLineIntersectPoint(const Point&p1,const Point&p2,const Point&q1,const Point&q2){ Point q12=q2-q1; double k=(p2-p1)*q12; if(Equal(k,0)) return {INF*INF,INF*INF}; double r=((q1-p1)*q12)/k; return p1+(p2-p1)*r; } inline Point circumcenter(Point&a,Point&b,Point&c){// 外心 Point t1=(a+b)*0.5,t2,t3=(b+c)*0.5,t4; t2=t1+(a-b).Rotate90(); t4=t3+(b-c).Rotate90(); return lineLineIntersectPoint(t1,t2,t3,t4); } inline Point incenter(Point&a,Point&b,Point&c){//内心 double r12=a.dis(b),r23=b.dis(c),r31=c.dis(a); Point t1=(b*r31+c*r12)/(r12+r31); Point t2=(a*r23+c*r12)/(r12+r23); return lineLineIntersectPoint(a,t1,b,t2); } inline Point prepencenter(Point&a,Point&b,Point&c){//垂心 Point t1=a+(b-c).Rotate90(); Point t2=b+(a-c).Rotate90(); return lineLineIntersectPoint(a,t1,b,t2); } inline Point barycenter(Point&a,Point&b,Point&c){//重心 return (a+b+c)/3; } inline double apothem(Point&a,Point&b,Point&c){// 内切圆半径 Point p12=b-a,p13=c-a,p23=c-b; return fabs(p12*p23)/(p12.r()+p13.r()+p23.r()); } inline double circumradius(Point&a,Point&b,Point&c){//外接圆半径 Point p12=b-a,p13=c-a,p23=c-b; return sqrt(p12.r2()*p23.r2())/(2*fabs(p12*p23)); } ``` ```c++ struct Line { Point X, Y; double A, B, C; void pre_work() { auto &[X1, Y1] = X; auto &[X2, Y2] = Y; A = Y2 - Y1, B = X1 - X2, C = Y1 * (X2 - X1) - X1 * (Y2 - Y1); } }; inline Line Midperpandicular(Point &X, Point &Y) {//中垂线 auto &[X1, Y1] = X; auto &[X2, Y2] = Y; Point Mid = (X + Y) / 2; double A = X1 - X2, B = Y1 - Y2, C = (X2 * X2 - X1 * X1 + Y2 * Y2 - Y1 * Y1) / 2; return {Mid, Mid, A, B, C}; } bool Parallel_Line(Line &X, Line &Y) {//是否平行 auto &[X1, Y1, A1, B1, C1] = X; auto &[X2, Y2, A2, B2, C2] = Y; if (fabs(A1 * B2 - A2 * B1) == 0) return 1; return 0; } inline Point Line_Line(Line &X, Line &Y) {//线线交点 auto &[X1, Y1, A1, B1, C1] = X; auto &[X2, Y2, A2, B2, C2] = Y; if (fabs(A1 * B2 - A2 * B1) == 0) return {1.0 * INF * INF, 1.0 * INF * INF}; return {(-B2 * C1 + B1 * C2) / (A1 * B2 - A2 * B1), (-A1 * C2 + C1 * A2) / (A1 * B2 - A2 * B1)}; } ``` ### 2.求凸包 ```c++ Point base; inline int Left(const Point &a, const Point &b, const Point &c) { return ((b - a) * (c - a)) >= 0; } inline vector<Point> Convex(vector<Point>a) { int n = a.size(), cnt = 0; if(n < 3) return a; base = a[0]; for(auto p : a){ if(make_pair(p.x, p.y) < make_pair(base.x, base.y)) base = p; } sort(a.begin(), a.end(), [](const Point &a, const Point &b) { ll d = ((a - base) * (b - base)); if(d) return d > 0; return (a - base).r2() < (b - base).r2(); }); vector<Point>res; for(int i = 0; i < n; ++ i) { while(cnt > 1 && Left(res[cnt - 2], a[i], res[cnt - 1])) -- cnt, res.pop_back(); res.push_back(a[i]), ++ cnt; } int fixed = cnt; for(int i = n - 2; ~i; -- i) { while(cnt > fixed && Left(res[cnt - 2], a[i], res[cnt - 1])) -- cnt, res.pop_back(); res.push_back(a[i]), ++ cnt; } res.pop_back(); return res; } ``` ### 3.最小圆覆盖 ```c++ inline Point incenter(Point &A, Point &B, Point &C) {//内心 Line X = Midperpandicular(A, B), Y = Midperpandicular(B, C); return Line_Line(X, Y); } struct Circle { Point O; double r; }; int n; Point A[N]; Circle Minimum_Circle_Coverage() { Point O; double r2 = 0; for (int i = 1; i <= n; i++) { if ((A[i] - O).r2() > r2) { O = A[i], r2 = 0; for (int j = 1; j < i; j++) { if ((A[j] - O).r2() > r2) { O = (A[i] + A[j]) / 2, r2 = (A[j] - O).r2(); for (int k = 1; k < j; k++) { if ((A[k] - O).r2() > r2) { O = incenter(A[i], A[j], A[k]), r2 = (A[k] - O).r2(); } } } } } } return {O, sqrt(r2)}; } ```