子序列自动机
title: 子序列自动机categories: - ICPCtags: - nullabbrlink: df3bb3f1date: 2023-11-09 00:00:00子序列自动机判断s是不是t的子序列 bool isSubsequence(string s, string t) { int m = t.size(); vector<array<int, 26>> next(m + 2); t = " " + t; for (int i = m; i >= 1; i--) { for (int j = 0; j < 26; j++) { if (j == t[i] - 'a') next[i][j] = i + 1; else { next[i][j] = next[i + 1][j]; ...
矩阵乘法+快速幂
title: 矩阵乘法+快速幂categories: - ICPCtags: - nullabbrlink: f4d30541date: 2023-11-04 00:00:00给定 n×n 的矩阵 A，求 A^k。typedef long long LL; const int mod=1000000007; struct matrix{ LL c[101][101]; matrix(){memset(c, 0, sizeof c);} } A, res; LL n, k; matrix operator*(matrix &x, matrix &y){ //矩阵乘法 matrix t; //临时矩阵 for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) for(int k=1; k<=n; k++) ...
线段树
title: 线段树categories: - ICPCtags: - nullabbrlink: 8893d943date: 2023-10-30 00:00:00线段树template <class Info, class Tag> struct LazySegmentTree { int n; vector<Info> info; vector<Tag> tag; LazySegmentTree() : n(0) {} LazySegmentTree(int n_, Info v_ = Info()) { init(vector<Info>(n_ + 1, v_)); } LazySegmentTree(vector<Info> t_) { init(t_); } void init(vector<Info> a) //[1,n] { ...
矩阵求逆
title: 矩阵求逆categories: - ICPCtags: - nullabbrlink: ‘73460288’date: 2023-10-29 00:00:00 N≤400，所有 0≤aij<1e9+7 const int N=405,P=1e9+7; int n; LL a[N][N<<1]; LL quickpow(LL a, LL b){ LL ans = 1; while(b){ if(b & 1) ans = ans*a%P; a = a*a%P; b >>= 1; } return ans; } bool Gauss_Jordan(){ for(int i=1;i<=n;++i){ //枚举主元的行列 int r = i; for(int k=i; k<=n; ++k) //找非0行 if(a[k][i]) {r=k; break;} ...
高斯消元
title: 高斯消元categories: - ICPCtags: - nullabbrlink: 55f2dbb7date: 2023-10-29 00:00:00高斯消元1.高斯消元解线性方程组。这个模板只处理n方程n个未知数的，分别处理无解，无穷多解，以及唯一解的情况。结果存在最后一列中（一开始的常数项）， 无解返回0 唯一解返回1 无穷多解返回2 int gauss(vector<vector<db>>& a, int n) { int r = 1; // 当前行 for (int c = 1; c <= n; c++) { // 消元进行到第c列 // 1.找到c列的最大行t int t = r; for (int i = r; i <= n; i++) if (fabs(a[i][c]) > fabs(a[t][c])) t...
字符串哈希学习笔记
title: 字符串哈希学习笔记categories: - ICPCtags: - nullabbrlink: 72aa3132date: 2023-10-27 00:00:00字符串哈希学习笔记板子：传入0base即可 struct Hash { static int findprime() { random_device rd; mt19937 gen(rd()); int n = gen() % 900000000 + 100000000; if (n % 2 == 0) n++; while (true) { bool ok = 1; for (int i = 3; i * i <= n; i += 2) { if (n % i == 0) { ok = 0; ...
Acwing第 131 场周赛 之找最值过程中维护某个性质的方案
title: Acwing第 131 场周赛 之找最值过程中维护某个性质的方案categories: - ICPCtags: - nullabbrlink: 31013d11date: 2023-10-18 00:00:00https://www.acwing.com/problem/content/5367/题目如果只需要输出最大值，我都没有问题。每次需要输出方案的时候,我似乎都需要先统计最大值，再重新扫描一遍找所有能够取得最大值的方案，然后在这些方案中找到最大值。最好的做法应该是在找最大值的过程中就维护题目要求方案的排序关键字，有时候这个关键字不是我们枚举顺序能决定的，我们就需要单独处理。 // Problem: 奶牛报数 // Contest: AcWing // URL: https://www.acwing.com/problem/content/5367/ // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor...
Codeforces Round 294 (Div. 2)
title: Codeforces Round 294 (Div. 2)categories: - ICPCtags: - nullabbrlink: 44a66cd8date: 2023-10-16 00:00:00Codeforces Round 294 (Div. 2)C题：有n个老师，m个学生，a方案是1老师和2学生，b方案是2老师和1学生，求最多可以成功达成多少套方案？Sol：wa了一发贪心，样例怎么全过了？从纯数学的角度去看，就是线性规划，只不过由于参数不确定需要分类讨论，我们只需要设x套a，y套b，求x+y的最大值（在两个总人数的约束条件下。void solve(){ cin>>n>>m; if(m<n)swap(n,m); if(m>2*n)cout<<n<<endl; else cout<<(n+m)/3<<endl; //cout<<ad+tmp<<endl; } 考虑到数据范围很小，官方正解是直接暴力枚举int...
Codeforces Round 888 (Div. 3) 补四个月前的一场题（早晚要还的
title: Codeforces Round 888 (Div. 3) 补四个月前的一场题（早晚要还的categories: - ICPCtags: - nullabbrlink: 401126dadate: 2023-09-26 00:00:00https://zhuanlan.zhihu.com/p/646586178待补
容斥原理简单题——需要动手画图才好想清楚
title: 容斥原理简单题——需要动手画图才好想清楚categories: - ICPCtags: - nullabbrlink: ‘45526744’date: 2023-09-22 00:00:00 找到最小的数满足里面有n个不被x整除的整数，m个不被y整除的数，且这n个数和m个数完全不重合。x和y都是质数int n, m,a,b; //int a[N]; bool check(int x){ int n1=x/a; int m1=x/b; int c=x/(a*b); int p=n1-c,q=m1-c; int lf=x-n1-m1+c; int p1=max(m-p,0LL); int q1=max(n-q,0LL); if(p1+q1<=lf)return true; return false; } void solve(){ cin>>n>>m>>a>>b; int l=0,r=2e9; while(l<r){ int...