NOTE1(2021.6.14~2021.8.31)

· · 个人记录

https://www.luogu.com.cn/paste/m3vrqv12

咕：

ABC214(待改)
ABC215(待改)
ABC216(无题解)
二项式定理及变形
a* K≡B (mod N)求a

链接：https://atcoder.jp/contests/abc186/editorial/422

2021.6.14：

Q：你有一个N个从小到大排列的正整数的序列:a =(a1, a2，…，a N)，Q查询。

在第i个查询(1≤i≤Q)中，给定一个正整数K i，在所有不等于a1, a2，…，an的正整数中找出第K个最小的整数。

A：求a之间的间距，lower_bound();代码

2021.6.15:

Q：你有N个白球，M个黑球，满足W_i≤B_i+K，K为输入常数，W_i表示前i个球中的白球个数，B_i同理。

A：将放置一个黑球视为“向x轴方向前进1”，将放置一个白球视为“向y轴方向前进1”，那么M个黑球和N个白球的每一种排列都对应着一条从(0,0)和(M,N)开始的路径。无限制情况下路径总数为(n+m)!/n!/m!;

如何排除不合法的答案？（有一个或多个点在y=k+1及其上方不合法）

令起点在（m+k+1，n-k-1），就保证路径一定不合法

（N,M）-（N-K-1，M+K+1）的方案数即为答案

2021.6.16：

Q：

A：分块+按秩合并并查集代码

Q：维护一个长度为 N 的数组，支持如下几种操作:

操作1：在某个历史版本上修改某一个位置上的值

操作2：访问某个历史版本上的某一位置的值

此外，每进行一次操作完成后生成一个完全一样的版本（从1开始编号，版本0表示初始状态数组）

A：操作树模板/可持久化线段树代码

Q：

A：操作树，a[]存储每个版本的栈顶元素，to[]链接上一个栈中元素代码

A：给定一个长度为n的序列，m个询问，每个询问的形式为：L，r，k表示在[L,r]间中的第k小元素。

Q：模板代码

2021.6.17：

Q：不强制在线

A：操作树/按秩合并并查集，可持久化线段树（维护fa[]，rk[]）代码

Hash：

子段hash：

注：

Q：给定一个长为N的字符串，多个询问：给定一个区间[L,R]，一个字符串A，[L,R]中是否出现给定字符串A（所有询问点字符串len_A均为K）

A：字符串hash+主席树

由于每次询问的字符串相等，故将所有可能出现的长度为K的字符串hash求出，再可持久化代码

Q：N堆方块，告诉你每堆方块的美观度和方块的个数；多个询问：从美观度在 [S,T] 中，位置在 [L,R] 堆的方块里选 K 个方块，求选出方块中美观度最大的方块美观度最小值为多少？

A：主席树，每堆建一个版本，

2021.6.18：

Q：

A：主席树，每次分别查找左、右子树是否有K个（K=(R-L+1)/2），若查到叶子节点依然合法，则存在答案，反之亦然。

Q：给你一个带边权的无向图，K个询问：询问从A点走到B点的所有路径中，最长的边最小值是多少？

A：Kruskal重构树模板（在Kruskal算法进行的过程中，我们把最小生成树的边权改为点权）

2021.6.19：

A&Q：复习模板，【模板】Kruskal重构树双倍经验

Q：n个瓶子，第i个瓶子里又g[i]克物质。m次操作，第i次操作把第a[i]个瓶子的东西全部倒到第b[i]个瓶子里（保证之后不出现a[i]）。k种反应，其中c[i]和d[i]反应，而且如果一个瓶子里有多种反应则优先反应靠前的。每次反应对答案贡献为min(g[i],g[i])* 2

A：把m个操作建重构树，然后将K个询问排序（按照重构树上节点深度排），再计算贡献

与dijkstra差别：节点可重复进入队列（dij不能，且是优先队列）

Q：

A：kruskal重构树；

求权值最大的点有两种方式：1.dfs树上的点，算贡献：

2.树状数组+dfs序：同一个非叶子节点给其子节点的贡献一致

2021.6.20：

A：一个长为N的数列，求多少次操作能将此数列变为回文数列（a[i]=a[N-i+1]），一次操作定义为：选定(x，y)将所有数列中所有x变为y

Q：将每一对a[i]和a[N-i+1]连一条边，发现要使每一连同块中的数相等，每一连同块中的数至少改变k-1次（k为连同块内数的个数）

最少操作数=数列中不同的数的个数-连同块个数。

A：求[L,R]中有多少对(x,y)满足：

Q：

基础/关键：“gcd(A1，…，AN)=X的数列{Ai}有多少?”（ABC162E）

最大公约数是X的倍数的必要充分条件是 A1，…AN 都是 X 的倍数。这样的数列 ?k / x?^ n 个。成为恰好 X 的必要充分条件是“ X 的倍数，并且不是 2x, 3x，…”。根据 X 从大的一方开始依次计算，2x, 3x，… 可以减去的个数来求。计算量是 O(K log K+K log N)。

回归本题：答案=总个数-(g==1)个数 - (x==g或y==g的个数) + （gcd(x,y)=g且x=g或y=g个数）

2021.6.21：

Q：在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。

A：kruskal重构树+主席树（先建立重构树，再用重构树的DFS序建立主席树）

