Atcoder abc281

發表於 更新於 分類於 ， Disqus： 文章字數： 1.9k 所需閱讀時間 ≈ 6 分鐘
G(DP)Ex(生成函数,cdq分治)

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

G - Farthest CIty

问 n个点, 的简单连通图, 1到n的距离 严格大于所有1到其它点的距离的 图有多少个

个数 mod m

范围

n 500

m [1e8,1e9]

4s

1024mb

我的思路

数数嘛, 对于一个具体的图, 考虑计算所有点到1的距离,看一下相邻点的性质,

显然 相邻点的距离值 差不大于1

所以有一个O(n^4) 的dp

dp[最大距离为i][距离为i的有j个][距离<=i的有k个] = 的方案数

有转移 dp[i][j0][k0] = dp[i-1][j1][k1] * binom(n-k1,j0)/j0个在剩下的中选/ * (2^(j1)-1)^j0(每个分别和前面j1的连接方式) * 2^(j0(j0-1)/2) (j0个内部的任意连接) , 其中 k0=k1+j0

这样答案就是 sum dp[1..n][1][n]

要是能优化成O(n^3)就能过了, 比赛时想了半天, 发现i无关, 想说矩阵乘法快速幂次, binom拆一拆 搞了半天

赛后又想了想, 可以完全不要 i 直接 dp[用了k个点][最大距离的有j个点]的方案数 就完了………………..

dp[i0][j0] = dp[i1][j1] * binom(n-i1,j0) * (2^{j1}-1)^j0 * 2^(j0(j0-1)/2), 其中 i0=i1+j0

ans=dp[n][1]

其实这里有点问题, 因为中间选的时候不能选择 最后一个

所以不妨 先把 n拿出来 最后考虑它

这样转移方程不变

ans= sum dp[n-1][j=1..n-1] * (2^j-1)

然后加个预处理 去掉 中间的log复杂度

代码

https://atcoder.jp/contests/abc281/submissions/37193246

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
#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 dp[510][510]; // dp[用i个点][最大距离有j个点]
ll binom[510][510];
ll p2[250010]={1};
ll cache[510][510]; // cache[i][j] = (2^i-1)^j

int main(){
  ll n=read(); // 500 n 点, 简单无向 联通图, 1-n严格长于1-其它
  ll m=read(); // 1e8~1e9
  rep(i,0,501) binom[i][i]=binom[i][0]=1;
  rep(i,1,501) rep(j,1,i) binom[i][j]=(binom[i-1][j]+binom[i-1][j-1])%m;
  rep(i,1,250001) p2[i]=p2[i-1]*2%m;
  rep(i,1,501) {
    cache[i][0]=1;
    ll base=p2[i]-1;
    rep(j,1,501) cache[i][j]=cache[i][j-1]*base%m;
  }
  dp[1][1] = 1;
  rep(i,1,n) rep(j,1,i+1) if(dp[i][j]) rep(j1,1,n) if(i+j1<=n-1){ // 最后一个先不考虑, (i,j) => (i+j1,j1)
    (dp[i+j1][j1] += dp[i][j]
     *binom[n-1-i][j1]%m
     *cache[j][j1]%m
     *p2[j1*(j1-1)/2]%m )%=m;
  }
  ll ans=0;
  rep(i,1,n-1) (ans+=dp[n-1][i]*(p2[i]-1)%m)%=m;
  printf("%lld\n",ans);
  return 0;
}

Ex - Alchemy

田中有 A种 等级1的 宝石, 每种都有无限多个

对于 n >= 2, 可以通过按照下面方式 生成一个等级n的宝石

n个不同类型的不同类型的宝石, 每个等级< n, 对于每个> 2 级的宝石至多1个

问 有多少种 等级 n的宝石

范围

n 2e5

a 1e9

4s

1024mb

我的思路

这题目感觉 生成函数 味道十分浓

$f_{lvl}(x)$ 等级lvl的宝石 选了i个的方案数的生成函数

等级$n$的宝石 有$ans_n = \lbrack x^n \rbrack \prod_{i=1}^{n-1} f_{i}(x)$

注意到 除了等级1, 其它等级在合成时, 每个等级只能选1个或0个 所以当$i > 1$时, 生成函数可以写成 $f_i(x) = 1+ans_i x$

而等级1, $f_1(x) = 1+Ax+k_{A,2}x^2+k_{A,3}x^3+\cdots$

$k_{i,j} $ 从i个颜色中选j个的方案数,$= \lbrack x^j \rbrack (1+x+x^2+x^3+\cdots)^i = \lbrack x^j \rbrack (\frac{1}{1-x})^i = (-1)^j \binom{-i}{j} = \binom{i+j-1}{j} $

$f_1(x) = 1+\binom{A}{1} x+\binom{A+1}{2}x^2+\binom{A+2}{3}x^3\cdots = (\frac{1}{1-x})^i$

