2021-XDU-寒假训练
（一）
A
B
字符串上做快速幂优化的dp
C 三维平面上求最长的基底长度
弱化：二维平面上求最长的基底长度
如何说明gcd欧几里得算法的正确性？等价于说明$gcd(a, b) = gcd(b, a % b)$：
只要说明(a, b)的公因子一定是a%b的因子，(b, a % b)的公因子一定是a的因子。这样，双方的公因子全体必然相同，进而gcd相等。
那么，在一般的欧几里得算法中，必须要证明上述的式子，即$fun(a, b) = fun(b, a%b)$
高斯整数是实部与虚部均为整数的复数。首先如下地定义高斯整数的唯一带余除法表示：
设$\frac{a}{b} = x + iy$, 一定存在唯一的整数$m, n$使得$m - 1/2 < x <=m + 1/2, n-1/2 < y <=n + 1/2$.
那么带余除法$a = bq +r, q =m+in$.
实际在运算时，对两个复数做除法，将实部虚部四舍五入，就得到了倍数q。
接下来尝试说明上述的除法满足欧几里得算法的条件：
仍然认为这里的$fun$函数是找二者最大的公因子。
由于$<C, +, *>$是环，乘法对加法可分配，运算满足封闭性，很容易证明两边的因子全体相同。
（手算证明a、b的因子一定是a%b的因子，大概利用了上述的几个性质，不知道是否正确）
那么通过欧几里得不断辗转相除就可以得到给出的所有向量的最大公因子。
得出的这个"Gcd"因子，就是我们要求的最终的基底向量。无需考虑转化为平面坐标上的基底，直接利用这个向量就可以得知需要几个向量才能构成一个题目要求的"正方形"：将给出的所有向量除以该基底，按道理可以得到标准的高斯整数，实部可以看作是为了表示这个向量，实轴基底所需要的数量，虚部可以看作是虚轴基底所需要的数量。不断地用横纵坐标更新最大最小值，最后在这个矩形区域中最长的边（即长方形的长），这就是为了表示所有的复数所需要的最少的基底数量，也就是题目要求中的K。显然，因为基底最大，相应的K就会最小。
此外，因为题目还允许变化基础偏移值$(a, b)$，所以给出的n个复数不需要全部使用，可以认为某一个为原点，考虑剩余$n-1$个对它的相对坐标，使用相对坐标完成上述讨论的gcd等操作即可。
因为看到了一份代码，在gcd中有四舍五入，而在将向量除以标准基底后得到的商上也进行了四舍五入，让人不禁怀疑这一坨四舍五入到底都是什么。事实上，gcd的四舍五入是高斯整数除法所内在要求的，而商上的四舍五入是为了防止double复数除法的精度问题。
此时不禁赞叹这一份优美的自定义高斯整数结构的代码。（可能需要coach才能查看）
1
2struct GaussianInteger{
3 ll x, y;
4 ll norm(){return x * x + y * y;}
5 GaussianInteger operator + (const GaussianInteger &b){
6 return {x + b.x, y + b.y};
7 }
8 GaussianInteger operator - (const GaussianInteger &b){
9 return {x - b.x, y - b.y};
10 }
11 GaussianInteger operator * (const GaussianInteger &b){
12 return {x * b.x - y * b.y, x * b.y + y * b.x};
13 }
14 //(专用! 因为此处b保证大于0)四舍五入除法
15 //高斯整数商的实部虚部在某个整数的**(-1/2, 1/2]**区间中。
16 ll D(ll a, ll b){
17 if(a >= 0) return (a % b) * 2 < b? a / b: a / b + 1;
18 a = -a; return -((a % b) * 2 <= b? a / b: a / b + 1);
19 }
20 GaussianInteger operator / (const GaussianInteger &b){
21 return {D(x * b.x + y * b.y, x * b.x + y * b.y), D(y * b.x - x * b.y, x * b.x + y * b.y)};
22 }
23 GaussianInteger operator % (const GaussianInteger &b){
24 GaussianInteger a = {x, y};
25 return a - a / b * b;
26 }
27};
28typedef GaussianInteger NODE;
29NODE gcd(NODE a, NODE b){return !b.norm()? a: gcd(b, a % b);}
30
31
32const int maxn = 1e5 + 10;
33NODE node[maxn];
34
35ll xmi, xmx, ymi, ymx;
36
37int main() {
38 Fastin;
39 int n; scanf("%d", &n);
40 for(int i = 0; i < n; i++) scnaf("%lld %lld", &node[i].x, &node[i].y);
41 for(int i = 1; i < n; i++) node[i] = node[i] - node[0];
42 NODE d = node[1];
43 for(int i = 2; i < n; i++) d = gcd(d, node[i]);
44 for(int i = 1; i < n; i++){
45 NODE p = node[i] / d;
46 xmi = min(xmi, p.x); xmx = max(xmx, p.x);
47 ymi = min(ymi, p.y); ymx = max(ymx, p.y);
48 }
49 ll ans = max(ymx - ymi + 1, xmx - xmi + 1);
50 printf("%lld\n", ans - n);
51 return 0;
52}三维空间上利用四元数（留坑）
暂时不太愿意花费太多时间去研究四元数的若干表示形式 因而留坑待补（弃坑（bushi
D 无向图生成树计数 & 允许旋转置换
无向图矩阵树定理
图中不允许自环，允许重边。
定理基尔霍夫矩阵$L(G) = D(G)-A(G)$，度数矩阵$D_{ii}(G) =deg(i),D_{ij}=0,i≠j$，邻接矩阵$A_{ij}(G)=A_{ji}(G)=#e(ij), i≠j$。
那么$L(G)$的所有代数余子式均相同，且等于G的生成树数量。
Burnside与Polya定理
burnside：G是X的置换群，C是X中满足如下条件的着色集合：对于G中所有的f和C中所有的c都有$f*c$仍在C中，则C中非等价的着色数$N(G,C)=\frac{1}{|G|}\sum _{f∈G}|C(f)|$，其中$C(f)$是在f作用下使得着色c保持不变的所有着色的集合。
polya: 如果一个置换$f$有$σ_f$个循环，那么可以根据循环具体地计算出不动点的数量，从而得到等价类的数量: $\frac 1 {|G|}\sum_ {f∈G}m^{σ_f}$，其中m是可选颜色的数量。
polya练习题-> 这里
E 杨表 & LIS
Diworth定理
一个序列中下降子序列的最少划分数个数等于最长上升子序列的长度。
一个序列中上升子序列的最少划分数个数等于最长下降子序列的长度。
每句中的前后两者互为偏序关系。
杨表
标准杨表从左向右、从上到下格子中的元素大小均是递增的。
大概长阶梯状，但是博客比较垃圾不太能上传图所以从略
$1-n$构成杨表个数为$f(1) = 1, f(2)=2, f(n) = f(n-1)+(n-1)*f(n-2),n >2$
定义某个方格的勾长为该方格正右方方格数+正下方方格数+1，那么如果给定杨表的形状，用$1-n$填充杨表的所有方式有$\frac {n!}{\prod _{x是杨表格子}hook(x)}$，这被称为勾长公式。
杨表的对行插入：设要插入x，从第一行开始，在当前行中找第一个大于x的位置，如果找到了就用x替换该元素y，并尝试在下一行插入y，反复不断进行；如果找不到这样的位置，就将当前的值放在行末，算法结束。
杨表的删除：假设要删除$(x, y)$，保证$(x, y)$是边角。设x = $S_{xy}$，如果x在第一行，删除x算法结束；不然，找出最大的小于x的位置，用x替换该位置上的元素y，再尝试在上一行中删除y，反复进行。
杨表$P_x$与LIS、LDS：
$P_x$中第一行的长度就是排列$X$的LIS的长度，第一列的长度是其LDS的长度
事实上，定义k-LIS序列为LIS长度不超过k的序列，类似地定义k-LDS序列。那么杨表前k列的长度就是最长的k-LIS长度。
本题
给定长度n，要求找出满足如下条件的长为n的排列：存在两个长度相同且无相交元素的LIS，答案对998244353取模。
由于diworth定理，可以得知就是要找包含一个总长为2L，LDS=2，LIS=L的子序列的序列的个数，这也就是说要找长度为n、2_LDS=2L、LIS=L的序列的个数。转换到杨表上来，杨表大小为n，前两行总共应有2L个元素，第一行必须有 L个元素，从而第二行也就必须有L个元素。将整数n进行拆分后用钩子公式即可得知当前形状的杨表的合法数量。又由于一对杨表唯一的确定一个排列，那么最终的排列数则是所有杨表合法数量的平方之和。
- 没有仔细研读2019国家集训队论文集，偷了几个结论就跑了
- 不是特别明白利用diworth定理和杨表相关性质对题目进行的转化
1onst int M = 998244353;
2const itn maxn = 1e2 + 10;
3int n, l;
4int a[maxn];
5ll ans = 0, pre[maxn], inv[maxn];
6ll fun(int x, int y){
7 return !x? inv[y]: inv[y] * pre[x - 1] % M;
8}
9//将要放第k层,上限为x，剩余sum个格子
10void dfs(int k, int x, int sum){
11 if(sum == 0){
12 //对第i层而言，显然有i-1个上方的格子，右边的格子分别为0,1,...,a[i] - 1
13 //i * (i + 1) * ... * (i + a[i] - 1)
14 ll res = pre[n];
15 for(int i = 0; i < k; i++){
16 res *= fun(i, i + a[i] - 1);
17 res %= M;
18 }
19 ans += res; asn %= M;
20 prt(a, k, 1);
21 return ;
22 }
23 for(int i = 1; i <= sum && i <= x; i++){
24 a[k] = i;
25 dfs(k + 1, i, sum - i);
26 }
27}
28
29int main(){
30 // Fastin;
31 int n; scanf("%d", &n);
32 pre[0] = 1; inv[0] = 1;
33 for(int i = 1; i < 100; i++){
34 pre[i] = pre[i - 1] * 1ll * i % M;
35 inv[i] = qp(pre[i], M - 2, M);
36 }
37
38 for(int i = 1; i + i <= n; i++){
39 a[0] = a[1] = i; l = i;
40 dfs(2, i, n - 2 * i);
41 printf("%lld\n", ans);
42 }
43 return 0;
44}K 可持久化01线段树
支持区间翻转，单点置值。每次操作完后输出整个序列中1的个数。
貌似可持久化线段树不是很能支持直接的区间操作？
在这道题中，如果出现区间翻转的操作，那么将所有有关的小线段都打上tag（实际是异或加1），并将他们的结果都用$r - l + 1 - st[p]$来代替本身；而如果出现了单点置值的情况，检查一路上遇到的所有的线段的tag，将将要置的值x不断地异或上这些tag，以最终的结果作为最终要置的值。这是因为，在一个已经翻转过的线段上置值（然而此时只是对这个大线段打了tag，没有实际地修改子线段，不然会T）等价于将要置的值先翻转，不断往下走，置好后再将$st[ls] + st[rs]$的值翻转一遍后置回本身。
需要注意的是，这里的翻转tag必须要在相邻的版本之间进行继承！不然就会发生翻转信息遗漏的问题。
对于01串的区间翻转问题，这种将要置的值翻转的手段好像是一个比较通用的手法？值得学习。
1#define mid ((l + r) >> 1)
2
3const int maxn = 2e7 + 10;
4int n, m, q;
5
6int root[100010], version = 0;
7int st[manx], tag[maxn];
8int ls[maxn], rs[maxn], top = 1;
9
10int build(int l, int r){
11 int now = top++;
12 if(l == r) return now;
13 ls[now] = build(l, mid);
14 rs[now] = build(mid + 1, r);
15 return now;
16}
17
18void up(int p, int l, int r){
19 st[p] = st[ls[p]] + st[rs[p]];
20 if(tag[p]) st[p] = r - l + 1 - st[p];
21}
22int set(int p, int l, int r, int k, int x){
23 int now = top++;
24 tag[now] = tag[p];
25 if(l == r && l == k){
26 st[now] = x;
27 return now;
28 }
29 x ^= tag[p];
30 ls[now] = ls[p]; rs[now] = rs[p];
31 if(k <= mid) ls[now] = set(ls[p], l, mid, k, x);
32 else rs[now] = set(rs[p], mid + 1, r, k, x);
33 up(now, l, r);
34 return now;
35}
36
37int update(int p, int l, int r, int L, int R){
38 int now = top++;
39 ls[now] = ls[p]; rs[now] = rs[p];
40 tag[now] = tag[p];
41 if(L <= l && r <= R){
42 st[now] = r - l + 1 - st[p];
43 tag[now] ^= 1;
44 return now;
45 }
46 if(L <= mid) ls[now] = update(ls[p], l, mid, L, R);
47 if(R > mid) rs[now] = update(rs[p], mid + 1, r, L, R);
48 up(now, l, r);
49 return now;
50}
51
52
53int main() {
54// Fastin;
55 scanf("%d %d %d", &n, &m, &q);
56 root[version++] = build(0, n * m - 1);
57
58 for(int i = 0; i < q; i++){
59 int op; scanf("%d", &op);
60 if(op == 1){
61 int i, j; scanf("%d %d", &i, &j); i--; j--;
62 root[version] = set(root[version - 1], 0, n * m - 1, i * m + j, 1);
63 version++;
64 }
65 else if(op == 2){
66 int i, j; scanf("%d %d", &i, &j); i--; j--;
67 root[version] = set(root[version - 1], 0, n * m - 1, i * m + j, 0);
68 version++;
69 }
70 else if(op == 3){
71 int i; scanf("%d", &i);
72 root[version] = update(root[version - 1], 0, n * m - 1, (i - 1) * m, i * m - 1);
73 version++;
74 }
75 else{
76 int x; scanf("%d", &x);
77 root[version] = root[x];
78 version++;
79 }
80 printf("%d\n", st[root[version - 1]]);
81 }
82 return 0;
83}