A：给定一个长度为 N 的正整数序列 A ，有 Q 次询问，第 i 次询问给定一个长度为 L_i 的序列 b_i，请你判断 b_i 是不是 A 的子序列。序列 A 和所有 b_i 中的元素都不大于一个给定的正整数 M。

Q：可持久化线段树实现，从后向前加边

2021.6.22：

void getadd(int x,ll d){add[x]=(add[x]+d)%mod,val[x]=(val[x]+d)%mod,sum[x]=(sum[x]+d*siz[x])%mod;}
void getmul(int x,ll d){mul[x]=d*mul[x]%mod,add[x]=d*add[x]%mod,val[x]=d*val[x]%mod,sum[x]=d*sum[x]%mod;}
void pushup(int x){sum[x]=sum[x<<1]+sum[x<<1|1];}
void pushdown(int x){
  if(mul[x]!=1)getmul(x<<1,mul[x]),getmul(x<<1|1,mul[x]),mul[x]=1;
  if(add[x]!=0)getadd(x<<1,add[x]),getadd(x<<1|1,add[x]),add[x]=0;
}

2021.6.23：

Q： 给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。

2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。

3：后接两个整数(x，y)，代表将点x上的权值变成y。

A：LCT模板，4操作直接a[x]=y,access(x);

Q：有n<=100个数（每个数小于10^3），分配到两堆，求两堆中数的和大的那一堆和为多少？

A：考虑动态规划，bool dp[i][j]表示状态i，数的和为j

int n; cin>>n;
for(int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i];
dp[0][0]=1;
for(int i=1;i<=n;++i)
  for(int j=0;j<=sum;++j){
      if(j>=a[i]) dp[i][j]=dp[i-1][j]||dp[i-1][j-a[i]];
      if(dp[i][j]) ans=min(ans,max(j,sum-j));
  }
cout<<ans<<'\n';

2021.6.24：(??﹏?)。。。

2021.6.25：

2021.6.26： 测试+abc207

2021.6.27：

A：n条线段中选3k(k<=3)条线段组成三角形（严格三边关系），求选择三角形的最长周长和？

Q：分类讨论；

k=1:三条边一定连续（排序后）

k=2:两种情况：1.连续六条边（样例一）2.两组不连续的三条边

k=3:同理四种情况：1.连续九条边；2.大的三条边+小的六条边；3.大的六条边+小的三条边；4.三组三条边

2021.6.28：

结论：

曼哈顿距离-->切比雪夫距离:(x,y)-->(x+y,x-y) 切比雪夫距离-->曼哈顿距离:(x+y)-->(\frac{x+y}{2},\frac{x-y}{2})

证明：

A：

Q：两种解题思路；

1.维护每一行的前缀和，以及向斜上方（左上和右上）的前缀和。对于每一行，先求出以（i,j）为中心的菱形，然后当转移到（i,j+1）时，变化的只有斜边，也就是减掉原菱形左上和左下的斜边，加上现菱形右上和右下的斜边即可。

2.[重点] ：将菱形->正方形（曼哈顿转切比雪夫）

(x,y)-->(x+y,x-y)

2021.6.29：

定义：一种编码方式，长度为n-2，可唯一表示一颗n个节点 带标号无根树

Tree_to_Prufer构建：每次在叶子节点中选择编号最小的节点，记录其父亲节点编号，并删除它；

构建：使用堆可以做到 O(nlogn) 的复杂度；使用一个指针代替堆找最小值，可以做到 O(n) 的复杂度。

指针作法：具体而言，指针指向编号最小的叶节点。每次删掉它之后，如果产生了新的叶节点且编号比指针指向的更小，则直接继续删掉，否则自增找到下一个编号最小的叶节点。

莱凯定理：n个点的带标号无根树有 n^{n-2} 个（无根树数量==prufer序列数）

指定度数树计数：n个节点依次有 d_1,d_2,d_3...d_n 的无根数共有 \frac{(n-2)!}{\prod_{i=1}^n*(d_i-1)!}

A：实现Prufer序列和无根树的相互转化

Q：

Q：熊大妈的乃修在时针的带领下，围成了一个圆圈舞蹈，由于没有严格的教育，奶牛们之间的间隔不一致。

奶牛想知道两只最远的奶牛到底隔了多远。奶牛A到B的距离为A顺时针走和逆时针走，到达B的较短路程。告诉你相邻两个奶牛件的距离，请你告诉奶牛两只最远的奶牛到底隔了多远。

A：环变链，复制一遍，用队列维护

A：一开始森林里面有N只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过N-1次打架之后，整个森林的小猴都会成为好朋友。 现在的问题是，总共有多少种不同的打架过程。 比如当N=3时，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。

Q：n个点的无根树数量* n-1条边的排列数

Q：n个数中分别选择 A_l,A_l+1,...A_r 个数组成无根树，答案为 ANS_l,ANS_l+1,...ANS_r

A：保存 i!，i!的逆元，i^{i-2}（1<=i<=n），再答案前缀和

2021.6.30：

