Hall’s theorem, 霍尔定理

二分图 左侧$n$点,右侧$m$点, $n\le m$

二分图的最大匹配个数$=n$ 的充要条件, 左侧点$n$的任意大小$(=k)$的子集 连到右图的点的个数都满足$\ge k$

$f(a,b,c,n) = \sum_{x=0}^n \lfloor \frac{ax+b}{c} \rfloor$

代码

1
2
3
4
5
6
7

// \sum_{x=0}^n \lfloor \frac{ax+b}{c} \rfloor
ll floor_sum(ll a,ll b,ll c,ll n){
  if(a==0) return (b/c)*(n+1);
  if(a >= c or b >= c) return n*(n+1)/2*(a/c) + (n+1)*(b/c) + floor_sum(a%c,b%c,c,n);
  ll m = (a*n+b)/c;
  return m*n - floor_sum(c,c-b-1,a,m-1);
}

https://atcoder.jp/contests/abc337

G - Tree Inversion

n点树

for u = 1..n

求 有多少(v,w),满足 w在u..v路径上(w可以等于u,v)，且v < w

n 2e5

1024mb

我的思路

如果是一个点u，

那么可以把u作为根，做dfs

dfs过程中 维护父向点集，和求 >= 当前点的个数

这样可以 树状数组维护，是O(n log n) 可以做的

但这同时求多个似乎不太好转换

1
2
3
4
5
6

     u
v1,v2,v3,...

u
|edge
v1

若和u直接相连的点是v1,v2,…,v3

从换根dp的角度想

如果u换成v1,把这条边叫做edge,那么原来 (u-v2子树),(u-v3子树)… 的贡献都不会变

只有w=u,而v 在(u-v1子树)中的贡献不见了

ans -= tree(edge-v1子树, < u)

多出来的是w=v1,而v在 u-v2/v3/…

ans += tree(edge-u, < v1)

所以如果有预计算 每条边 u0-u1,

tree(u0,< u1) 和tree(u1,< u0)，就可以实现换根dp

这怎么算呢，

想的是 启发式合并，每次点少的向多的合并

同样fenwick维护,似乎能做?

https://atcoder.jp/contests/abc336

F - Rotation Puzzle

h行w列, 数字$[1,hw]$每个出现一次

一次操作 选取$(h-1)\cdot(w-1)$的矩形 旋转180度

问是否能让20次操作内，所有数字 变成 从小到大 从左到右从上到下 的样子

1
2

1 2 3 4
5 6 7 8

h,w [3,8]

5s

1024mb

我的思路

如果单独考虑x的变化

从中线划分

那么左侧的x，在左侧矩形选择翻转时，它变为右侧，且和边界距离+1

那么右侧的x，在左侧矩形选择翻转时，它变为左侧，且和边界距离-1

感觉 有用但又没有用

另一个想法就是meet-in-middle + 暴力搜索, 因为一个操作立刻反向操作 等于没操作，所以除了首次操作 后续的操作都 3分叉，数据量看起来是能接受的

$3^{10}\cdot 8\cdot 8=3779136$

哎, 本来以为什么神奇性质题，结果无聊的meet-in-middle

https://atcoder.jp/contests/abc335

G - Discrete Logarithm Problems

长度n数组a, 质数$p$

1
2
3

for i in 1..n:
	for j in 1..n:
		ans += 存在k使得  ai.pow(k) \equiv aj \pmod{p}

求 ans

n 2e5

$p \in [2,10^{13}]$

$a_i \in [1,p)$

5s

1024mb

我的思路

首先什么时候会不存在不等

$a_i^k\equiv a_j\pmod{p}$

而注意到例如$1$ 只能得到$1$,而$p-1$只能得到$-1,1$

回忆到64位的miller robin 判别法的过程

需要考虑的是 幂次是$p-1$的 因子 的幂次,也就是$a^t\equiv 1 \pmod{p}$

例如对于7来说

1
2
3
4
5
6

1 (1)
2->4->1 (3)
3->2->6->4->5->1 (6, ntt中会选择的)
4->2->1 (3)
5->4->6->2->3->1 (6)
6->1 (2)

