题目：[NOIP2002普及组]过河卒题目描述棋盘上\(A\)点有一个过河卒，需要走到目标\(B\)点。卒行走的规则：可以向下、或者向右。同时在棋盘上\(C\)点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示，\(A\)点\((0,0)\)、\(B\)点\((n,m)\)，同样马的位置坐标是需要给出的。现在要求你计算出卒从\(A\)点能够到达\(B\)点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。输入格式一行四个正整数，分别表示\(B\)点坐标和马的坐标。输出格式一个整数，表示所有的路径条数。样例#1样例输入#
题目传送门前言线段树好题！！！！咕咕了挺久的一道题目，很早之前就想写了，今天终于找了个时间A掉了。题意给定一个\(1\)到\(n\)的排列，有\(m\)次操作，分两种类型。1.0lr表示将下标在\([l,r]\)区间中的数升序排序。2.1lr表示将下标在\([l,r]\)区间中的数降序排序。给定一个数\(q\)询问最后\(q\)位置上的数。\(Solution\)看到数据范围，发现前\(30\)分是可以暴力的，这里不多赘述。注意到\(n,m\leqslant10^5\),优先考虑\(O(nlogn)\)或\(O(n\sqrtn)\)做法。对一个序列进行操作，自然想到，线段树，但是线段树不支持区
题目传送门前言线段树好题！！！！咕咕了挺久的一道题目，很早之前就想写了，今天终于找了个时间A掉了。题意给定一个\(1\)到\(n\)的排列，有\(m\)次操作，分两种类型。1.0lr表示将下标在\([l,r]\)区间中的数升序排序。2.1lr表示将下标在\([l,r]\)区间中的数降序排序。给定一个数\(q\)询问最后\(q\)位置上的数。\(Solution\)看到数据范围，发现前\(30\)分是可以暴力的，这里不多赘述。注意到\(n,m\leqslant10^5\),优先考虑\(O(nlogn)\)或\(O(n\sqrtn)\)做法。对一个序列进行操作，自然想到，线段树，但是线段树不支持区
「学习笔记」数位DP意义不大的题不写了。点击查看目录目录「学习笔记」数位DP概述例题P2657[SCOI2009]windy数思路代码P4317花神的数论题思路P4124[CQOI2016]手机号码思路代码haha数题意思路代码0和1的熟练题意思路代码苍与红的试炼题意思路代码概述数位DP一般用来解决「在一个较大的区间内统计具有一定特征的数的数量」的问题。数位DP一般有两种做法：递推法：首先需要预处理出具有一定条件的数的个数，然后将上限按数位拆分开来考虑贡献。暴搜法：直接记忆化搜索具有特定条件的数的个数。例题P2657[SCOI2009]windy数思路本题使用递推。设\(f_{i,j}\)表示
「学习笔记」数位DP意义不大的题不写了。点击查看目录目录「学习笔记」数位DP概述例题P2657[SCOI2009]windy数思路代码P4317花神的数论题思路P4124[CQOI2016]手机号码思路代码haha数题意思路代码0和1的熟练题意思路代码苍与红的试炼题意思路代码概述数位DP一般用来解决「在一个较大的区间内统计具有一定特征的数的数量」的问题。数位DP一般有两种做法：递推法：首先需要预处理出具有一定条件的数的个数，然后将上限按数位拆分开来考虑贡献。暴搜法：直接记忆化搜索具有特定条件的数的个数。例题P2657[SCOI2009]windy数思路本题使用递推。设\(f_{i,j}\)表示
矩阵对角化今天听\(\texttt{m}\color{red}\texttt{yee}\)嘴的，赶紧来补个学习笔记。我们有点时候需要计算一个较小矩阵的\(n\)次幂，但直接求幂非常不方便，这是会考虑矩阵对角化，将\(M\)改写为\(\mathcal{PDP^{-1}}\)，这样\(M^n\)次就可以写为\((\mathcal{PDP^{-1}})=\mathcal{PD^nP^{-1}}\)，转化为快速计算\(\mathcal{D^n}\)。求解方法我们定义一个矩阵\(\mathcal{A}\)的特征向量为\(\alpha\)，相应特征值为\(\gamma\)，他们满足：\[\mathcal{
矩阵对角化今天听\(\texttt{m}\color{red}\texttt{yee}\)嘴的，赶紧来补个学习笔记。我们有点时候需要计算一个较小矩阵的\(n\)次幂，但直接求幂非常不方便，这是会考虑矩阵对角化，将\(M\)改写为\(\mathcal{PDP^{-1}}\)，这样\(M^n\)次就可以写为\((\mathcal{PDP^{-1}})=\mathcal{PD^nP^{-1}}\)，转化为快速计算\(\mathcal{D^n}\)。求解方法我们定义一个矩阵\(\mathcal{A}\)的特征向量为\(\alpha\)，相应特征值为\(\gamma\)，他们满足：\[\mathcal{
5042.龟速飞行棋题目链接：5042.龟速飞行棋赛中没过，赛后补题时由于题解有些抽象，自己写个题解。可以发现每次转移的结果只跟后面两个点的胜负状态有关。不妨设\(f_{u,a,b}\)表示，\(u+1\)号点的胜负态为\(a\)，\(u+2\)号点的胜负态为\(b\)，此时从\(1\)号点出发的胜负态是什么。那么可以发现，利用\(a,b\)的数值，可以求出\(u\)号点的胜负态\(uwin\)。这样就可以从\(n\)号点的胜负态一路推到\(1\)号点的胜负态，就可以简单做了。当\(u=n\)时，不妨令\(a=1,b=1\)，这样\(u\)号点必败。\(u-1\)号点若\(t_u=2\)必败，
5042.龟速飞行棋题目链接：5042.龟速飞行棋赛中没过，赛后补题时由于题解有些抽象，自己写个题解。可以发现每次转移的结果只跟后面两个点的胜负状态有关。不妨设\(f_{u,a,b}\)表示，\(u+1\)号点的胜负态为\(a\)，\(u+2\)号点的胜负态为\(b\)，此时从\(1\)号点出发的胜负态是什么。那么可以发现，利用\(a,b\)的数值，可以求出\(u\)号点的胜负态\(uwin\)。这样就可以从\(n\)号点的胜负态一路推到\(1\)号点的胜负态，就可以简单做了。当\(u=n\)时，不妨令\(a=1,b=1\)，这样\(u\)号点必败。\(u-1\)号点若\(t_u=2\)必败，
平方剩余、二次互反律一、平方剩余定义：设p为奇素数且\(\mathsf{a\neq0\mod\p}\)，如果a在模p下是另一个数的平方，即\(\mathsf{a\equivb^{2}\mod\p}\)，则称a为模p下的平方剩余，否则称a为平方非剩余。而二次同余式\(\mathsf{x^{2}\equiva\mod\p}\)可能有0—2个解例子：\(\mathsf{p=5}\)时，因为\(\mathsf{1^{2}\equiv1\mod\5\qquad2^{2}\equiv4\mod\5\qquad3^{2}\equiv4\mod\5\qquad4^{2}\equiv1\mod\5}\)则1，4