int qpow(int a,int b){
    int ans=1;
    while(b){if(b&1) ans=ans*a%p;a=a*a%p;b>>=1;}
    return ans;
}
signed main()
{
    scanf("%d",&p);//p>n
    scanf("%d",&a),cout<<qpow(a,p-2)<<'\n';//求a在mod p下的逆元 
    scanf("%d",&n);//1~n在mod p下的逆元 
    for(int i=(inv[1]=1,cout<<1<<' ',2);i<=n;++i) inv[i]=(p-p/i)*inv[p%i]%p,cout<<inv[i]<<' ';puts("");
    scanf("%d",&n);//1!~n!在mod p下的逆元 
    for(int i=1;i<=n;++i) ani=ani*i%p;
    for(int i=(ni[n]=qpow(ani,p-2),n-1);i+1;--i) ni[i]=ni[i+1]*(i+1)%p;
    for(int i=1;i<=n;++i) cout<<ni[i]<<' ';
    return 0;
}

A：限定某些点度数的树计数

Q：\frac{(n-2)!}{\prod_{i=1}^k\cdot (d_i-1)!}\cdot \binom{n-2}{s}\cdot (n-k)^{n-2-s}

化简得：\frac{(n-2)!\cdot (n-k)^{n-2-s}}{\prod_{i=1}^k\cdot (d_i-1)!\cdot (n-2-s)!}

实现：分解质因数+高精乘单精（UB交标）

A：指定度数树计数

Q：n个节点依次有 d_1,d_2,d_3...d_n 的无根数共有 \frac{(n-2)!}{\prod_{i=1}^n*(d_i-1)!}

实现：分解质因数+高精乘单精

A：

Q：prufer+背包DP

修建轨道最少->结构为一棵树

背包DP：

算法流程：

2021.7.1：

Q：用1 2的矩阵填满n m的矩阵的方法有多少种

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,dp[13][13][1<<13];
int main()
{
    freopen("temp.in","r",stdin);
    while(scanf("%d%d",&n,&m)){
        if(!n&&!m) return 0;
        memset(dp,0,sizeof(dp));
        dp[0][m][0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<(1<<m);++j) dp[i][0][j<<1]=dp[i-1][m][j];
            for(int j=1;j<=m;++j){
                int x=1<<j,y=1<<j-1;
                for(int k=0;k<(1<<m+1);++k){
                    if(!(k&x)&&(k&y)) dp[i][j][k]=dp[i][j-1][k^y];
                    else if((k&x)&&!(k&y)) dp[i][j][k]=dp[i][j-1][k^x];
                    else if(!(k&x)&&!(k&y)) dp[i][j][k]=dp[i][j-1][k^x]+dp[i][j-1][k^y];
                }
            }
        }
        cout<<dp[n][m][0]<<'\n';
    }
}

Q：在n* m的矩阵中，有些格子有树，没有树的格子不能到达，找一条或多条回路，吃完所有的树，求有多少中方法。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int gp[12][12],n,m;
long long dp[13][13][1<<13];
void DP()
{
    memset(dp,0,sizeof(dp));
    dp[0][m][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<(1<<m);++j) dp[i][0][j<<1]=dp[i-1][m][j];
        for(int j=1;j<=m;++j){
            int x=1<<j,y=1<<j-1;
            for(int k=0;k<(1<<m+1);++k){
                if(gp[i][j]){
                    if((k&x)&&(k&y)) dp[i][j][k]=dp[i][j-1][k-x-y];
                    else if(!(k&x)&&!(k&y))dp[i][j][k]=dp[i][j-1][k+x+y];
                    else dp[i][j][k]=dp[i][j-1][k^x^y]+dp[i][j-1][k];
                }
                else{
                    if(!(k&x)&&!(k&y)) dp[i][j][k]=dp[i][j-1][k];
                    else dp[i][j][k]=0;
                }
            }
        }
    }
    cout<<"There are "<<dp[n][m][0]<<" ways to eat the trees.\n";
}
int main()
{
    int T; scanf("%d",&T);
    for(int k=1;k<=T;++k){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&gp[i][j]);
        cout<<"Case "<<k<<": ";
        DP();
    }
    return 0;
}
/*
cin:
2
6 3
1 1 1
1 0 1
1 1 1
1 1 1
1 0 1
1 1 1

2 4
1 1 1 1
1 1 1 1

cout:
Case 1: There are 3 ways to eat the trees.
Case 2: There are 2 ways to eat the trees.
*/

2021.7.2：

2021.7.3： 测试 2021.7.4：ABC208 2021.7.5：

Q：

A：二分+模拟

先我们使用贪心求出小w的最高可能得分，然后再解决字典序最大这个要求。对于这个要求，我们可以从前往后一位一位贪心的解决。对于每一位，我们贪心地选择在不影响最高得分的情况下数字最大的牌。这个问题可以通过二分答案再贪心判定解决。对于每一位先二分这位填什么数字，再对于这个位置之后的位置使用做法2贪心判定即可。

Q：三分法求函数极值

A：

while(l+eps<r){
double mid=l+(r-l)/3.0,midmid=r-(r-l)/3.0;
if(check(mid)>check(midmid)) r=midmid;
else l=mid;
}

Q：

A：三分法.题解

Q：一个最小圆，覆盖n个点

A：随机化random_shuffle

Q：定义f(s,t,k)表示城市s到城市t不经过编号大于k的城市的最短路径长度，求

A：floyd变种

2021.7.6：

Q：广义费马点；

