Atcoder abc345

發表於 更新於 分類於 ， Disqus： 文章字數： 2.4k 所需閱讀時間 ≈ 8 分鐘
E(DP)G(概率论,NTT,牛顿法,拉格朗日反演)

https://atcoder.jp/contests/abc345

E - Colorful Subsequence

n个球 一排，有价值vi,颜色ci

问 恰好删除k 个且 剩余球 相邻不同色，vi和最大值

或不可能输出-1

n 2e5

k 500

v [1,1e9]

5s

1024mb

我的思路

可行性，首先同色连续t个，那么至少删除t-1个，那么留最大的

做完操作后满足了 相邻不同色，再看 恰好删除k个

只需要从两侧删除就可以满足恰好k个了

所以先处理所有连续 变为不同色

然后 不知道怎么搞，感觉需要 nk的复杂度的， 但只想到 nk2的

dp[i][t] = 前i个第i个保留，一共删除t个且合法的最优方案

dp[i][t] = a[i] + max(dp[i-1-d][t-d]) 表示从i-1向前连续删除了 d个的方案, 其中 c[i] != c[i-1-d]

处理边界只需要 两端塞入 {v=0,c=max color+1/+2} 即可

然而上面是 nk的状态 和 k倍的转移代价，所以时间上是 nk2的

两端塞了以后 0 [1...n] 0

ans = dp[n+1][k] = f[n+1][n+1-k]

一个想法是

令 dp[i][0<=t<=i] = f[i][i-t]

f[i][i-t] = a[i] + max(f[i-1-d][i-1-t]), a[i] != a[i-1-d]

还是不知道怎么处理这个不等，而且 这样转换的话，第二个维度的值会很大

但 如果对应到 二维 定义域平面上的话

1
2
3
4
5
6
7
8
            x
           x
          x
         x
t+      x
^      x
|     x
 -> i+

其中

a[i]!=a[i-1-d] 的处理？？？？

题解

一样左侧塞 价值0,颜色0的球

dp[i][j][k] = 前i个 删除了j个 最右颜色k,且合法的最大和，或者无方案是-infity

ans=max dp[N][K][0~N]

dp[0][0][0]=0

dp[0][j][k] = -\infity

dp[i][j][k]=

  • 如果 k != ci ，因为k表示最右侧的颜色，也就是第i个一定会被删掉，=dp[i-1][j-1][k]

  • 如果 k == ci ，如果删掉第i个，那么还是=dp[i-1][j-1][k]，如果不删除第i个，那么 = vi + max(dp[i-1][j][!=k])

然后实现的话 $O(n^2 k)$ 也是TLE

观察转换 实际上从 for i从 i-1变成i的时候， j方向上平移一次就能完成 dp[i][j][k] = dp[i-1][j-1][k]

剩下的就是处理 dp[i][j][k=ci]

那么 对于 max(dp[i-1][j][!=k=ci]) 的处理， 如果记录dp[i][j] => (值,k)的 最大的两个

那么

  • k = 最大值对应的 k,那么 结果=次大
  • k != 最大值对应的 k,那么 结果=最大

注意到 第三个维度[k] 只有平移和 取max,里面是单调递增的

而且 最后的结果也是 取所有k中 对应 最大值

那么会发生什么

f[i-1][j-1] => {{最大值v0,对应k0},{次大值v1,对应k1}}

继承过来 f[i][j] => {{最大值v0,对应k0},{次大值v1,对应k1}}

f[i][j][ci] .setmax(vi + max(f[i-1][j][!= ci]))

后面max部分可以O1算出只需要知道 f[i-1][j]中的最大的k和ci是否相等，记作x

那么 [i][j][ci] = max([i-1][j-1][ci], vi + x)

发现 判断ci 和 f[i-1][j-1]中的k的关系，以及vi+x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def exclude(i,j,k):
	[{v0,k0},{v1,k1}] = f[i][j]
	return k==k0?v1:v0

def patch(i,j, v,k)
	[{v0,k0},{v1,k1}] = f[i][j]
	if k == k0:
		v0 = max(v0,v)
	elif k == k1:
		v1 = max(v1,v)
	else:
		f[i][j].append([v,k])
	sort(f[i][j])
	f[i][j] = f[i][j][:2]

for i:
	for j:
		f[i][j] = f[i-1][j-1]
		patch(i,j, vi + exclude(i-1,j,ci),ci)

然后i的这个维度可以滚动

代码

https://atcoder.jp/contests/abc345/submissions/53649774

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)