$f_2(x) = 1+\binom{A+1}{2}x$

$ans_3 = \lbrack x^3 \rbrack f_1(x) f_2(x) = \binom{A+2}{3} +\binom{A+1}{2}\binom{A+1}{2}$

问题就是 如果直接每次做多项式乘法, 那么 这样 每次都是O(n) 总的复杂度会是 O(n^2)

但这个计算过程似乎可以用二维数组描述

dp[i][j]= 前i个生成函数生成的第j个系数

ans_2 = dp[1][2]

ans_3 = dp[2][3] = dp[1][2] + dp[1][1]*ans_2

ans_i = dp[i-1][i]

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * dp[i-1][i]

题解

一样的

也是 同样的生成函数

这里也说 对于 O(N) 和 (1+a_ix) 的多项式 乘法 难以优化

这里说 用cdq分治就好了

1
2
3
4
5
6
7
8
9
// g 表示 f(x)(1+a_2 x)...(1+a_{l-1} x), 主要用来 取 ai
// 返回 (1+a_l x)(1+a_{l+1} x)...(1+a_{r-1} x), 没有f(x)
vector<mint> dc(int l,int r,vector<mint> g){ // dc [l,r) 返回的幂次 肯定是 r-l
  if(r-l==1)return {1,g[l]};

  int m = (l+r)/2;
  vector<mint> temp = dc(l,m,g); // [l..m), 最高幂次m-l
  return convolution(temp,dc(m,r,convolution(g,temp))); //然而这里 还是会tle, 因为每次g的大小还是O(n) 所以 这里和g的
}

递归证明一个性质, dc(l,r 只需要 g的[l..r))

对于r-l ==1 显然

按长度递归证明, dc(l,m,g) 需要 g[l..m)

dc(m,r,convolution(g,temp)) 需要 convolution(g,temp(最高幂次m-l))[m..r), 需要g的 [m-(m-l)…r-0)

递归得证, 这样就保证了复杂度

1
2
3
4
5
6
7
8
9
// g 表示 f(x)(1+a_2 x)...(1+a_{l-1} x), 中[l..r) 的系数 主要用来 取 ai
// 返回 (1+a_l x)(1+a_{l+1} x)...(1+a_{r-1} x), 没有f(x)
vector<mint> dc(int l,int r,const vector<mint>& g){ // dc [l,r) 返回的幂次 肯定是 r-l
  if(r-l==1)return {1,g[0]};

  int m = (l+r)/2;
  vector<mint> temp = dc(l,m,g[0..m-l) ); // [l..m), 最高幂次m-l
  return convolution(temp,dc(m,r,convolution(g,temp)[m-l..r-l) ));
}

然后 我上面还有点弱智 错误, 说的每次不能选同样种类的

所以$f_1(x)$ 的就是简单的 $\sum_{i=0}^{\infty} \binom{A}{i} x^i$, 没那么复杂

代码

https://atcoder.jp/contests/abc281/submissions/37194740

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
#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++)

ll read(){ll r;scanf("%lld",&r);return r;}

int n;
mint ans=0;

template<class T>
vector<T>vec(const vector<T>a,int l,int r){ return vector<T>(a.begin()+l,a.begin()+r); }

// g 表示 f(x)(1+a_2 x)...(1+a_{l-1} x), 中[l..r) 的系数 主要用来 取 ai
// 返回 (1+a_l x)(1+a_{l+1} x)...(1+a_{r-1} x), 没有f(x)
vector<mint> dc(int l,int r,const vector<mint>& g){ // dc [l,r) 返回的幂次 肯定是 r-l
  if(l==n) ans=g[0];
  if(r-l==1) return {1,g[0]};
  int m = (l+r)/2;
  auto glm=vec(g,0,m-l); // g[0..m-l) = g[l..m)
  auto dclm = dc(l,m,glm);
  auto gmr = vec(convolution(g,dclm),m-l,r-l); // (g*dclm)[m-l..r-l) = g[m..r)
  return convolution(dclm,dc(m,r,gmr));
}

int main(){
  n=read();
  mint a=read();
  if(n==1){
    printf("%d\n",a.val());
    return 0;
  }
  mint coef=1;
  vector<mint> f={coef};
  rep(i,1,n+1) f.push_back(coef=(coef*(a-i+1)/i));
  dc(2,n+1,vec(f,2,n+1));
  printf("%d\n",ans.val());
  return 0;
}

总结

G

没啥难的

这… 为啥会多想一个维度, 哎 太菜了

Ex

这次算是 建立生成函数 的部分 自己能想到了

但是 这种 像是cdq 分治的还是不熟 ,遇到了两三次了? 就是用来处理这种 递归 多项式 形状的东西

虽然说如果提前知道所有ai ,还是会用分治去处理 prod (1+ai x),这里也想到了, 但是这种在过程中获取ai的就真没想到具体的操作

参考

官方题解