1. CF1861F
枚举一个人最优花色是啥，调整可证把这个花色尽可能分配给他更优。然后二分答案，让其他人保证每个花色都要 \(\leq x\)．
再往后是没想到的：可以先考虑一些复杂度较高的做法，比如 flow，左边 \((n-1)\) 个人右边 4 种花色，连边容量是 \(x-a_{i,j}\)，左边点的容量是这个人还要拿多少张牌，右边点的容量是这个花色还剩多少张要分配。满流就 ok。
最大流转最小割，右边只有 4 个点直接状压每个点选不选，然后对于左边每个点就互相独立，可以割掉入边或者割掉所有出边选更小的那个即可。
入边容量是确定的，那么只有 \(x\leq \ ?\) 的时候才会选择割出边，否则选择割入边。排序前缀和二分即可。现在时间复杂度是 \(\mathcal{O}(4\times 2^4\times n\log n\log a)\)．
感觉有点难写。Code
2. CF1864G
一个列操作了之后，这个列上的所有数都必须到自己所在行，反之同理。
两个数的偏移量相同，至少有三次操作对它们进行了操作，挑出同为行/同为列的两个操作，发现这两个操作的 \(\Delta\) 相同；反之如果行列均至少操作一次，并且有两行 \(\Delta\) 相同或者两列 \(\Delta\) 相同那么一定存在两个数偏移量相同。所以存在两个数偏移量相同当且仅当行列均操作至少一次并且存在两行/列 \(\Delta\) 相等。
如果确定了每行的 \(\Delta\) 为 \(r_i\)，列的为 \(c_i\)．如果存在一列没有转动，那么所有的 \(r\) 根据这一列上的元素就能确定具体的值；如果所有列都转动了，此时所有 \(r\) 必须均为 \(0\)，否则一共 \(n\) 列而 \(1\leq c_i<n\) 根据鸽巢就会出现重复。
分析完性质之后尝试转，首先找出所有的合法行和合法列，这里合法定义为还没转过并且转了 \(\Delta>0\) 的偏移量之后所有数都能归位。某个时刻如果同时出现行 \(i\) 和列 \(j\) 合法，考察 \((i,j)\) 这个元素，假设先转完行，如果它需要回到原来位置需要在 \(i+r_i\) 那一列再转一下，此时 \(j\) 和 \(i+r_i\) 这两列的偏移量相同，就不符合条件了。所以必须全都是合法列或者合法行，把它们全都转一下，它们之间顺序可以任意排列所以方案数是个阶乘。模拟下去把阶乘乘起来就行。
3. the 2nd ucup stage1 B
按照花费排序之后是 \(v_1,v_2,\cdots v_k\)，贪心是修改一个后缀的 LCA，枚举 \([i+1,n]\) 后缀的过程中能够维护出后缀中距离 LCA 最远点的距离（最大深度减去 LCA 深度），和 \(v_{i-1}\) 的花费取 \(\min\) 贡献到答案里面。这里出现算错就是后缀里面有一个并没有 chkmin 成功，此时不会更新答案。
4. the 2nd ucup stage1 F / P3513
把图划分成两个点集，一个是团，另一个是独立集。性质是团中点的度数 \(\geq\) 独立集中点的度数。先把一个合法方案构造出来，按照度数从大到小排序贪心把点加到团中然后 check 是否能够凑出一个团，加到不能加为止再 check 剩下的是否为独立集。
唯一的问题就是度数相同时的决策，为什么按照任意顺序加是对的。现在考虑一个合法方案会不会被判成不合法：
假如团的集合是 \(A\)，独立集的集合是 \(B\)，首先有 \(A\) 中度数均 \(\geq |A|-1\)，\(B\) 中度数均 \(\leq |A|\)，那么度数相同只可能是同为 \(|A|\) 或者 \(|A|-1\)。
- 如果是 \(|A|\)，也就是 \(B\) 中存在点只和 \(A\) 中的相连并且都有连边。这样的点最多存在一个，大于一个那么 \(A\) 中的度数就都 \(\geq |A|+1\) 了。此时注意到度数为 \(|A|\) 的点的连边情况都是连向了所有度数 \(\geq |A|\) 的点，那么这些点之间就没有区分自然可以任意顺序加入。
- 如果是 \(|A|-1\)，\(B\) 中的点度数为 \(|A|-1\) 意味着它在 \(A\) 中仅和一个点之间没有连边，而这个点度数就是 \(|A|-1\)，\(A\) 中其它的点度数都 \(\geq |A|\)．此时度数为 \(|A|-1\) 的点连边情况都是连向所有度数 \(\geq |A|\) 的点，那么这些点之间也没有了区分可以任意顺序加入。
5. the 2nd ucup stage2 M
哎，看上去是比较套路应该很快想到题，但是完全没想到容斥，雷暴还是太强了啊啊啊啊/zk
容斥，钦定一些段它就是 \(s\)，那么相当于这样把 \(w\) 生成出来：新拼上一个 \(s\) 然后拼若干个 border，或者拼上任意一个字符。
假设 \([x^i]F(x)\) 为 \(-1\) 当且仅当 \(i\) 是 \(s\) 的一个周期，那么拼上一个 \(s\) 再拼上若干个周期用 gf 表示出来就是 \(-\frac{x^{n}}{1-F(x)}\)，然后拼上若干个字符就是 \(\frac{1}{1-26x}\)，SEQ 一下再取反就是答案（最后一段的连续钦定的最后一次钦定位置是末尾，不需要乘 \(-1\)）
令 \(\frac{x^{n}}{1-F(x)}\cdot \frac{1}{1-26x}=\frac{-x^n}{(1-F(x))(1-26x)}=\frac{P(x)}{Q(x)}\)，答案的 gf 就是 \(\frac{1}{1-\frac{P(x)}{Q(x)}}=\frac{Q(x)}{Q(x)-P(x)}\)，分子分母都是 \(\mathcal{O}(n)\) 项的多项式，求 \([x^m]\)，是一个线性递推，然后学习了一下 bostan-mori \(\mathcal{O}(n\log n\log m)\) 解决。
5. the 2nd ucup stage2 K
模拟费用流，因为费用流每次是跑最短路增广，所以只需要维护右侧 \(k\) 个点之间的最短路。对于左侧每个点会给右侧带来 \(k\) 条边，然而两点之间只有最小的那一条是有用的。所以对每个点对用一个堆维护之间连边的边权，只对每个堆堆顶以一共 \(\mathcal{O}(k^2)\) 条边跑最短路，增广之后最多改变 \(\mathcal{O}(k)\) 个左部点的匹配，再对堆进行修改即可。复杂度 \(\mathcal{O}(nk^2\log k)\)（如果我没算错的话）．
6. 2nd ucup stage 2 H
本来以为是构造题，看到题解才意识到标题是关键信息（
其实是让我们构造一个静态区间半群信息查询的一个结构，上个 Sqrt Tree 就行了。
7. C. 23zr提高day4雁河菊【爆标】
桶排，\(a_i\) 先和 \(i\) 取个 \(\min\)，现在要求是操作使得 \(a_1=1,a_i\leq a_{i-1}+1\)，令 \(b_i=a_i-i\) 那么限制变成 \(b_1=0,b_i\leq b_{i-1}\)，也就是把 \(b\) 操作成不升的序列。
这里结论是不管 \(b_1=0\) 求出的答案和限制 \(b_1=0\) 是一样的，也就是一定存在最优解使得 \(b_1=0\)．
由于最开始 \(a_i\) 和 \(i\) 取 \(\min\) 了，那么 \(b_i\leq 0\)，所以 \(b_1\) 不会变大，要不然不会更优（后面的不会操作到 \(>0\) 所以 \(b_1\) 不用动）。而既然要将 \(b\) 操作成不升的序列，\(b_1\) 也不会变小要不然给后面的限制就更紧了。所以 \(b_1\) 一定不会动。
考虑最初 \(a\) 是排好序的，\(a_i\leq a_{i+1}\)，所以 \(b_i-1\leq b_{i+1}\)，换而言之，往后一个 \(b\)，变小程度不会 \(>1\)．这个时候再用 sequence 那个题的做法，并且利用 \(b_i-1\leq b_{i+1}\) 将堆换成桶来做到线性复杂度。
代码
int n,m,a[N],buf[N<<1],*vis=buf+1,tong[N];
void solve(){
gi(n);gi(m);for(int i=1,x;i<=n;i++){gi(x);tong[x]++;}n=0;
for(int i=0;i<=m;i++){
while(tong[i]--)a[++n]=i;
tong[i]=0;
}
ll ans=0;
for(int i=1;i<=n;i++)if(a[i]>i)ans+=a[i]-i,a[i]=i;
for(int i=1;i<=n;i++)a[i]-=i,a[i]=-a[i];
vis[a[1]]++;
int up=a[1];
for(int i=2;i<=n;i++){
vis[a[i]]++;
if(a[i]>up)up=a[i];
while(!vis[up])--up;
if(a[i]<up){
ans+=up-a[i],vis[up]--,vis[a[i]]++;
if(a[i]>up)up=a[i];
}
}
for(int i=1;i<=n;i++)vis[a[i]]=0;
print(ans);pc('\n');
}
8. Noi2016十连测第一场 模范学长
这让我们想起 Tutte 矩阵那里用到过的 Schwartz-Zippel，对于域 \(\mathbb{F}\) 上的一个不恒为 \(0\) 的 \(n\) 元 \(d\) 度多项式 \(P(x_1, x_2,\cdots, x_n)\)，
设 \(r_1,r_2,\cdots,r_n\) 为 \(n\) 个 \(\mathbb{F}\) 中的独立选取的随机数，则：
在这里为了 check 多项式系数是否为偶数，在域中需要满足 \(x+x=0\)，但是模 \(2\) 的域 \(F_2\) 太小了肯定不行，于是考虑用系数模 \(2\) 的多项式环。说人话就是每个未知元用一个随机的系数模 \(2\) 的多项式（这里假定占位元是 \(x\)），然后所有运算都在模一个多项式 \(m\) 意义下进行，用二进制数表示一个多项式就行。
多项式加法肯定就是二进制数的异或（先不考虑是否需要取模），乘法咋做？考虑龟速乘，计算 \(a*b\) 的时候每次将一个 \(a*x^k\) 异或上去，现在问题就是龟速乘的时候 \(a\gets a*x\) 之后咋快速对 \(m\) 取模。
我们想让 \(a\) 总是它所在的剩余类中最小的那个，考察与 \(a\) 在同一剩余类中数有哪些，由于系数 \(\bmod\ 2\) 所以只需要考虑在 \(m,xm,x^2m\cdots\) 中选取若干个加到 \(a\) 上面就能得到 \(a\) 剩余类中的所有数。假设 \(m\) 的最高次项为 \(x^d\)，此时发现这个剩余类中有且仅有一个最高次项 \(<x^d\) 的，用它当作这个剩余类的代表元即可。这个时候再考虑加法，由于每个数的最高次数 \(<x^d\)，所以加法不会出现需要取模的情况，直接异或就行。
所以就二进制数 \(a\) 左移一位之后如果最高位是 \(x^d\) 了，将其异或上 \(m\) 即可。更简洁的写法是直接 \(\min(a,a\operatorname{xor}m)\)，效果是一样的。在高消的时候 A'[j][k]=A[j][k]-A[i][k]*A[j][i]/A[i][i] 两边同乘 A[i][i] 之后就没有了乘法，由于只需要 check 行列式是否非 0 所以用 A[j][k]*A[i][i]-A[i][k]*A[j][i] 来作为 A'[j][k]$ 即可，只是相当于给矩阵整体乘了个 A[i][i]．
这里 \(m\) 选取不可约多项式很好，EI 说随机之后有 \((1+o(1))/d\) 的概率是不可约多项式。
注记：判断不可约多项式，von zur Gathen & Gerhard 的 Modern Computer Algebra, 第 14 章
A polynomial \(f\in \mathbb{F}_q[x]\) of degree \(n\geq 1\) is irreducible if and only if
- \(f\) divides \(x^{q^n}-x\), and
- \(\gcd(x^{q^{n/t}}-x,f)=1\) for all prime divisors \(t\) of \(n\)
我的评价是：打住，别学了。
代码
const int mod=1000000007;
mt19937_64 rnd(time(NULL)^(ull)(new char));
const int N=61;
int val[N];
int mul(int x,int y){
int s=0;
while(y){
if(y&1)s^=x;
x<<=1;
if(x&(1<<29))x^=mod;
y>>=1;
}
return s;
}
int getval(string &s){
int len=s.size();
int o=0,now=1;
for(int i=0;i<len;i++){
if(s[i]=='+')o^=now,now=1;
else if(s[i]>='a'&&s[i]<='z')now=mul(now,val[s[i]-'a']);
else now=s[i]-'0';
}
o^=now;
return o;
}
int n;
string s[N][N];
int a[N][N];
int gauss(){
for(int i=1;i<=n;i++){
int p=0;
for(int j=i;j<=n;j++)
if(a[j][i]){
p=j;
break;
}
if(!p)return 1;
swap(a[p],a[i]);
for(int j=i+1;j<=n;j++){
int t=a[j][i];
for(int k=1;k<=n;k++){
a[j][k]=mul(a[j][k],a[i][i])^mul(a[i][k],t);
}
}
}
return 0;
}
void solve(){
read(n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>s[i][j];
for(int q=1;q<=10;q++){
for(int i=0;i<26;i++)
val[i]=rnd()%(1<<29);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=getval(s[i][j]);
if(!gauss()){
puts("No");
return ;
}
}
puts("Yes");
}
9. HDU 6804 Contest of Rope Pulling
这个题的套路是 \(\pm 1\) 随机游走，前缀和最值期望只有根号，所以 random_shuffle 之后 开 \(\mathcal{O}(\sqrt n V)\) 大小的背包就行。
10. HDU6413 棋盘上的旅行
另一个随机化的套路，给每个权值赋一个随机颜色，只要答案中的权值满足颜色两两不同就能得到正解。
11. CF1292F Nora's Toy Boxes
够炫酷。
\(a_i\mid a_j\) 则连边 \(i\to j\)．正难则反，考虑往里面加点。对每个弱连通块单独考虑。初始图中有入度 \(d=0\) 的点，对于 \(d\neq 0\) 的至少要有一个，对 \(d\neq 0\) 的点可以标记出若干 \(d=0\) 的点记作 \(T_i\)，表示其后继也能选了。于是可以设计状态 \(f_{S,i}\) 表示已经标记出了集合 \(S\) 中的点，并且 \(d\neq 0\) 的已经选出来了 \(i\) 个，转移分为两类，一个是心选一个不会更新 \(S\) 的点转移到 \(f_{S,i+1}\)，需要记录 \(S\) 子集内有几个 \(T\)；另一个转移是枚举一个能够扩张 \(S\) 的 \(T\) 并且转移到 \(f_{S\cup T,i+1}\)．
分析一下一个弱连通块 \(d=0\) 的点有多少个，首先它要有出度所以仅考虑 \(\leq a/2\) 的点，它们两两不整除也就是一条最长反链，其 \(\leq\) 最小链覆盖，而所有奇数及其 \(2^k\) 倍数已经是一个大小为 \(a/4\) 的链覆盖。在这个分析下 \(d=0\) 的点最多 \(a/4\) 个。
那么现在这个做法是 \(\mathcal{O}(2^{a/4}n^2)\)，这里记了已经选了几个点其实并不必要？因为只需要求最后选出点最多的方案，但是问题在于当前已经可以放进集合的有可能在后面才放进集合。于是想到从末状态倒着往前插（似乎正难则反第二遍又变成原问题了）这样转移的时候只需要考虑当前新增的这些用一个排列数组合进方案里即可，这样复杂度就是 \(\mathcal{O}(2^{a/4}n)\) 的了。
12. CF1149D Abandoning Roads
权值为 \(a\) 的边连成了若干连通块，只有连通块之间的 \(b\) 才有用。想直接跑最短路得出答案，问题在于可能会通过走更短的几次 \(b\) 来代替在同一块内的一堆 \(a\)，路径更短但是经过同一连通块两次所以不合法。那就尝试直接状压记录走了哪些连通块，由于点数 \(\leq 3\) 的连通块一定不会通过几次 \(b\) 代替一堆 \(a\)（最极限的情况就是 \(2\) 个 \(b\) 代替 \(3\) 个 \(a\)）所以只需要记录 \(\geq 4\) 的连通块，这样复杂度就是 \(\mathcal{O}((n+m)2^{n/4})\)．