A：模拟退火模板（有错误，模板见code4399）

Q：带权广义费马点；

A：模拟退火模板

Q：农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。

A：二维凸包模板

2021.7.7：

Q：凸包求面积

A：分割为三角形（模板）

Q：一个二维向量(x,y)的权定义为x^2+y^2。已知一个由n个二维向量组成的集合，求该集合的一个子集，使该子集中的向量和的权尽可能大。

A：计算几何；

将向量按极角序排序：

bool cmp(node a,node b){return (a.x==b.x&&a.y==b.y)?0:atan2(a.y,a.x)<atan2(b.y,b.x);}

选择的向量一定是连续的一段，并且一定在同一平面,“平面”指虚线一侧：

用叉积判断，双指针移动加边删边，维护答案

Q：给定平面上 n 个点，求凸包直径。

A：模板；

思想：1.求凸包，2.找到一对初始对蹱点，3.按照某一方向旋转两条切线，直到找到下一对对蹱点，更新答案；

实现：枚举凸包的每一条边，判断最远点

直线旋转很麻烦，实际上求对于每对凸包上每条边，求距离边最远的点的平行直线（= 求三角形的高 = 同底三角形求面积 = 求平行四边形面积 = 叉积的几何意义）

void getmax(){
s[num+1]=s[1];
for(int i=1,j=2;i<=num;++i){
while(cross(s[i],s[j],s[i+1])<cross(s[i],s[j+1],s[i+1])) ++j=j>num?1:j;
ans=max(ans,max(getdis(s[i],s[j]),getdis(s[i+1],s[j])));
}
}

  • code1409【Usaco2006 Oct】Building the Moat护城河的挖掘

Q&A：凸包模板题

Q：一个贪婪的国王要求他的建筑师建一堵墙（图中虚线）围绕他的城堡（图中实线），且墙与城堡之间的距离总不小于一个数L。输入城堡各个节点（图中实线与实线的交点）的坐标和L，要求最小的墙壁周长。

A：求凸包，可证外圈弧形刚好围成一个圆

Q：《墙》的变种（多个建筑物）

A：读题仔细，方法同上

2021.7.8：

Q&A：旋转卡壳模板

Q&A：旋转卡壳模板

2021.7.9：

Q&A：动态凸包模板+离线操作倒序处理

Q&A：决策单调性优化DP

2021.7.11：abc209abcd

2021.7.12：

Q：两个人玩单词接龙，所用单词必须是给定的单词，A说：abcdErd，则B接龙的单词前三个字母应与上一个单词后三个字母相同（e.g:Erdweb），没有单词可说的人输掉比赛，单词可重复使用，A先手，n个询问，给定A的第一个单词，求问谁会赢

A：将单词的前三个、后三个字符分别建成一个点，后面像前面连边

发现：

1.一个没有从它开始的任何有向边的顶点是一个失败的顶点。

2.如果一个顶点的每条有向边都以一个获胜的顶点为终点，那么这个顶点也是一个失败的顶点。

3.如果一个顶点的任何有向边都以一个失败的顶点结束，那么这个顶点就是一个成功的顶点。

4.如果一个顶点不满足上述三个条件中的任何一个，那么它始终是一个循环顶点。

Q：加入若干条直线，询问与某一平行与y轴的直线相交的最远点

A：李超线段树模板 讲解

Q：加入若干条线段，询问与某一平行与y轴的直线相交的最远点

A：李超线段树模板

Q：加入若干条线段，离线操作，询问与某一平行与y轴的直线相交的最远点

A：李超线段树模板

2021.7.13：

Q：Farmer John要带着他的N头奶牛，方便起见编号为1…N，到农业展览会上去，参加每年的达牛秀！他的第i头奶牛重量为wi，才艺水平为ti，两者都是整数。 在到达时，Farmer John就被今年达牛秀的新规则吓到了：

（一）参加比赛的一组奶牛必须总重量至少为W（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛）

（二）总才艺值与总重量的比值最大的一组获得胜利。

FJ注意到他的所有奶牛的总重量不小于W，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

A：背包DP+01分规;

Q：一棵树n个点中选择k个点，选择一个点必须选择其父亲，求招募费用/战斗值(01分规式子)

A：01分数规划+树形DP

2021.7.14：

Q&A：最优比率生成树（01分规应用）

Q：某地方有N个工厂，有N-1条路连接它们，且它们两两都可达。每个工厂都有一个产量值和一个污染值。现在工厂要进行规划，拆除其中的M个工厂，使得剩下的工厂依然连成一片且 总产量/总污染 的值最大。

A：类似于【JSOI2016】最佳团体（树形DP）

Q：n个礼物有各自的美观度，选择连续的一段（L<=len<=R），求(max（i,j)-min(i,j))/(j-i+k)最大值（k是给定常数）

A：01分规+单调队列；

两种情况：1.区间max，min跨度小于L，则另区间长度为L，单调队列维护min，max；

2.区间max，min跨度L，以R为限制，01规划二分答案；

题解 · 详

Q：最优比率环

A：01分规二分答案后转化为spfa判负环

2021.7.15：

Q&A：wqs二分+斜率优化

Q：小澳的梦境中出现了一个平面直角坐标系，自原点，向四方无限延伸。