ll read(){ll r;scanf("%lld",&r);return r;}
ll INF=0x3f3f3f3f'3f3f3f3f;
using state = array<pair<ll,int>,3>;
state dp[2][510];
int c[200010];
int v[200010];
int main(){
  int n=read();
  int k=read();
  rep(i,1,n+1) { // 2e5
    c[i]=read();
    v[i]=read();
  }
  // for(auto &row:dp) for(auto &col:row) col = {{-INF,-1}};
  # define rdp(i,j) dp[(i)%2][j]
  rep(i,0,1) rep(j,0,k+1) rdp(i,j) = {{{-INF,-1},{-INF,-1},{-INF,-1}}};
  rdp(0,0) = {{{-INF,-1},{-INF,-1},{0,0}}};

  auto exclude=[&](int i,int j,int k) {
    auto vks = rdp(i,j);
    assert(vks.size() == 3);
    return vks[k == vks.back().second ? 1:2].first;
  };
  auto add=[&](ll a,ll b){ return (a==-INF or b==-INF) ? -INF: a+b; };
  auto patch=[&](int i,int j, ll v, int k){
    if(v==-INF) return;
    auto &vks = rdp(i,j);
    bool found=false;
    for(auto &o:vks) if(o.second == k) {
      found=true;
      o.first = max(o.first,v);
    }
    if(!found) vks[0] = {v,k};
    sort(begin(vks),end(vks));
  };

  rep(i,1,n+1)  rep(j,0,k+1) {
    rdp(i,j) = {{{-INF,-1},{-INF,-1},{-INF,-1}}};
    if(j) rdp(i,j) = rdp(i-1,j-1);
    patch(i,j,add(v[i],exclude(i-1,j,c[i])),c[i]);
  }
  ll ans = rdp(n,k).back().first;
  printf("%lld\n",ans<=0?-1:ans);
  return 0;
}

G Sugoroku 5

n+1 个 squares

初始在 squares 0,

每次 扔 骰子(1~k)得到数值y, 从x移动到 min(N,x+y)

1
2
for i = 1..n:
	计算 恰好 i 次 走到 N的 概率 mod 998244353

k <= n <= 2e5

12s

1024mb

我的思路

显然的 概率论题

g(i) = 扔i次骰子，点数和 >= n的概率

p(i) = g(i) - g(i-1)

$f(x) = \sum_{i=1}^k \frac{1}{k} x^i$ 表示扔1次的 概率 x^{点数}

$g(i) = \sum_{t\ge n} [x^t] f(x)^i$

或者反过来 用1去减 $[x^{< n}]$ , $g(i) = 1 - \sum_{t < n} [x^t] f(x)^i$

直接每次计算 $f(x)$基于前面的 迭代+NTT 也是 $n \log n$,总时间也是$O(n^2 \log n)$

一个变化是 不要手动累和$< n$,同样交给生成函数

$g(i) = 1 - [x^{n-1}] (f(x)^i (\sum_{j=0}^{\infty} x^j))$

$g(i) = 1 - [x^{n-1}] \frac{f(x)^i}{1-x}$

$p(i)=g(i)-g(i-1) = [x^{n-1}]\frac{f(x)^{i-1}-f(x)^{i}}{1-x}$

$p(i)=[x^{n-1}]\frac{f(x)^{i-1}}{1-x}(1-f(x))$

没啥想法，

可以 算1次方，2次方，4次方，8次方？？

这样每次 转移都是 减去2的幂次的上一个 次方过来，这样似乎还是 每个都需要计算

题解

一样的方向是 生成方程

$F(x)=\frac{1}{K}\sum_{i=1}^K x^i$

$a_i=x^{N-1}F^i = [x^{N-1}]\frac{F^i}{1-x}$

然后这里对$F(x)$进行代数处理

$F(x)=\frac{x(1-x^K)}{K(1-x)}$

$a_i=\frac{1}{K^i}[x^{N-1}]\frac{x^i(1-x^K)^i}{(1-x)^{i+1}}$

$a_i=\frac{1}{K^i}[x^{N-1-i}]\frac{(1-x^K)^i}{(1-x)^{i+1}}$

  • K很大 可以枚举？？ inverse怎么算？
  • K很小， abc281ex 的 分治方法？ cdq 分治

说是这样可以 $N^{1.5} log N$ 做出来，没有懂

接下来 $N \log N$

$F(x)=\frac{1}{K}\sum_{i=1}^K x^i$

$a_i=\sum_{k=0}^{N-1}[x^k]F^i=x^{N-1}F^i = [x^{N-1}]\frac{F^i}{1-x}$

特别的$a_0=1$

$[x^0]F^{n > 0} =0$

$a_i=\sum_{k=1}^{N-1}[x^k]F^i$

如果能利用 拉格朗日 反函数计算法,(整理了下文章 之前abc222ex出现过)