p有10^13，可以暴力 sqrt(p) 分解p-1

然后 通过从小到大尝试 p-1的因子的幂次 是否

可以O(n * log(p) * log(p))计算出每个 ai 的最小幂次x,使得ai^x = 1 \mod p

对于长度 p-1的 肯定是全 可以 贡献N

问题是 长度更小的呢，如何知道哪些可以，哪些不行

$t(a_i) =$最小的幂次使得$a_i^{t}\equiv 1\pmod p$

那么对于成立的 $a_i^k\equiv a_j\pmod{p}$

有$k\le t(a_i)$

$a_i^{kt(a_j)}\equiv a_j^{t(a_j)}\equiv 1\pmod{p}$

$kt(a_j) =wt(a_i), w\in\mathbb{Z}^+$

$\displaystyle k\frac{t(a_j)}{\gcd(t(a_j),t(a_i))} =w\frac{t(a_i)}{\gcd(t(a_j),t(a_i))}, w\in\mathbb{Z}$

$k$是$\displaystyle \frac{t(a_i)}{\gcd(t(a_j),t(a_i))}$的倍数 且 $\le t(a_i)$

好像量级还是没啥变化

另外$1\equiv (a_i^{t(a_i)})^k\equiv (a_i^{k})^{t(a_i)} \equiv a_j^{t(a_i)} \pmod{p}$

所以如果$t(a_j) > t(a_i)$ ,和t的最小的定义矛盾, 必定没有方案

所以$t(a_j)\le t(a_i)$

同样从幂次的因子角度考虑

3->2->6->4->5->1 长度6

而6的因子有1,2,3,6

例如 $2=3^2$,$2^t=3^{2t}$,所以2->4->1实际上是上面2的倍数项

例如 $6=3^3$,$6^t=3^{3t}$,所以6->1实际上是上面3的倍数项

所以$a_i^x$如果$x$是$t(a_i)$的因子,那么$t(a_i^x)\equiv \frac{t(a_i)}{x}$

而如果拉长

1
2
3
4

[              ]  [              ]
3->2->6->4->5->1->3->2->6->4->5->1
         |           |           |
         4           2           1

这里有$t(3^{len=4})=3=\frac{1}{2}6=\frac{1}{2}t(3)$

而 这种倍长过程实际就是在求$lcm(t(3),len=4)$

所以显然$t(a^x)=\frac{lcm(x,t(a))}{x}=\frac{t(a)}{\gcd(x,t(a))}$

$t(a_j)=t(a_i^k)=\frac{t(a_i)}{\gcd(k,t(a_i))}$

2和3都是6的因子不太好考虑不是的情况

现在考虑p=11,那么p-1=10,因子有1,2,5,10

1
2
3

      2->4->8->5->10->9->7->3->6->1
pow   1  2  3  4   5  6  7  8  9  10
len   10 5 10  5   2  5 10  5 10  1

注意到1~10每个数字可以都表示成 2的幂次，所以, 它们的链，不过是2多次增长以后，按照幂次跳跃取得的

一个猜想:

长度成倍数，则包含：t(a_i) % t(a_j) =0则$a_i^k\equiv a_j\pmod{p}$

那么p=11也不是个好例子，看看p=13,p-1=12,这样的话长度可能是4和6,而4和6不是倍数关系却gcd不为1

1
2
3
4
5
6

    2->4->8->3->6->12->11->9->5->10->7->1
pow 1  2  3  4  5   6   7  8  9  10 11 12
         [1]        2         3         4 长度4的链
          3         2        [1]        4 长度4的链
      [1]    2      3      4      5     6 长度6的链
       5     4      3      2     [1]    6 长度6的链

虽然有重叠元素，但是互相不包含,

对于oi比赛，那这个时候，已经可以编码了

那么问题来了，数学上如何证明呢？？？？？？

而且这样的方法 因子可能有8e3量级的个数, 在计算 t(a_i)时 时间似乎不够 2e5 * 8e3 * log(8e3,2) ~= 2e10

所以 数学证明 和 效率都有问题