小澳在坐标系的原点，他可以向上、向左或者向右走。他可以走n步，但不能经过相同的点。

小澳想知道他有多少种走法。

A：

2021.7.16：

Q：，求第K项

A：矩阵快速幂；

Q&A：类似标数法台阶问题求方案数；矩阵快速幂加速

Q：广义的斐波那契数列是指形如a(n)=p a(n-1)+q a(n-2)的数列，求第K项

A：DP+矩阵快速幂

Q：限定长度为K，求有多少个由0,1组成字符串不包含子串101,111。

A：两种方法

正解是矩阵快速幂DP，也可以：找规律，发现斐波那契数列，再乱搞

2021.7.17：

Q：

A：从后向前贪心选择；越后面的点代价越高，所以从后往前，选择的点尽量靠前，直到非选不可时再选择。

所以从右往左枚举，维护一个票数差的最大值，并且在临界处再买

假设从i+1到N的任意区间都已经合法，那么判断i加入后是否合法，只需要判断i至j是否合法即可（i<=j<=N），所以只需要维护一个后缀和，用sum[i]-sum[j+1]即可算出区间的差值，sum[i]不变，所以只需要保存后缀和中的最小值即可。

程序实现维护后缀最大值

2021.7.18：

2021.7.19：

Q：对一棵n个节点带边权的树，进行两种操作：1.向节点u空头零食，使得其余每个节点v权值增加v~u的路径长度；2.询问当前城市u的权值

A：首先套路树剖；预处理每个节点到根节点的边权前缀和，然后将修改操作差分；修改和查询操作：

void change(int x){//tot：修改总次数
++tot,Sum+=dis[x];
while(top[x]) modify(1,1,n,num[top[x]],num[x],1),x=fa[top[x]];
}
int ask(int x){
int ans=Sum+tot*dis[x];
while(top[x]) ans-=2*query(1,1,n,num[top[x]],num[x]),x=fa[top[x]];
return ans;
}

Q：给定一个线性方程组，对其求解

A：模板：消元成上三角+回带

2021.7.20：

Q：

A：拆点，将点与点间的边权变为一，用矩阵快速幂优化，g[i][j]^n表示走n步走到点（i，j）的方案数；详细题解

scanf("%d%d",&n,&t),--t;
for(int i=1;i<=n;++i){
for(int j=1;j<=8;++j) a.f[i+j*n][i+(j-1)*n]=1;
char tmp[13];scanf("%s",tmp+1);
for(int j=1;j<=n;++j) if(tmp[j]) a.f[i][j+n*(tmp[j]-'1')]=1;
}
jz=a;
while(t){if(t&1) a=qpow(a,jz);t>>=1,jz=qpow(jz,jz);}
cout<<a.f[1][n]<<'\n';
return 0;

2021.7.21：

Q：给定一个连通图；同时，有m条食人鱼按不同周期T（T=2或3或4）在几个节点间游动，任何时刻不能和食人鱼在同一节点，也不能不走，求用k步从起点走到终点，可重复经过同一点的方案数；

A：若没有食人鱼，则是普通矩乘，有了食人鱼，将矩阵食人鱼所在行和列赋值为零，发现gcd(2,3,4)=12，故将12作为一个周期，快速幂优化；

scanf("%d%d%d%d%d",&n,&m,&S,&E,&k);
for(int i=1,u,v; i<=m; ++i) scanf("%d%d",&u,&v),dis.f[u][v]=dis.f[v][u]=1;
scanf("%d",&m);
for(int i=1; i<=m; ++i) for(int j=(scanf("%d",&kp[i][0]),1); j<=kp[i][0]; ++j) scanf("%d",&kp[i][j]);
for(int i=1; i<=12; ++i) {
a[i]=dis;
for(int j=1; j<=m; ++j) {
int tmp=(i-1)%kp[j][0]+1,x=kp[j][tmp],y=kp[j][tmp%kp[j][0]+1];
for(int p=0; p<n; ++p) a[i].f[x][p]=a[i].f[p][y]=0;
}
}
for(int i=0; i<n; ++i) jz.f[i][i]=ans.f[i][i]=1;
for(int i=1; i<=12; ++i) jz=qpow(jz,a[i]);
for(int i=k/12; i; i>>=1,jz=qpow(jz,jz)) if(i&1) ans=qpow(ans,jz);
for(int i=1; i<=k%12; ++i) ans=qpow(ans,a[i]);
cout<<ans.f[S][E]<<'\n';
return 0;

Q：一个n* m的矩阵，选择两个不同点建车站，代价为两个点的点权+两点曼哈顿距离

A：

! 从左至右，右至左跑两便；乱搞排序做法可过

2021.7.22：

2021.7.23：

Q：给你一个n维球体上的n+1个点的坐标，询问球心坐标

A：多维高斯消元模板；

除了球心坐标，未知数还有半径r，

详细题解

2021.7.24：

2021.7.25：

Q:给定一个字符串S，按顺序选择8个字母拼接成“chokudai”，求字母选择的方案数。

A：dp；设dp[i][j]为当前选到S的第i个字符，已匹配chokudai的第j个字符。

Q：给定一个n* m（n,m<8）的图，有些点可以选择，从可选点中选择k个点染色，使染色的点形成一个连通块，问有多少种选法。

A：dfs，看题解（个人TLE）

