Atcoder abc281

發表於 2022-12-10 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus： 0 Comments 文章字數： 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]

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

#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

1024mb

我的思路

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

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

等级 $n$ 的宝石有 $a n s_{n} = [x^{n}] \prod_{i = 1}^{n - 1} f_{i} (x)$

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

而等级1, $f_{1} (x) = 1 + A x + k_{A, 2} x^{2} + k_{A, 3} x^{3} + \dots$

$k_{i, j}$ 从i个颜色中选j个的方案数, $= [x^{j}] (1 + x + x^{2} + x^{3} + \dots)^{i} = [x^{j}] (\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} \dots = (\frac{1}{1 - x})^{i}$

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

$a n s_{3} = [x^{3}] 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分治就好了

// 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)

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

// 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

#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;
}

总结

没啥难的

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

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

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

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

参考

官方题解