记$edge\left \{ u,v,capacity,cost \right \}$为一条从u 到v 的，流量为cap 的，费用为cost 的弧与反弧
源点向每个房间连边$edge\left \{ S,x,1 \right \}$
每道菜向汇点连边$edge\left \{ x+n*2+p,T,1 \right \}$
每个人拆成两个用，x+p 与房间连边，x+p+n 与菜连边
当第k 个人喜欢第x 个房间，连边$edge\left \{ x,k+p,1 \right \}$
当第k 个人喜欢第x 道菜，连边$edge\left \{ k+n+p,x+n*2+p,1 \right \}$
跑一边S 到T 的最大流

记$edge\left \{ u,v,capacity,cost \right \}$为一条从u 到v 的，流量为cap 的，费用为cost 的弧与反弧
拆点，对于点x，分为x 和x+n 两点，x 负责流入，x+n 负责流出
对于每个点连边$edge\left \{ x,x+n,1 \right \}$
对于原图每条连接u,v 的边，连边$edge\left \{ u+n,v,INF \right \}$，$edge\left \{ v+n,u,INF \right \}$
跑一边s+n 到t 的最大流
最大流最小割

记E 为Elaxia 的最短路DAG，W 为w 的最短路DAG
根据W 重构E 每条边的权值
对于连接u，v，权值为val的边
当且仅当在W 中$d\left [ u \right ]+val= d\left [ v \right ]$或$d\left [ v \right ]+val= d\left [ u\right ]$时，边权为val，否则为0
在E 上跑一边最长路得出答案

观察到$k\leq 10^{9}< 13!$
对于过大的n，至多只有最后13位会变
对于会变得位置求Cantor展开，然后直接计算

若$ax\equiv 1\left ( mod \ p \right )$，则称x，a 互为mod p 意义下的逆元

1. 扩展欧几里得算法 $$ax\equiv 1\left ( mod \ p \right )\Leftrightarrow ax+py=1$$ 若$gcd\left ( a,p \right )\neq 1$则无解

1
2
3
4
5
6

void exgcd(LL a,LL b,LL &x,LL &y)
{
    if (!b) {x=1,y=0;return;}
    exgcd(b,a%b,y,x);
    y-=a/b*x;	
}

1. 费马小定理
   若p 为质数，则$a^{p}\equiv a\left ( mod \ p \right )$

   $$x\equiv a^{p-2}\left ( mod \ p \right )$$

2. 欧拉定理
   若$gcd\left ( a,p \right )=1$，则$a^{\varphi\left ( p \right )}\equiv 1\left ( mod \ p \right )$

   $$x\equiv a^{\varphi\left ( p \right )-1}\left ( mod \ p \right )$$

3. 线性递推
   设$p=k*i+r$，其中$\left ( r<i,1<i<p \right )$

   $$k*i+r\equiv 0\left ( mod \ p \right )$$

   同时乘上$i^{-1},r^{-1}$，得$k*r^{-1}+i^{-1}\equiv 0\left ( mod \ p \right )$

   $$i^{-1}\equiv k*r^{-1}\left ( mod \ p \right )$$ $$i^{-1}\equiv \left \lfloor \frac{p}{i} \right \rfloor*\left [p\mod i \right ]^{-1}\left ( mod \ p \right )$$

数据不大直接上莫队

题目描述
给出一个n个点的树，其中1为根节点
有m次操作，每次给以a为节点的子树中深度为d的节点+v

用一个桶$cnt\left [ d \right ]$记录深度为d 的节点要加的值，一遍dfs即可

题目描述
给出n个点，m条边
每个点有一个权值w，和衰减速度v，每走1单位的路衰减v
保证最优取法所有点权值均大于0

用$dp\left [i \right ]\left [ s \right ]$记录最小衰减值，其中i 为当前点位置，s 为当前状态

其中$d\left [ i \right ]\left [ j\right ]$为i 到j 的距离，可以用Floyd 处理

题目描述
给出一个n*m的矩阵，矩阵中有A和Q两种字符
求有多少个子矩阵，矩阵的四个角选出三个能构成QAQ

记A为1，Q为0，当且仅当矩阵四个角和为1或2满足条件
剩下的做法和之前的洛谷P3941 入阵曲（传送门）差不多

题目描述
nodgd的粉丝太多了，每天都会有很多人排队要签名。
今天有n个人排队，每个人的身高都是一个整数，且互不相同。很不巧，nodgd今天去忙别的事情去了，就只好让这些粉丝们明天再来。同时nodgd提出了一个要求，每个人都要记住自己前面与多少个比自己高的人，以便于明天恢复到今天的顺序。
但是，粉丝们或多或少都是有些失望的，失望使她们晕头转向、神魂颠倒，已经分不清楚哪一边是“前面”了，于是她们可能是记住了前面比自己高的人的个数，也可能是记住了后面比自己高的人的个数，而且他们不知道自己记住的是哪一个方向。
nodgd觉得，即使这样明天也能恢复出一个排队顺序，使得任意一个人的两个方向中至少有一个方向上的比他高的人数和他记住的数字相同。可惜n比较大，显然需要写个程序来解决，nodgd很忙，写程序这种事情就交给你了。

从小到大考虑每个人，对于每个人贪心地考虑位置
用线段树维护，支持求排名和单点修改