https://atcoder.jp/contests/abc338

G - evall

给定字符串S,由123456789+*组成

最开始和最后的字符是数字，没有相邻的非数字

对于$(i\le j)$, 如果s[i],s[j]都是数字，则eval(i,j)为这一段字符串的表达式结果

否则 为0

求 $\displaystyle \sum_{i=1}^{|S|}\sum_{i=j}^{|S|} eval(i,j)\mod 998244353$

$|S| \le 10^6$

2s

1024mb

我的思路

这里虽然没有括号，但是有乘法的优先运算

如果固定前面

1
2
3

1234123*234*345+3245*145+324*45*345
[............]
fix          i->

那我们得到的是 [base + prodbase * (cur=34)]

每次遇到数字就是cur*=10,cur+=int(s[i])

而进入新的乘法则是prodbase*=cur, cur = 0

而进入新的加法则是base+=prodbase*cur,prodbase=1,cur=0

这个方法的问题在于 如果想用矩阵表示，那么在做prodbase * cur的时候 无法做这个乘法

再增加prodres东西

1
2
3
4
5
6

1234123*234*345+3245*145+324*45*345
                                 i
[base                  ]          
                         xxxxxx      prodbase 
                                xx   cur
                         xxxxxxxxx   prodres

ans = base + prodres

prodres = prodbase * cur, 而新的转移 发现cur不需要了

那么 遇到数字时,

1
2
3
4
5
6

			sumall     base prodres    prodbase    1
sumall        1 
base          1         1     
prodres      10                 10
prodbase   int(char)         int(char)     1  
1                                                  1

那么 遇到+时,

1
2
3
4
5
6

			sumall    base prodres    prodbase     1
sumall        1 
base                   1          
prodres                1                
prodbase            
1                                         1        1

那么 遇到*时,

1
2
3
4
5
6

			sumall    base prodres    prodbase    1
sumall        1 
base                   1          
prodres                                   1               
prodbase            				       
1                                                 1

所以，后缀矩阵乘法就秒了

前置的是[0,0,0,1,1]

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