Atcoder abc303

發表於 更新於 分類於 ， Disqus： 文章字數： 2.3k 所需閱讀時間 ≈ 8 分鐘
G(二维数组,小根堆,DP)Ex(Prüfer code)

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

G - Bags Game

n包, i个x[i]钱

每次3选1

  • 获得 最左/最右 一个
  • 获得 最左/最右 (一共B个,可以分别取一部分) - A元
  • 获得 最左/最右 (一共D个,可以分别取一部分) - C元

两人交替, 分别是X,Y, 求X-Y 的双方最优操作后的值，一个要最大，一个要最小

n 3000

xi,a,b,c,d, 1e9

2.5s

1024mb

我的思路

如果没有后两种

那就是经典的dp[l][r] = 从当前开始最优差值

dp[l][r] = max(x[l] - dp[l+1][r], x[r] - dp[l][r-1])

现在多了两种批量的情况

例如其中第二个方案就是 x[l...i] + x[j...r] - A - dp[i+1][j-1], len(l..i)+len(j..r) == B

但是注意到可以变换一下

x[l...r] - x[i+1..j-1] - A - dp[i+1][j-1], len(l..i)+len(j..r) == B

令 ndp[i..j] = x[i..j] + dp[i..j]

dp[l..r] = max(x[l] - dp[l+1][r],x[r]-dp[l][r-1],x[l..r] - A/C - ndp[i+1..j-1])

不妨设 第一种是 支付E=0元，取得F=1个

dp[l..r] = x[l..r] - min(A/C/E + ndp[i+1..j-1,A/C/E])

因此 需要一个 能够快速查询

[l...r]区间内 A/C/E + min(ndp[len(l..r)-B/D/F]) 即可

minndp[l..r] 可以通过minndp[l-1..r-1] 维护小根堆转移得到

代码

https://atcoder.jp/contests/abc303/submissions/42716988

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
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
template<class T> using minPQ=priority_queue<T,vector<T>,greater<T>>;
ll read(){ll r;scanf("%lld",&r);return r;}
int n;
ll x[3010];
ll prex[3010];
ll cost[3];  // {0,
int sz[3]={1}; // {1,
ll dp(int l,int r);
// min([l...r] 范围内, 长度 [(r+1-l) - sz[t]], ndp[i..j] = dp[i..j] + x[i..j]
ll minndp(int _l,int _r,int t){
  static ll mem[3010][3010][3];
  static bool vis[3010][3010][3];
  int len0 = (_r+1-_l);
  int len1 = len0 - sz[t];
  if(len1 <= 0) return 0;
  ll &res=mem[_l][_r][t];
  if(vis[_l][_r][t]) return res;
  // 一次 触发批量
  minPQ<array<ll,3> > pq;// {dp + x, pl, pr}
  int pl=1; // 还未加入的 子段,
  rep(l,1,n+1) { // [l...[pl..pr]...r]
    int r = l + len0 - 1;
    if(r > n) break;
    // [ll..rr]
    while(true){
      int pr = pl + len1 - 1;
      if(pr > r) break;
      pq.push({dp(pl,pr) + (prex[pr]-prex[pl-1]),pl,pr});
      pl ++;
    }
    while(pq.top()[1] < l) pq.pop();
    vis[l][r][t] = true;
    mem[l][r][t] = pq.top()[0];
  }
  return res;
}
ll dp(int l,int r) { // [l..r]
  static ll mem[3010][3010];
  static bool vis[3010][3010];
  assert(l <= r);
  ll &res=mem[l][r];
  if(vis[l][r]) return res;
  res = -0x3f3f3f3f'3f3f3f3f;
  vis[l][r] = true;
  rep(t,0,3) res = max(res, (prex[r] - prex[l-1]) - cost[t] - minndp(l,r,t));
  return res;
}
int main(){
  n = read();
  rep(t,1,3){
    cost[t] = read();
    sz[t] = read();
  }
  rep(i,1,n+1) prex[i]=prex[i-1]+(x[i]=read());
  printf("%lld\n",dp(1,n));
  return 0;
}