Q：给你n个多边形，每条边平行于坐标轴，q个询问，每次询问覆盖一个点的多边形个数。

A：将多边形拆成平行于y轴的线段，问题转化为区修单查。

不知道为什么写挂了

2021.7.26：noi同步赛day1

2021.7.27：

Q：平面直角坐标系上给定n个矩形障碍物（边平行于坐标轴），求从（0，0）到（x，0）最短距离（不可穿越矩形，可走矩形边界）。

A：小模板+set使用；解决了历史遗留问题。

将矩形转化为线段，用set维护（遇见障碍物即分叉）；如图：

2021.8.16：（其余见数论专版）

Q：n 名男同学，m 名女同学和两名老师要排成一条直线，并且任意两名女同学不能相邻，两名老师也不能相邻，输出一共有多少种排法？

A：高精+排列组合，插空法+捆绑法；不管两名老师限制排列数量-捆绑老师（一定不合法）排列的数量：

\left( n+2\right) !\cdot C_{n+3}^{m}\cdot A_{m}^{m}-\left( n+1\right) !\cdot 2\cdot C_{n+2}^{m}\cdot A_{m}^{m}

2021.8.17：

Q：本题有两种操作，每个测试点多组数据。

第一种：求 1~N 的一个给定全排列在所有 1~N 全排列中的排名。结果对 998244353 取模。

第二种：求 1~N 中排名为 rk 的全排列。

A：康托展开：X=a_{n}\left( n-1\right) !+a_{n-1}\cdot \left( n-2\right) !+\ldots +a_{1}\cdot 0!

逆康托展开：

康托展开用树状数组；逆康托两种写法：权值线段树/vector（询问的rk在long long范围内）

//VECTOR版本
vector<int>v;
void contor(){
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
int ans=1,f=1;memset(c,0,sizeof(c));
for(int i=n;i;--i) ans=(ans+1ll*ask(a[i])*f%mod)%mod,add(a[i],1),f=f*(n-i+1)%mod;
cout<<ans<<'\n';
}
void revcontor(){
scanf("%lld",&k),--k;
int i,f[23]={1,1};for(i=2;i<=20;++i) f[i]=f[i-1]*i;
for(i=1;i<=n&&n-i>20;++i) cout<<i<<' ';
for(int j=i;j<=n;++j) v.push_back(j);
for(int j=i,t;j<=n;++j) t=k/f[n-j],cout<<v[t]<<' ',v.erase(v.begin()+t),k%=f[n-j];
puts("");
}
//权值线段树版本
void build(int x,int lef,int rig){
if(lef==rig) return siz[x]=1,void();
int mid=lef+rig>>1;
build(x<<1,lef,mid),build(x<<1|1,mid+1,rig);
siz[x]=siz[x<<1]+siz[x<<1|1];
}
void ask(int x,int lef,int rig,int k){
--siz[x];
if(lef==rig) return cout<<lef<<' ',void();
int mid=lef+rig>>1;
siz[x<<1]>=k?ask(x<<1,lef,mid,k):ask(x<<1|1,mid+1,rig,k-siz[x<<1]);
siz[x]=siz[x<<1]+siz[x<<1|1];
}
void revcontor(){
scanf("%lld",&k);
build(1,1,n);--k;
for(int i=1,t;i<=n;++i){
if(n-i>20) ask(1,1,n,1);
else t=k/f2[n-i],ask(1,1,n,t+1),k%=f2[n-i];
}
puts("");
}

Q：

A：康托展开；难点：要求的逆康托rk超出long long范围。

改进：不用hash 乘 n！，使用数组存储，其他一样。

Q&A：康托展开模板

暴力；next_permutation(p+1,p+n+1);下一个排列函数

Q：n个位置，有m棵幼苗，要求两颗幼苗之间至少有一个空位，求摆放方案数。

A：

2021.8.18：

Q：

A：暴力枚举：ans=位数比它小的所有合法数量+算出每一位比它小的数量。仔细读题！！！

Q：

A：好题解

从本质上说，就是该图的最短路是确定的，都是沿着矩形外围一圈走，且一开始先走矩形长的一边。

M+\begin{pmatrix} m \\ 1 \end{pmatrix}+\begin{pmatrix} m+1 \\ 2 \end{pmatrix}+\ldots +\begin{pmatrix} m+n-2 \\ n-1 \end{pmatrix}

  • 帕斯卡公式/杨辉三角求组合数及变形：

对于\forall 1\leq k\leq n-1有：\begin{pmatrix} n \\ k \end{pmatrix}=\begin{pmatrix} n-1 \\ k \end{pmatrix}+\begin{pmatrix} n-1 \\ k-1 \end{pmatrix}

推论1（上指标求和）：\sum ^{n}_{i=k}\begin{pmatrix} i \\ k \end{pmatrix}=\begin{pmatrix} n+1 \\ k+1 \end{pmatrix}

推论2：\sum ^{m}_{i=1}\begin{pmatrix} i+n \\ i \end{pmatrix}=\begin{pmatrix} n+m+1 \\ n \end{pmatrix}-1

定理：\sum ^{n}_{i=0}\begin{pmatrix} n \\ i \end{pmatrix}=2^{n}

