https://atcoder.jp/contests/abc309/tasks

Ex - Simple Path Counting Problem

N行 M列 grid

长K整数数组A

长L整数数组B

$f(i,j) =$从$(1,A_i)$移动到$(N,B_j)$恰好$(N-1)$次的路径方案数

其中每次移动$(+1,-1),(+1,+0),(+1,+1)$

求$\displaystyle \sum_{i\in[1,K]}\sum_{j\in[1,L]} f(i,j) \pmod{998244353}$

$1\le N\le 10^9$

$1 \le M,K,L,\le 10^5$

$1\le A_i,B_j\le M$

10 s

1024 MB

我的思路

这个 坐标的x始终+1,看起来没什么用啊

所以$f(i,j)$等价于 $A_i$变为$B_j$,且每次$+1/+0/-1$,过程中不超过$[1,M]$范围的恰好$N-1$次的方案数

如果 没有范围限制, 对于合法$X+Y*0-Z = B_j-A_i, X+Y+Z=N-1$的方案数有$\binom{N-1}{X,Z}$

$\displaystyle \sum_{Z=1}^{N-1} \frac{(N-1)!}{Z!(B_j-A_i+Z)!((N-1)-Z-(B_j-A_i+Z))!}$

其中令$\frac{1}{(<0)!} = 0$

这种情况 只和 $B_j-A_i$的值有关,可以预处理(所有差在$[-(M-1),+(M-1)]$内 )+统计(??????????????????)就可以

似乎连统计两个数组的所有差都不会??

好像 $f_A(x) = \sum count(A[i]=v)x^{-v}$

$f_B(x) = \sum count(B[i]=v)x^{v}$

$f_A(x)f_B(x)$ 应该就能统计

然后为了不要处理负, $f’_A(x) = x^{\max{v}} f_A(x)$即可

其实这里还有个问题是 N很大的话 暴力计算阶乘够吗?

那么回到题目, 当有范围限制要如何做呢?

似乎没有办法

但这里既然想到生成函数

$[x^j] f_i(x)$ 表示移动$i$次后路径值变为$j$的方案数

$f_0(x) = x^{A_i}$

$g(x) =$转移方程

$f_i(x) = g(f_{i-1}(x))$

求 $[x^{B_j}]f_{n-1}(x)$

好像 为了$[1,M]$的范围 还是要处理 两端..

一个想法是, 去计算 2的幂次的转移变化, 这样的话 对于N就是log级别了

但似乎 这会变成 $M * M$的矩阵,而不是一个简单的乘上一个函数

https://atcoder.jp/contests/abc308/tasks

Ex - Make Q

简单无向图, N点,M边, 初始边白色, 如果要把边染色成黑色代价Ci

也就是 要 给一个环上色，且延伸一个 环内点-环外点的边，也就是视觉意义上的Q

问 画出Q的最小代价

n300

ci 1e5

4s

1024mb

我的思路

这个n300 不知道怎么用，看起来像是n^3 一类的玩意

如果给定了圆，那么延伸边，可以直接暴力枚举O(n^2)？

一个思路是最小生成树，而和最小生成树不同的是，当有同并查集的时候 直接触发 找环

问题是，每边尽量短并不意味环更短，10个1 > 3个2

钦定 环上延伸边的点

环上延伸边的点是u, 然后找环，再定延伸边

for u (O(n)): 找环?, 延伸边:O(n)

如果先定延伸边，那么就是 求不含延伸点，含固定点的最小环

似乎并不会找 含 固定点的最小环

另外，如果再处理一下， 先找含固定点的最小环，那么未包含的点就可以作为延伸点，包含的点再考虑

1
2
3
4
5
6

1-(1)-2-(1)-3
1-(1)-4-(1)-3
1-(3)-3
1-(100)-5
显然 最小环是 1-2-3-4-1, 长度是4,但是延伸点会是1-5长度100
而 1-2-3-1 环更大是5，可以选延伸边1-4长度1

https://atcoder.jp/contests/abc307/tasks

Ex - Marquee

给定长度L的字符串S, 包含大小写字母, 在宽W的滚动显示器上，每次移动一个字母

因此有L+W-1种状态,例如S=ABC,W=5,点表示空

1
2
3
4
5
6
7

ABC..
BC...
C....
....A
...AB
..ABC
.ABC.

现在问题是 给定长度L字符串 T，问有多少个 状态和T匹配

T中有字符_可以匹配任意字符

l,w 3e5

5s

1024mb

我的思路

实际上滚动可以看成，S左侧W-1个点，右侧W-1个点

1

.....S.....

然后 用T去匹配

这匹配有点KMP的感觉，

