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

G - Count Sequences

范围 [0,m] 单调递增 n个数, 且相邻 mod 3 不同

问 方案数 mod 998244353

范围

n 1e7

m 1e7

4s

1024mb

我的思路

f(n,m) = 范围 [0,m] 放n个数, 第一个放0 的方案数

ans = sum f(n,0..m)

f(n,m) = sum f(n-1,m-非3倍数)

考虑 生成函数 f(n,m) 为 生成函数$F_n$的系数

$F_1 = 1+x+x^2+x^3+\cdots = \frac{1}{1-x}$

$ans = \lbrack x^m \rbrack (F_n \cdot \frac{1}{1-x}) $

$F_i = F_{i-1} \cdot (x+x^2+x^4+x^5+x^7+x^8+\cdots)$

$= F_{i-1} \cdot \frac{x+x^2}{1-x^3}$

$F_n = F_1 \cdot (\frac{x+x^2}{1-x^3})^{n-1} $

$ans = \lbrack x^m \rbrack \frac{(x+x^2)^{n-1}}{(1-x)^2(1-x^3)^{n-1}}$

然后 我暴力算 样例就TLE了

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

G - Infinite Knapsack

n种物品, 每种无限多个

第i种, 重ai,体积bi,价值ci

f(X) = 总重量<=X,总体积<=X的最大价值

可证明 lim_{x->infty}f(X)/X 的极限存在, 求极限

范围

n 2e5

ai,bi,ci [1e8,1e9]

2s

1024mb

我的思路

感觉就一个很数学的题

考虑3元组, (a,b,c) 若 a >= b, 等价于a个(a/a,b/a,c/a)

若 a < b, 等价于a个(a/b,b/b,c/b)

于是分成两种

$(1,p\le1,c_0),p=b_0/a_0$

$(q\le1,1,c_1),q=a_0/b_0$

而实际上未来增长只会是 这两种按一个比例的和

$(t_0,pt_0,c_0t_0) + (qt_1,t_1,c_1t_1)$

$t_0 + qt_1 = pt_0+t_1 $

$t_0 = t_1 (1-q)/(1-p)$

$c_{0,1} = (c_0t_0 + c_1t_1)/(t_0 + qt_1)$

$= (c_0(1-q)/(1-p) + c_1)/((1-q)/(1-p)+ q)$

$= (c_0/(1-p)+c_1/(1-q))/(1/(1-p)+q/(1-q))$

$ans=\max(c_0,c_1,(c_0(1-q)+ (1-p)c_1)/((1-q)+ (1-p)q))$

问题是两两计算的话 为n^2

稍微改一下

$1,p < 1,c_0$

$1,q > 1,c_1$

$pt_0+qt_0=t_0+t_1$其中$t_0,t_1 > 0$ 即$t_0 = t_1 \frac{q-1}{1-p}$

$c_{0,1}=\frac{c_0t_0+c_1t_1}{t_0+t_1}$

$= \frac{c_0\frac{q-1}{1-p}+c_1}{\frac{q-1}{1-p}+1}$

$= \frac{\frac{c_0}{1-p}-\frac{c_1}{1-q}}{\frac{1}{1-p}-\frac{1}{1-q}}$

也就是 $(\frac{1}{1-\frac{b_i}{a_i}},\frac{\frac{c_i}{a_i}}{1-\frac{b_i}{a_i}})$ 这些点之间的最大斜率

n个点之间 找最大斜率

但注意到的是 是由第4向限和第1向限的点, 并不是两两之间, (因为两两之间的话 相当于$t <0)

直接考虑 分别两坨点的凸包

双指针???? 不会了

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

G - Security Camera 3

给定 h行W列, 一些地方是障碍

问最少安装多少摄像头, 能监控所有非障碍区域,

一次安装 在一个非障碍区域并监控它自身和朝向(4向)的一段连续的非障碍区域

同一个地方可以安装多个不同向的

范围

h,w 300

2s

1024mb

我的思路

把连续一段横着 或者竖着 看作一个单位

那么 对于(i,j) 所在的横的r_x, 和竖的c_y

有关系r_x+c_y >= 1

所有 r和c的取值只能1/0

要 所有r+c 的和最小

似乎是个线性规划?

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

Ex - Colorfulness

n球, 颜色ci

f(球的一个排列) = 相邻不同色的个数

对于k=1..m分别求 $\sum(f(排列)^k)$ mod 998244353

范围

n 2.5e5

m 2.5e5

ci [1,n]

8s

1024mb

我的思路

k==1 时

那颜色可以分开考虑

一个颜色 去计算它能构成x个间隔, 那么它每个贡献 (x+1(两端))/2, 再乘上方案数

注意每个排列的最左和最右还要-1, 所以还要减 n!

k==2时

明显就不一样了, 因为贡献变成了 (相邻不同色)^2

颜色c 有 x间隔 ( (x+1) + 其它颜色间隔贡献 -1)^2

问题 其它颜色贡献会受到颜色c的间隔数x 影响

如果直接按照题目来, 按f(P)归类

如果能算出 不同为y个的 出现次数t(y)

那么 就是 f(1) = sum t(y) * y

f(2) = sum t(y) * y^2

这样做也是 需要O(n m) 的

而且怎么算不同出现次数也没啥想法

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] ?