推论：\sum ^{n}_{i=0}\dfrac{\begin{pmatrix} n \\ i \end{pmatrix}}{i+1}=\dfrac{2^{n+1}-1}{n+1}

上指标反转（负数组合数）：\begin{pmatrix} n \\ m \end{pmatrix}=\left( -1\right) ^{m}\begin{pmatrix} m-n-1 \\ m \end{pmatrix}

其余指标运算：\begin{pmatrix} n \\ m \end{pmatrix}\begin{pmatrix} m \\ r \end{pmatrix}=\begin{pmatrix} n-r \\ m-r \end{pmatrix}\begin{pmatrix} n \\ r \end{pmatrix}

Q：监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

A：总方案数-相邻房间宗教互不相同数量：M^{n}-M\cdot \left( M-1\right) ^{n-1}

Q：

A：组合数DP，很妙；两种方法：

正解（组合数DP）：

另一个很妙的做法：

2021.8.19：

Q：

A：水题；隔板法；

Q：

A：二项式定理版题；

Q：

A：二项式定理结论题，ans=2^(n-1)。

Q：给出 1 个长度为 n 的序列，以及 1 个正整数 m。问这个原序列中是否存在非空子序列，使其元素之和能被 m 整除。

A：抽屉原理，n>=m则一定存在，否则背包DP；

for(int i=1,x;i<=n;++i){
scanf("%d",&x),x%=m,f[i&1][x]=1;
for(int j=0;j<m;++j){
f[i&1][j]|=f[1-(i&1)][j];
f[i&1][(j+x)%m]|=f[1-(i&1)][j];
}
ans|=f[i&1][0];
}

Q&A：抽屉原理；

Q：

A：总方案数-不合法方案数。

2021.8.21：（补lucas定理）

Q：给定N,P,K,R，求\left( \sum ^{\infty }_{i=0}C_{nk}^{ik+r}\right) mod p

A：

2021.8.23：

Q：给你一个长为N的数组A，求所有 k\in \left[ 1,M\right] 满足 \gcd \left( k,a_{i}\right) =1

A：类似sieve，求出A[i]的所有质因数，再筛掉它们的倍数。

for(int i=1,x;i<=n;++i){
scanf("%d",&x);
for(int j=2;j*j<=x;++j) if(x%j==0){
while(x%j==0) x/=j;
if(!vis[j]) for(int k=j;k<=m;k+=j) vis[k]=1;
}
if(x>1&&!vis[x]) for(int j=x;j<=m;j+=x) vis[j]=1;
}

Q：给你m则形如A>B的条件，求满足该条件的n个数的排名，有多种方法则输出字典序最小。

A：拓扑序+优先队列

Q：X先生来到了一个奇怪的国家旅行。这个国家有N个城市，每个城市均有且仅有一个机场，但是这机场所有航班只飞往一个城市。每个城市有一个游览价值，第i个城市的游览价值为A[i]。

现在他想知道，从第i个城市出发，并只坐飞机飞往下一个城市，游览价值之和最多是多少（一个城市游览多次只计算1次游览价值）

A：Tarjan缩点+拓扑序；

//复习Tarjan（校园网）
void tarjan(int x){
low[x]=dfn[x]=++cnt,vis[x]=1,stack[++index]=x;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
else if(vis[v]) low[x]=min(low[x],low[v]);
}
if(low[x]==dfn[x]) for(++num;stack[index+1]!=x;--index) vis[stack[index]]=0,bel[stack[index]]=num;
}

2021.8.24：

Q：给定一个有向无环图，每个点的权值为：C_{i}=\sum _{j,i,\in E}W_{j,i}C_{j}-U_{i}，j表示指向i的节点，若一个节点的权值大于0，则会向下一个节点传递C[j]，否则不传递。给定初始节点（没有入度）的权值，求结束节点的权值（没有出度）

A：拓扑序，push时判断一下正负即可。

  • CF1385E Directing Edges

Q：给定一个由有向边与无向边组成的图，现在需要你把所有的无向边变成有向边，使得形成的图中没有环。

如果可以做到请输出该图，否则直接输出"NO"。

A：有解情况：拓扑序的性质：所有有向边一定是拓扑序小的指向大的，以此来定无向边的方向，有向边直接输出就行了。

当且仅当一遍拓扑图跑完push的数量！=n 时无解。

Q&A：同上（CF1385E Directing Edges）

Q：给你一个有向无环图，规定一个节点“死亡”当且仅当指向它的节点全部“死亡”。一个节点的“灾难值”定义为：当前节点死亡后跟随它“死亡”的节点个数，输出1~n每个节点的灾难值。

A：把图拆成树，发现使得某个点死亡，需要它的所有父亲节点死亡，即它父亲节点的LCA死亡，以此在拓扑序更新节点时跑LCA。

直接把点挂在LCA上，此时节点的灾难值即为其子树的大小。

while(!q.empty()){
int x=q.front();q.pop();
g[pre[x]].push_back(x),fa[x][0]=pre[x],dep[x]=dep[pre[x]]+1;
for(int i=1;i<=16;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
pre[v]=pre[v]?getlca(pre[v],x):x;
if(!--r[v]) q.push(v);
}
}

Q：给定一个N个点M条边的有向无环图，每条边长度都是1。请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。

A：正反两遍拓扑序+DP求出以某个点为 起点/终点 的最长路径长度;然后考虑删点问题：

