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

G - Row Column Sums 2

求个数mod 998244353

nxn的矩阵, 元素非负整数

行i 和为ri

列i 和为ci

范围

n 5000

ri,ci [0,1,2]

3s

1024mb

我的思路

这 ri, ci很有说法,

显然 sum r == sum c

说明每行/列只有4种情况 全0,1个1,2个1,1个2

而全零的行列可以直接删掉

如果是一个2的情况, 那么显然对应到另一个2的

因此变成

一些 行列为2的成对 直接填2, 剩余的 只有 1个1 和2个1

行 (a个1,b个2)

列 (c个1,d个2)

选出 t个填2的行列

sum binom(b,t) * binom(d,t) * t!(其中行定,列匹配) * f(a,b-t,c,d-t)

因为上面枚举了t

希望能在小于O(N)的时间 算出 f(a,b,c,d) = 行(a个1,b个2) 列(c个1,d个2) 全部拆成1和1+1的方案

注意到a,c 不变 考虑最小的b,d 比如f(a,b,c,0)的情况, 比较好算, = c!/(c-a)! * binom(2b,2) * binom(2b-2,2) * binom(2b-4,2) …

1
2
3

  1 1 1 1 1 1
a
b

然后考虑 每次b和d增1

1
2
3
4

  1 1 1 1 1 1 2
a             j
b
2      i      x

如果这增的两个选了, 那么4种情况

对应原来一种情况, 是原来一个(1,1) 指向的

1
2
3
4
5
6
7

  1 2
1   j
2 i x
```

对应原来一种情况, 是原来一个(1,2) 或(2,1) 指向的

1 2

2 1 j
2 i x

1
2
3
4
5
6
7
8

对应原来一种情况, 是原来一个(2,2) 指向的

````
    2 2
    1
2 1   j
2   i x

对应 [b-2][d-2] 的情况 前面还插入了两个

1
2
3

    2 2
2   1 j
2   i x

f[b][d] = f[b-1][d-1] * (a+2*(b-1)) + f[b-2][d-2] * (d-1)*(b-1)

然后考虑说 新增的没有共点 ???????????????????????????????????

1
2
3
4

      2
      1
      1
2 1 1

上面 看起来是二维, 然而实际上b和d的差为定值, 所以是个一维的

diff=d-b >= 0

f[b] = f[b-1] * (a+2*b) + f[b-2] * (b+diff-1)*(b-1)

但是不共点的情况 咋讨论啊, 感觉好多啊, 不会了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

  1
  1
11

  1
 11
11

1 1
  1
11

1 1
 11
11

 11
  1
11

  1
1 1
11

 11
1 1
11

难道 对 这种2x2 的形态进行计数, f[i][状态=6] ?

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

G - Yet Another mod M

给长n数列A, distinct( ai != aj)

问是否存在 m \in [3,1e9]

使得 a[i]=a[i]%m 后,

有一半以上的数为某个x,(存在x使得x的个数 > 非x的个数)

范围

n 5000

ai 1e9

2s

1024mb

我的思路

感觉又是数论什么的, 不过这个n 5000 不知道是有什么n^2的说法吗

首先假设 能有x(m) 满足

显然 若p为m的因子

那么 这些 xi%m == x(m) 的 对应 xi%p = (xi%m)%p = x(m) %p 依然满足

所以只用考虑 质数 和 2 * 质数, 又因为2*质数 如果合法,则质数合法, 当为2^幂次时, 校验4即可

所以 只用考虑 质数

如果本来就有数字次数大于一半, 那么随便取

否则必定会让原来不等的两个数相等

考虑两个不等的数 ai,aj

ai % m == aj % m

(ai-aj) %m = 0

所以枚举质因子

但这样是 n^2 sqrt(ai) n

感觉并过不了? 上质因子拆解模版?

还是先收集完(ai-aj)

然后同时进行质因数查找

关键验证还需要n

(ai-aj)%m == 0 等价与 它们mod m后相等

换句话说, 收集ai-aj 后

如果 有t > n/2个值相等

那么两两成边 t(t-1)/2 条边, 即 ai-aj 需要 >= t(t-1)/2

这样的话 直接在收集后 的ai-aj 中枚举m????(O(max(ai/2)))

不会

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

G - Access Counter

给定 长24的C

如果 Ci==T, 甲 X % 可能访问

如果 Ci==A, 乙 Y % 可能访问

超过的C看作循环

好的状态 = 甲不是第N次方案的

求好的状态的 概率 mod 998244353

范围

n 1e18

x,y [1,99]

|c| == 24

2s

1024mb

我的思路

先最无脑的

dp[i][j] = 第i个被访问, 且是第j次 的概率

dp[i][j] = dp[k < i][j-1] * prod p[k+1..i-1] 不被访问 p[i]

ans = sum dp[i是乙][n]

然而是个无限的求和

要干掉无限

那么换个角度

dp[j][idx] 第j次访问, 位置在C[idx] 的概率

dp[j][idx] = dp[j-1][i=0..23] * p[i->idx] 从i开始下一次访问idx, 中间不访问其它的概率

这里把dp[j] 看成一个向量, p与j无关的常系数矩阵, 不就是矩阵快速幂了!

所以如何算p[pos0 -> pos1]

直接走到 = prod(1-p[pos0+1..pos1-1]) * p[pos1]

绕一圈走到 = prod(1-p[pos0+1..pos1-1]) * prod(1-p[...]) * p[pos1]

绕两圈走到 = prod(1-p[pos0+1..pos1-1]) * prod(1-p[...])^2 * p[pos1]

综上 = prod(1-p[pos0+1..pos1-1]) * p[pos1] * 1/(1-prod(1-p[...]))

问题来了, 如果分母为0 怎么办?

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

F - Transportation

n 个点

Xi 价格 点i 修 airport

Yi 价格 点i 修 harbor

Zi 修路 ui<->vi, m条

最小代价 所有点连通

范围

n 2e5

m 2e5

xi,yi,zi[1,1e9]

4s

1024mb

我的思路

如果没有airport/harbor, 那么就是 最小生成树

如果有

则会有两个点同时有 两种交通工具, 或者一个点同时三个交通工具

如果能确定基础代价, 那么增加连通代价 要么是路, 要么是某个交通工具

n这么大 也不能bitmask

如果只有一种

那么就是 先考虑所有都建立, 然后每次可以拆一个 贡献 -Xu + min(road[u,v?])

不会了

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

G - Reversible Cards 2

给定n张卡, 每张 正面ai,反面bi

初始都正面

问对于 k=0..m 的每个取值

让 可见面=k的最小翻转次数

所有 ai+bi 和为m, 所有ai,bi 在[0,m] 之间的整数

范围

n 2e5

m 2e5

3s

1024mb

我的思路

先想的是分治

f[i..j][v] 表示[i..j] 这一段 可见面=v的最小翻转次数

f[i..j][v] = min(f[i..mid][x]+f[mid+1..j][v-x])

似乎 需要min卷积 并不会

想过网络流, 但这里没有最大最小什么的, 唯一的最小就是最小次数, 但感觉网络流上 去等于k 看起来更像是费用和,

预处理, 先计算所有Ai的和, 然后翻转 看成 Bi-Ai 的增量

问题变成 有n个变量, 问和 = k-sum(A) 的最小选择个数

一股 spfa的感觉?

不会