Ex - Constrained Tree Degree

给定 范围在[1,N-1]的K个数字的集合S

问点标签1~N的N点树且所有点的度$\in S$ 的树的个数 mod 998244353

n [2,2e5]

5s

1024mb

我的思路

首先 如果没有1, 那么肯定没有方案，所以考虑有1的情况， 所有叶子都是好的

那么如何唯一的表示一棵树？？？

考虑从根节点开始，每次放置的是 当前可延伸的最小节点

这样有性质， 不能小于它已经存在的兄弟节点

这样就可以用 [大小,最后值] 来表示, 每次放置以后 大小+1, 最后值变为新放入的, 并且多出一个[0,0]

而除了根，最终的大小+1$\in S$

然而感觉这就是 暴力得不能再暴力了，复杂度爆炸

我发现问题是，即使没有限制，我好像也不知道如何统计n点树的个数

这样一想

那先去掉限制

上面的方法维护的内容过多了，特别是这个最后的值

换个方式

1 开始，每次选点都是对所有叶子节点的最左选择所有的分支

这样对于1来说，出度为d的话，就是binom(n-1,d)

f(可放置叶子数量,剩余点个数)

$f(l,n) = \sum_{t=0\cdots n} f(l-1 + t, n-t) \binom{n}{t}$， 这样在最左候选点放置t个

令$g(i=l+n,j=n) = f(l,n)$

$g(i,j) = f(i-j,j) = \sum_{t=0\cdots j} f(i-j-1+t,j-t) \binom{j}{t}$, 这里变形后需要额外处理 $i \le j,g(i,j) = 0$吗???????????????????????????????????????????

$= \sum_{t=0\cdots j} g((i-j-1+t) + (j-t),j-t) \binom{j}{t}$

$= \sum_{t=0\cdots j} g(i-1,j-t) \binom{j}{t}$

$=j! \sum_{t=0\cdots j} \frac {g(i-1,j-t)}{(j-t)!} \frac{1}{t!}$

令$h(i,j) = \frac{g(i,j)}{j!}$

$h(i,j) = \sum_{t=0\cdots j}h(i-1,j-t) \frac{1}{t!}$

生成方程 $H_i(x) = H_{i-1}(x) e^x$

这样的话

其实就是 binom 这一块会变，也就是不可以选的t要让$\binom{n}{t}$ 变为$0$

这就直接让对应的$\frac{1}{t!} = 0$即可

依然要注意的是，根和非根不一样,所以上面小改一下变成f(可放置叶子数量,剩余点的个数,是否为根)

令$E_0(x) = \sum_{i,i \in S} \frac{1}{i!}x^i$

$E_1(x) = \sum_{i,i+1 \in S} \frac{1}{i!}x^i$

$E_0(x) = E_1(x) x$

要求的是ans = f(1,n-1,true) = g(n,n-1,true) = h(n,n-1,true) * (n-1)!

然而问题是这样的话，上面的依次计算 是n^2 log n的样子，虽然比暴力小了不少依然不行

所以 快速幂的方法

$H_n(x,true) = H_{n-1}(x,false)\star E_0(x) = H_0(x) E_1^{n-1}(x) E_1(x) x$

$ans = (n-1)! [x^{n-1}]H_{n}(x,true) = (n-1)! [x^{n-2}] E_1^{n}(x)$

样例1为例

n = 4, k = 2

s1=1,s2=3

ans = f(1,3,true) = g(1+3,3,true) = h(4,3,true) 3!

[x^3] H_4(x,true) = [x^3] H_3(x,false) (x+x^3/3!)

= [x^3] (1+x^2/2!)^3 (x+x^3/3!)

= 3/2! + 1/3!

$ans = 10$ 并不对