struct node{
priority_queue<int>a,b;
void push(int x){a.push(x);}
void pop(int x){b.push(x);}
int top(){while(!b.empty()&&a.top()==b.top()) a.pop(),b.pop();return a.top();}
}hp;//手写可删堆模板
int main()
{
n=read(),m=read();
for(int i=1,u,v;i<=m;++i) u=read(),v=read(),e[u].push_back(v),re[v].push_back(u),++r[v];
for(int i=1;i<=n;++i) if(!r[i]) q.push(i);
while(!q.empty()){
int x=q.front();q.pop(); tp[++cnt]=x;
for(int i=0;i<e[x].size();++i) if(!--r[e[x][i]]) q.push(e[x][i]);
}
for(int j=1;j<=n;++j)
for(int i=0,x=tp[j];i<e[x].size();++i) dt[e[x][i]]=max(dt[e[x][i]],dt[x]+1);
for(int j=n;j;--j)
for(int i=0,x=tp[j];i<re[x].size();++i) ds[re[x][i]]=max(ds[re[x][i]],ds[x]+1);
for(int i=1;i<=n;++i) hp.push(ds[i]);
ans=hp.top();
for(int j=1;j<=n;++j){
int x=tp[j];hp.pop(ds[x]);
for(int i=0;i<re[x].size();++i) hp.pop(dt[re[x][i]]+ds[x]+1);
if(hp.top()<=ans) ans=hp.top(),id=x;
for(int i=0;i<e[x].size();++i) hp.push(dt[x]+ds[e[x][i]]+1);
hp.push(dt[x]);
}
cout<<ans<<'\n';
return 0;
}

Q&A：

关于此题容斥原理的解释

2021.8.25：

Q&A：SPFA跑负边权最短路。

Q：定义十进制表示中只包含数字6和8的号码是幸运号码，比如68，666，888；又规定凡是“幸运号码”的倍数都是“近似幸运号码”。询问一段闭区间[a, b]内，“近似幸运号码”和“幸运号码”的总个数。

1<=a<=b<=10000000000

A：容斥原理；

Q&A：类似上题《幸运数字》

Q：一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次；每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

A：先不考虑硬币个数的限制，即完全背包选择的方案数，再减去不合法方案数，发现有一种硬币超出限制就不合法；

用类似前缀和的思想（术语叫差分），我们先完全背包预处理好无限制的情况，拿dp[tot]减去dp[tot-c[i]*(d[i]+1)]就是我们所需的方案数。

for(int i=0;i<=15;++i){//C[]：价值；D[]：限制的数量 
int tmp=s,cnt=0;
for(int j=1;j<=4;++j) if((i>>j-1)&1) tmp-=c[j]*(d[j]+1),cnt^=1;
if(tmp>=0) ans+=f[tmp]*(cnt?-1:1);
}

2021.8.26：（其余见数论专版）

Q：给出一个长度为 n 的序列 A。如果序列 A 不是非降的，你必须从中删去一个数，重复这一操作，直到 A 非降为止。求有多少种不同的操作方案，答案模 10^9 + 7。

A：

Q：求有多少长度为 n 的序列 A，满足以下条件：

　　·1～n 这 n 个数在序列中各出现了一次

　　·若第 i 个数 A[i]的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的

A：错排问题

2021.8.27/28：（见数论专版）

2021.8.30：

Q：给你一个长为 N 的序列 A，输出所有的正整数 K 小于等于 M，满足 gcd(A[i]，K)==1。

A：类似sieve，将输入的每个数分解质因数，筛掉质因数的倍数。

Q：给定一个长为N的字符串，选择任意多个位置（不能为0）组成一个新的字符串，满足相同字符相邻的选择方法有多少种？

1≤N≤1000，字符集≤10

A：状压DP；dp[选到第i个字符][迄今选了的字符集][最后选择的字符]={可能的组合数}

for(int i=1;i<=n;++i){
int x=tmp[i]-'A'; f[i][1<<x][x]=1;
for(int j=0;j<1024;++j){
for(int k=0;k<10;++k){
f[i][j][k]+=f[i-1][j][k];//字符集相同，不选i位置 
if(x==k) f[i][j][k]+=f[i-1][j][k];//字符相同，选择该位置不影响字符集 
f[i][j][k]%=mod;
}
if(!(j&1<<x))//字符集不同，一种新的字符 
for(int k=0;k<10;++k) f[i][j|(1<<x)][x]=(f[i][j|(1<<x)][x]+f[i-1][j][k])%mod;
}
}

Q：给你n个坐标，两坐标的距离定义为：min(x_i-x_j,y_i-y_j),求距离最大的两点的距离。

A：将 n 个点排序，考虑二分 k 值，要满足题目条件，就要满足x_i-x_j>=k 且 y_i-y_j>=k。

//二分check函数
bool check(int k){
for(int i=1,j=1,mn=a[1].y,mx=a[1].y;i<=n;++i){
while(j+1<=n&&a[j+1].x+k<=a[i].x) ++j,mn=min(mn,a[j].y),mx=max(mx,a[j].y);
if(a[j].x+k<=a[i].x&&(mn+k<=a[i].y||mx-k>=a[i].y)) return 1;
}return 0;
}