但这里任意字符_ 似乎不是很好转移

一个想法是 KMP的树状版：AC自动机能有用吗？

但实际还是,KMP中 aba 的后缀最长匹配前缀的是a

而___的后缀最长匹配前缀是__

需要一个可以支持 通配符号的类似的 匹配算法

自匹配还算好，就是kmp的原理

dp[i]=i结尾后缀 相等的 最长前缀长度

dp[i] = dp[j] + 1, match(a[i],a[j+1]) and dp[i-1]最先递归向下到j

然而并不对

例如 样例1

1
2

ABC
..___

对于T来说 ..___ 的后缀(.___)match的最长前缀长度为4 (..__)

但是对于..ABC => .ABC. 转换 并不是只鉴定最后一位就可以的

也就是

1
2
3
4
5

 .ABC.
..ABC
..___
 ..__
 ..___

这个match关系没有传递性

但是是必要条件，因为S的子串如果match,则可以看成T的一个特例化，而如果 特例化对应match,则非特例化一定match

https://atcoder.jp/contests/abc306/tasks

G - Return to 1

n点,m有向边

从1开始，每次 从当前点选一条边移动，问$10^{10^{100}}$次时能否回到1

n,m 2e5

2s

1024mb

我的思路

次数巨大，如果走k1次回到1，k2次回到1

那么可以 gcd(k1,k2)次的足够大的倍数回到1， 因为 问题中的次数巨大，所以 ak1+bk2=c gcd(k1,k2) = 10^{10^{100}}能找到正解

所以 问题是能否找到 两个不同的次数的 gcd 只有2和5的因子

一个不会证明的想法是，计算从1出发到达每个点的不超过2种 距离，和逆向从1倒退不超过2种距离

这样每个点 可以得到2x2种从1到1的距离

对所有距离做gcd看看是否只有 2和5的因子

但是这个做法，正确性 感觉不会证明

https://atcoder.jp/contests/abc305/tasks

Ex - Shojin

N个问题, 难度(Ai,Bi)

选择$D \in [1,N]$天 完成所有N个问题，即把N个问题分成D个连续非空子区间

疲劳x 每天初始 = 0，每天完成当前的区间中的问题

区间内问题顺序可以任意调整，每次完成一个问题后 x_new = A x_old+B

给定X, 问 min D, 使得 sum x_每天结束<= X

输出 (min D, 对于 min D时最小的sum x_每天结束)

n 2e5

X 1e8

ai [1,1e5]

1<= bi

sum bi <= X

3s

1024mb

我的思路

先说一天内，如果指定了区间

先i后j: $a_j(a_i x + b_i) + b_j$

先j后i: $a_i(a_j x + b_j) + b_i$

如果要 $a_j(a_i x + b_i) + b_j < a_i(a_j x + b_j) + b_i$

即 $a_j b_i + b_j < a_i b_j + b_i$

即 $(a_j-1) b_i < (a_i-1) b_j$

即 $\frac {a_j-1}{b_j} < \frac{a_i-1}{b_i}$

即每个元素 可以按照key = $-\frac{a-1}{b}$ 排序

反过来排序则是最大

问题其实变成对于给定D, 求min

对于min显然 随着D增加，min 单调递减，因为至少有一天两个问题，而后一个问题的额外代价 是 (Ax+B)-x = (A-1)x+B, 而单独放一天则是B, 而A>=1

有一个巨大的dp

dp[i][d] 以i结束，i前面划分了d天的 最小消耗

就是求 dp[n][min d] <= x

dp[i][d] = min(dp[j][d-1] + cost[j+1..i]), j<i

首先 状态就n^2,空间就n^2 ,转移看上去要n^2,时间就是n^4

先说能否降低到n^3, 也就是cost[i...j] 有没有什么快速的计算方法或者预处理

显然x=Ax+B可以用矩阵乘法表示

那么就可以用线段树按 上面 -(a-1)/b 的顺序 维护

一个区间就是区间内的变成 对应的矩阵，而区间外的 变成 单位矩阵

那么计算一个区间cost[i...j] 无非就是cost[i...j-1] 基础上让 j在线段树中对应的 变为对应矩阵再计算完整线段树的 矩阵乘法结果，

这样显然 循环 遍历i,j 能 n^2 log n 算出所有cost[i..j]

至少时间复杂度变成 n^3 + n^2 log n

感觉 还缺了什么数学性质

但对于相邻的两个区间，并不知道 相邻位置放在哪个区间好

因为并不知道 它 排序后的位置，

虽然可以 预估它放最前 和 最后的贡献变化，一个是预估，另一个是需要他前后的区间的信息