dw网站怎么做跳转,免费网页在线代理服务器,整站seo优化哪家好,个人社保缴费基数是什么意思这要从校赛的一个区间与非操作题说起#xff0c;群里大佬用的ddp思想使其满足结合律#xff0c;但是我连矩阵乘法都不会于是从头开始学习矩阵乘法。
P3390 【模板】矩阵快速幂
和快速幂一模一样#xff0c;只是把数乘换成矩阵乘#xff0c;只需要定义结构体矩阵然后重载一…这要从校赛的一个区间与非操作题说起群里大佬用的ddp思想使其满足结合律但是我连矩阵乘法都不会于是从头开始学习矩阵乘法。
P3390 【模板】矩阵快速幂
和快速幂一模一样只是把数乘换成矩阵乘只需要定义结构体矩阵然后重载一下乘法*即可。 注意 111乘以任何数都等于这个数本身 单位矩阵乘以任何矩阵就等于这个矩阵本身
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const ll mod1e97;
const int N110;
int n;
ll k;
struct node
{ll m[N][N];node(){memset(m,0,sizeof m);};node operator *(const node b) const{node res;for(int i1;in;i)for(int j1;jn;j)for(int k1;kn;k) res.m[i][j](res.m[i][j]m[i][k]*b.m[k][j])%mod;return res;}
};
node qmi(node a,ll b)
{node res;for(int i1;in;i)// 单位矩阵res.m[i][i]1;while(b){if(b1) resres*a;aa*a;b1;}return res;
}
int main()
{IO;int T1;//cinT;while(T--){node a;cinnk;for(int i1;in;i)for(int j1;jn;j) cina.m[i][j];node resqmi(a,k);for(int i1;in;i){for(int j1;jn;j) coutres.m[i][j] ;cout\n;}}return 0;
}P1962 斐波那契数列
[0011][fn−2fn−1][fn−1fn]→[0011]n−2[f1f2][fn−1fn]\begin{bmatrix} 0 0 \\ 11 \end{bmatrix} \begin{bmatrix} f_{n-2}\\f_{n-1} \end{bmatrix}\begin{bmatrix} f_{n-1}\\f_{n} \end{bmatrix} \to\begin{bmatrix} 0 0 \\ 11 \end{bmatrix}^{n-2} \begin{bmatrix} f_{1}\\f_{2} \end{bmatrix}\begin{bmatrix} f_{n-1}\\f_{n} \end{bmatrix} [0101][fn−2fn−1][fn−1fn]→[0101]n−2[f1f2][fn−1fn] 矩阵乘法满足结合律由此可以根据上述式子进行矩阵快速乘
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const ll mod1e97;
const int N110;
int sz;//矩阵大小
ll n,k;
struct node
{ll m[N][N];node(){memset(m,0,sizeof m);};node operator *(const node b) const{node res;for(int i1;isz;i)for(int j1;jsz;j)for(int k1;ksz;k) res.m[i][j](res.m[i][j]m[i][k]*b.m[k][j])%mod;return res;}
};
node qmi(node a,ll b)
{node res;for(int i1;isz;i)// 单位矩阵res.m[i][i]1;while(b){if(b1) resres*a;aa*a;b1;}return res;
}
int main()
{IO;int T1;//cinT;while(T--){cinn;if(n2) {cout1\n;continue;}sz2;node a;a.m[1][1]0,a.m[1][2]1,a.m[2][1]1,a.m[2][2]1;node resqmi(a,n-2);ll ans0;ans(ansres.m[1][2]res.m[2][2])%mod;coutans\n;}return 0;
}P1939 【模板】矩阵加速数列和上面这个题基本一样。
P2044 [NOI2012]随机数生成器
[a101][xn−1c][xnc]→[a101]n[x0c][xnc]\begin{bmatrix} a 1 \\ 01 \end{bmatrix} \begin{bmatrix} x_{n-1}\\c \end{bmatrix}\begin{bmatrix} x_{n}\\c \end{bmatrix} \to\begin{bmatrix} a 1 \\ 01 \end{bmatrix}^n \begin{bmatrix} x_{0}\\c \end{bmatrix}\begin{bmatrix} x_{n}\\c \end{bmatrix}[a011][xn−1c][xnc]→[a011]n[x0c][xnc] 这题比较dt的地方是两个数相乘会爆long long于是上龟速乘防止乘积爆
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N110;
int sz;//矩阵大小
ll mod;
ll mul(ll a,ll b)//龟速乘
{ll res0;a%mod;while(b){if(b1) res(resa)%mod;a(aa)%mod;b1;}return res;
}
struct node
{ll m[N][N];node(){memset(m,0,sizeof m);};node operator *(const node b) const{node res;for(int i1;isz;i)for(int j1;jsz;j)for(int k1;ksz;k) res.m[i][j](res.m[i][j]mul(m[i][k],b.m[k][j]))%mod;return res;}
};
node qmi(node a,ll b)
{node res;for(int i1;isz;i)// 单位矩阵res.m[i][i]1;while(b){if(b1) resres*a;aa*a;b1;}return res;
}
int main()
{IO;int T1;//cinT;sz2;ll a,c,x0,n,g;while(T--){cinmodacx0ng;node now;now.m[1][2]now.m[2][2]1,now.m[1][1]a;node resqmi(now,n);ll ans(mul(res.m[1][1],x0)mul(res.m[1][2],c))%mod%g;coutans\n;}return 0;
}SP1716 GSS3 - Can you answer these queries III
矩阵乘法优化dp 考虑P1115 最大子段和如何做 不难得知设计dp即可。 状态表示fif_ifi表示以第iii个位置为结尾最大字段和gimax(f1,f2,…,fi)g_imax(f_1,f_2,\dots,f_i)gimax(f1,f2,…,fi) 状态转移fimax(fi−1ai,ai)f_imax(f_{i-1}a_i,a_i)fimax(fi−1ai,ai)gimax(gi−1,fi)g_imax(g_{i-1},f_i)gimax(gi−1,fi) 最终答案即是gng_ngn
总所周知递推不满足结合律换句话说就是你必须一步一步递推不过矩阵乘法能够优化递推 斐波那契前 n 项和 而优化的方式就是使计算过程具有结合律那么如果我们通过矩阵操作使一些不具有结合律的东西具有结合律那么我们就能用线段树维护这个东西花费log代价显然使非常优秀的。
效仿矩阵乘法优化斐波那契的方法寻找矩阵 [ai−∞aiai0ai−∞−∞0]?[fn−1gn−10][fngn0]\begin{bmatrix} a_i-\inftya_i\\a_i0a_i\\ -\infty-\infty0\\ \end{bmatrix}? \begin{bmatrix} f_{n-1}\\g_{n-1}\\0 \end{bmatrix} \begin{bmatrix} f_n\\g_n\\0 \end{bmatrix} ⎣⎡aiai−∞−∞0−∞aiai0⎦⎤?⎣⎡fn−1gn−10⎦⎤⎣⎡fngn0⎦⎤ ???表示一个运算 [abcd]?[ef][max(ae,bf)max(ce,df)]\begin{bmatrix} ab\\cd \end{bmatrix}? \begin{bmatrix} e\\f \end{bmatrix}\begin{bmatrix}max(ae,bf)\\max(ce,df) \end{bmatrix}[acbd]?[ef][max(ae,bf)max(ce,df)] 不难发现上述定义的新运算是具有结合律的 对比此运算和矩阵乘法与运算不难发现 矩阵乘法中的“乘”相当于这里的“加”而矩阵乘法中的“加”相当于这里的“max” 矩阵乘法满足结合律实际上使“乘”对“加”满足分配了而这里“加”对“max”同样满足分配率于是新运算具有结合律。
满足结合律并且区间查询单点修改无疑线段树只需要每个节点维护一个矩阵即可。
考虑答案在哪? 定义 Ai[ai−∞aiai0ai−∞−∞0]A_i \begin{bmatrix} a_i-\inftya_i\\a_i0a_i\\ -\infty-\infty0\\ \end{bmatrix}Ai⎣⎡aiai−∞−∞0−∞aiai0⎦⎤ BiA1?A2?…?AiB_i A_1?A_2?\dots\ ?A_i BiA1?A2?… ?Ai 那么再看此题 P1115 最大子段和不难得出 Bn?[000][fngn0]B_n ?\begin{bmatrix} 0\\0\\0 \end{bmatrix}\begin{bmatrix} f_n\\g_n\\0 \end{bmatrix}Bn?⎣⎡000⎦⎤⎣⎡fngn0⎦⎤ 答案就是gng_ngn不难发现答案就蕴藏着BnB_nBn矩阵中分析一下不难得知如果Bn[b11b12b12b21b22b23b31b32b33]B_n\begin{bmatrix} b_{11}b_{12}b_{12}\\b_{21}b_{22}b_{23}\\ b_{31}b_{32}b_{33}\\ \end{bmatrix}Bn⎣⎡b11b21b31b12b22b32b12b23b33⎦⎤那么答案就是max(b21,b23)max(b_{21},b_{23})max(b21,b23)
而本题有了之前的工作只需要套个线段树就是基本的区间修改单点查询问题。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int maxn3,INF0x3f3f3f3f;
const int N50010;//投机取巧
int n,q,a;
int sz;//矩阵大小
struct node
{int l,r;int m[maxn][maxn];node(){lr0;memset(m,0,sizeof m);};node operator *(const node b) const{node res;res.ll,res.rb.r;memset(res.m,-0x3f,sizeof res.m);for(int i0;isz;i)for(int j0;jsz;j)for(int k0;ksz;k) res.m[i][j]max(res.m[i][j],m[i][k]b.m[k][j]);return res;}int ans(){return max(m[1][0],m[1][2]);}
}tree[N2];
void pushup(int u)
{tree[u]tree[u1]*tree[u1|1];
}
void build(int u,int l,int r)
{if(lr){cina;//这样输入省空间tree[u].ltree[u].rr;tree[u].m[0][0]tree[u].m[1][0]tree[u].m[0][2]tree[u].m[1][2]a;tree[u].m[0][1]tree[u].m[2][0]tree[u].m[2][1]-INF;return;}int midlr1;build(u1,l,mid);build(u1|1,mid1,r);pushup(u);
}
void modify(int u,int pos,int x)
{if(tree[u].ltree[u].r){tree[u].m[0][0]tree[u].m[1][0]tree[u].m[0][2]tree[u].m[1][2]x;return;}int midtree[u].ltree[u].r1;if(posmid) modify(u1,pos,x);else modify(u1|1,pos,x);pushup(u);
}
node query(int u,int l,int r)
{if(tree[u].lltree[u].rr) return tree[u];int midtree[u].ltree[u].r1;if(rmid) return query(u1,l,r);else if(lmid)return query(u1|1,l,r);else return query(u1,l,r)*query(u1|1,l,r);
}
int main()
{IO;cinn;sz3;build(1,1,n);cinq;while(q--){int op,x,y;cinopxy;if(op1){if(xy) swap(x,y);coutquery(1,x,y).ans()\n;}elsemodify(1,x,y);}return 0;
}