$[x^k]F(x)^n=\frac{n}{k}[x^{k-n}]\left(\frac{x}{G(x)}\right)^k$

$a_i=\sum_{k=1}^{N-1} \frac{i}{k} [x^{k-i}]\left(\frac{x}{G(x)}\right)^k$

$=\sum_{k=1}^{N-1} \frac{i}{k} [x^{-i}]\left(\frac{1}{G(x)}\right)^k$

$=i[x^{-i}]\sum_{k=1}^{N-1} \frac{1}{k} \left(\frac{1}{G(x)}\right)^k$

如何计算右侧

令 $H(x) = \sum_{k=1}^{N-1} \frac{1}{k} \left(\frac{1}{x}\right)^k$

$H(G(x)) = \sum_{k=1}^{N-1} \frac{1}{k} \left(\frac{1}{G(x)}\right)^k$

$H(G(x)) = \int (\frac{d}{dx} H(G(x))) + C$, 注意到, 其中0次方系数 并不在意

$\displaystyle \int (\frac{d}{dx} H(G(x)))$

$\displaystyle =\int (\frac{d}{dx} (\sum_{k=1}^{N-1} \frac{1}{k} \left(\frac{1}{G(x)}\right)^k))$

$\displaystyle =\int ((\sum_{k=1}^{N-1} \left(\frac{1}{G(x)}\right)^{k-1})(-\frac{1}{G(x)^2} (G’(x)))$

$\displaystyle =\int (-G’(x)(\sum_{k=2}^{N} \left(\frac{1}{G(x)}\right)^{k}))$

$\displaystyle =\int (-G’(x)\frac{1}{G^2(x)}\frac{1-\frac{1}{G^{n-1}(x)}}{1-\frac{1}{G(x)}})$

$\displaystyle =\int (-G’(x)\frac{1-\frac{1}{G^{n-1}(x)}}{G^2(x)-G(x)})$

然后题解说 没有这么 麻烦，而且注意到 要求的是 $i[x^{-i}]H(G(x))$

这里一个“Note that”, 感觉注意不到,

我怎么知道G(x) 和 1/G(x) 的系数

如果 真的能得到 1/G(x) 的-1次方系数？和0次方系数?

牛顿法 计算G(x) mod x^N

$[x^0]G(x)=0$(因为带入x=0,有F(x)=0需要$G(F(x))-x=0$)

令 $A(G)=F(G)-x=0$

$G_{2d}(x)=G_{d}(x)-\frac{A(G_d(x))}{A’(G_d(x))} \pmod {x^{2d}}$

需要计算右侧 分子分母

  • $\displaystyle A(G_d(x)) = F(G_d(x))-x = \frac{G_d(x)^{k+1}-G_d(x)}{K(G_d(x)-1)} -x \pmod{x^{2d}}$
  • $\displaystyle A’=\frac{\frac{d}{dx}A(G_d(x))}{\frac{d}{dx}G_d(x)}$ 链式法则

总结

https://atcoder.jp/contests/abc345/editorial

E： 卡 黄题了，感觉在状态设计上没有保持尽量不变，而题解的状态 让每次更新时 只有 O(k)个会被更新，其它都是平移

F: 比E简单

Ex:

NTT 是显然，但优化完全不会

https://maspypy.com/%e5%88%86%e5%89%b2%e7%b5%b1%e6%b2%bbfft-%e3%81%ae%e3%82%88%e3%81%8f%e3%81%82%e3%82%8b%e5%bd%a2%e3%81%ae%e3%81%b2%e3%81%a8%e3%81%a4

相关

abc281Ex

abc260Ex Newton’s method

abc222H Lagrange inversion theorem

/algo/Newton_s_method

/algo/Lagrange_inversion_theorem

https://www.luogu.com.cn/problem/solution/AT_abc345_g

https://asecuritysite.com/gf/inv_poly

codeforces 生成函数 https://codeforces.com/blog/entry/77551

noshi91

luogu P5373 https://www.luogu.com.cn/problem/P5373

啊 noshi91有什么神奇的突破性进展？？？？？？？？？ https://noshi91.hatenablog.com/entry/2024/03/16/224034

https://www.cnblogs.com/yyyyxh/p/18081638/Bostan_Mori

https://www.luogu.com/article/7joh5isi

https://www.zhihu.com/question/371932147

$ans_i=[x^n]F(x)^i$， 并且对于批量的i需要求结果

$=y^i$

$=y^i$

$=[y^i]([x^n] \sum_{j=0}^{\infty}(yF(x))^j)$

$=[y^i][x^n] \frac{1}{1-yF(x)}$

一元变二元