f(1,3,true) = f(3,0,false) + f(1,2,false) 3!

g(3+0,0,false) = 1

g(3+0,2,false) = 1

h(3,0,false) = 1/0! = 1

h(3,2,false) = 1/2! = 1/2!

但如果每次处理高位零才对

$h_1(x) = 1 + x^2/2! \mod x^1 = 1$

$h_2(x) = h_1(x) (1+x^2/2!) \mod x^2 = 1$

$h_3(x) = h_2(x) (1+x^2/2!) \mod x^3 = 1 + x^2/2!$

这样 $ans = 3! [x^3] (1+x^2/2!)(x+x^3/3!) = 3!(1/2!+1/3!) = 4$

所以如何 快速计算

$h_n(x) = h_{n-1}(x) E(x) \mod x^n$ 呢?

题解

Prüfer code

对于一个 无根 树，每次选择最小的叶节点，删除并向队列A（初始空）中添加这个被删节点连接的点，这样直到剩下两个节点

那么 队列A和树一一对应

性质

  1. 构造完后剩下的两个节点里，一定有一个是编号最大的节点。
  2. 对于一个 n度的节点，其必定在序列中出现 n−1 次. 因为每次删去其子节点它都会出现一次，最后一次则是删除其本身。推论: 一次都未出现的是原树的叶子节点。

还原：

根据性质2,显然把序列未出现的最小的叶子节点 和 A[0]连接，那么变成了 A[1:]的子问题, 重复操作即可

至此关于prufer code的 正向和逆向证完，注意到还原操作显然的唯一性，而任何树可以产生队列，因此一一对应

另一方面，对于任意长度N-2,值域[1,N]的序列，抽屉原理长度 < 剩余点数, 所以总可以建立新的边, 而且 注意到 每次是一个队列中和队列外的建立边，所以永不成环, 另一方面不成环的n点n-1条边 一定是连通成树的不会不连通，所以神奇的这样有N^{N-2}个树

而基于这个性质，问题变成有多少个 长度n-2值序列1~N，且每个值出现次数在 {s_i-1} 中呢

这样就无脑做了 $(N-2)![x^{N-2}] (\sum_{i+1\in S} \frac{1}{i!}x^i)^N$

代码

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
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}

int main(){
  int n=read();
  vector<mint> fac(n+1,1);
  rep(i,1,n+1) fac[i]=fac[i-1]*i;
  vector<mint> ifac(n+1,1);
  ifac[n]=fac[n].inv();
  per(i,0,n) ifac[i]=ifac[i+1]*(i+1);
  vector<mint> E(n+1,0);
  int k=read();
  rep(i,0,k) {
    int s=read();
    E[s-1] = ifac[s-1];
  }
  if(E[0] == 0) return printf("0\n")*0;
  vector<mint> res = {1};
  int p=n;
  while(p){
    if(p & 1) {
      res = atcoder::convolution(res,E);
      res.resize(n,0);
    }
    E = atcoder::convolution(E,E);
    E.resize(n,0);
    p/=2;
  }
  printf("%d\n",(fac[n-2]*res[n-2]).val());
  return 0;
}

总结

G

没怎么想也想出来了,这题评分怎么这么高不科学，

Ex

感觉比G难但是 评分却更低，第一次见 Prüfer code，学习了

在大的思路还是在向生成方程靠拢，但是搞了一个我自己不会快速计算的 $H_n(x) = H_{n-1}(x) E(x) \mod x^n$

$\displaystyle F(x) = \sum_{i+1\in S} \frac{1}{i!}x^i$

$\displaystyle G_0(x) = 1$

$\displaystyle G_n(x) = G_{n-1}(x) F(x) \mod x^n$

$\displaystyle (n-1)[x^{n-2}]G_n(x) =?= [x^{n-2}]F^n(x)$

这对吗，以及如果对的话，这$F(x)$换成一般的也相等吗?

参考

官方题解