爱飞鱼的blog

给定 n×n 的矩阵 A，求 A^k。 12345678910111213141516171819202122232425262728293031323334353637typedef 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++) t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j])%mod; return t;}void...

debug:重载乘号的时候要把两个传进来的矩阵用起来 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384// Problem: P3390 【模板】矩阵快速幂// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P3390// Memory Limit: 256 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>using namespace std;#define ll long long# define int long long#define ull unsigned long...

输出一个整数，表示a*b mod p的值。 数据范围 1≤a,b,p≤1018 1234567891011ll qadd(ll a, ll b, ll p){ ll res = 0; while (b) { if (b & 1) res = (res + a) % p; a = (a + a) % p; b >>= 1; } return res;} 利用longlong取模溢出相抵消 123456789ll mul(ll x,ll y,ll m){ x%=m;y%=m; ll d=((long double )x*y/m); d=x*y-d*m; if(d>=m)d-=m; if(d<0)d+=m; return d;}

曼哈顿距离与切比雪夫距离 距离 - OI Wiki (oi-wiki.org)已经说的比较清晰，提取要点和结论便于复习使用。 曼哈顿距离：d(A,B)=∣x1−x2∣+∣y1−y2∣d \left(\right. A , B \left.\right) = \left|\right. x_{1} - x_{2} \left|\right. + \left|\right. y_{1} - y_{2} \left|\right.d(A,B)=∣x1​−x2​∣+∣y1​−y2​∣ 切比雪夫距离：d(A,B)=max(∣x1−x2∣,∣y1−y2∣)d \left(\right. A , B \left.\right) = max \left(\right. \left|\right. x_{1} - x_{2} \left|\right. , \left|\right. y_{1} - y_{2} \left|\right....

找到最小的数满足里面有n个不被x整除的整数，m个不被y整除的数，且这n个数和m个数完全不重合。x和y都是质数 1234567891011121314151617181920212223int 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 mid=(l+r)>>1; if(check(mid))r=mid; else...

将O（n)优化成o（根号n） [CQOI2007] 余数求和 题目描述 给出正整数 nnn 和 kkk，请计算 G(n,k)=∑i=1nk mod iG(n, k) = \sum_{i = 1}^n k \bmod i G(n,k)=i=1∑n​kmodi 对于 100%100\%100% 的数据，保证 1≤n,k≤1091 \leq n, k \leq 10^91≤n,k≤109 1234567891011121314void solve(){ int n,k;cin>>n>>k; int ans=n*k; //注意推导公式字母不要弄混 for(int l=1,r=1;l<=n;l=r+1){ if((k/l)==0)break;//注意特判分母为0的情况，不然会RE r=k/(k/l); r=min(n,r);//防止多算 //cerr<<l<<"...

I题：要求矩阵的最大子矩阵和，其中第i行第j列是ai*bj。 经过代数变形问题等价求:a的连续子段和b的连续子段和. 考虑到有负数存在，我们四个dp数组分别记录a的最小子段和a的最大子段,b同理。 答案就是最值最值（4种可能） j题：给出一个有根树，1为根。给出节点颜色，要求红节点的子树点权和是3的倍数。 每个点的点权为1或2，给出任意一种构造方案。 解法：分析可知两种情况下无法构造 红叶子没有子节点，子树和无法到3. 红节点的儿子不存在白节点

https://www.acwing.com/activity/content/competition/problem_list/3648/ B题收获： 1.利用题目告诉的结论：1e9范围质数之差小于300 2.一个数不被2-a的任何数整除 等价于他的最小质因子需要大于a c题：初步宏观思路：不难想到用并查集维护类别，只需将每一个类缩成一个点，由于最多只有500个类别，跑一个floyd就可以了 部分细节处理：我的思路是类别用并查集维护，开了一个哈希表去存每个类别对应的根节点是最终floyd的第几个点，in...

B题是纯数学期望推导，用到错位相减，注意数学式子推导过程中一些常数不要丢掉，由于式子其中一部分非常复杂导致计算出来后忘掉最初式子。 c题待补 D题是贪心，需要找到最优策略。策略是倒着推并且遇到当前数出现次数比他的出现次数多时就停下。不停下会导致多出现的呢个数没有数列带它走。

B 水平考试 ====== 等价于两个集合 S,TS, TS,T 判断 SSS 中是否存在 TTT 中所不包含的元素。 若存在则输出 0； 否则输出 10。 时间复杂度：O(T)O(T)O(T) C题：区间查询当前区间可以被分为多少段，要求每段只有一种数字。 做法1：提前对所有段编号，查询时直接左右边界编号相减，注意边界需要特别处理 做法2：标记第i段与第i+1段之间的分界点，然后求前缀和，本质上和做法1一样 D题：给定网格，0表示障碍，1表示道路。问有多少块长方形道路？（正方形也是长方形） 对此我们首先用过bfs找到连通块，对于每个连通块我们需要维护这个连通块最大x，y坐标， 最小x，y坐标，以及连通块大小。当连通块是矩形的时候通过 统计矩形的(minX, minY) -> (maxX, maxY) 然后判断 (maxY - minY + 1) * (maxX - minX + 1) ==...